最近在学习pomelo的时候,偶然在网上看到博文《史上最强算法论战:请不要嘻哈,这是哈希》
http://chuansong.me/n/1489885
被作者的文笔吸引,对其中的干货很有兴趣,随后用一周时间进行了膜拜。现将学习结果总结如下。
- 1.所谓无锁设计,是不使用编程语言的多线程锁转而使用cpu的锁(总线锁,寄存器锁,缓存锁)
- 2.CAS原语有好多种写法,目前的物理服务器都是多cpu多核心,所以需要按Test and test and set 的写法编程。
- 3.当前的现代cpu,Cache Line 是64byte .机器的字长是64bit.cpu只对16,32,64 bit的数据提供原子操作。
未解决的问题:这货到底是用在什么业务场景的,一直没想明白,所以也没办法写出来测试程序。请iteye上的大师指点。
package testPatternBox;
import java.util.concurrent.atomic.AtomicLong;
import java.util.concurrent.locks.LockSupport;
class BackOffAtomicLong
{
private final AtomicLong value = new AtomicLong ( 0L );
public long get ( )
{
return value.get ( );
}
public long incrementAndGet ( )
{
for ( ;; )
{
long current = get ( );
long next = current + 1;
if ( compareAndSet ( current ,
next ) )
return next;
}
}
public long subtractAndGet ( )
{
for ( ;; )
{
long current = get ( );
long next = current - 1;
if ( compareAndSet ( current ,
next ) )
return next;
}
}
public boolean compareAndSet ( final long current ,
final long next )
{
if ( value.compareAndSet ( current ,
next ) )
{
return true;
}
else
{
LockSupport.parkNanos ( 1L );
return false;
}
}
public void set ( final long l )
{
value.set ( l );
}
}
class DataItem
{// 数据项
/**
* 而compoundKey为(股东代码,股票代码,持仓类型,flag)的复合体,股东代码占用最63~27位(5位字符和四个字节无符号整数),
* 股票代码占26~11位(两个字节),持仓类型占用10~6位(五个字节),isTail占用第5位,表示是否为尾部,
* 即后继元素中没有相同hash值的元素。 doWrite占用第4位,表示该key正在更改/写入,
* readerCount占用3~0为表示该key正在读的线程数量。
*/
/**
* 每条持仓记录,由三个信息来定位(key): 持仓类型(一位字符,A~F), 股东代码(10位字符,第1位A~Z,后面9位是数字0~9),
* 股票代号(short类型)
*
* 被定位到的持仓记录是一个64bit的值(value)
*/
private BackOffAtomicLong compoundKey = new BackOffAtomicLong ( ); // 数据项的关键字
private BackOffAtomicLong value = new BackOffAtomicLong ( );;// 存储的值
public DataItem ( Long key , Long value )
{
this.compoundKey.set ( key );
this.value.set ( value );
}
public Long getKey ( )
{
return compoundKey.get ( );
}
public BackOffAtomicLong getBackOffAtomicLongKey ( )
{
return compoundKey;
}
public boolean setKey ( Long key )
{
return this.compoundKey.compareAndSet ( this.compoundKey.get ( ) ,
key );
}
public Long getValue ( )
{
return value.get ( );
}
public BackOffAtomicLong getBackOffAtomicLongValue ( )
{
return value;
}
public boolean setValue ( Long value )
{
return this.value.compareAndSet ( this.value.get ( ) ,
value );
}
public boolean equals ( DataItem di )
{
if ( this.getKey ( ) == di.getKey ( ) && this.getValue ( ) == di.getValue ( ) )
return true;
else
return false;
}
}
class DataItemUtils
{// 用来处理DataItem元素 ,由于看不懂文章里的维护策略,暂时没有使用。
/**
* tail位为0时表示不是尾,为1时表示是尾
*
* @return 是否是最后一个元素
*/
public static boolean isTail ( DataItem i )
{
return ( ( i.getKey ( ) ) & ( 12L ) ) == 12L;
}
public static boolean setIsTail ( DataItem i )
{
return i.setKey ( i.getKey ( ) | 12L );
}
public static boolean setIsNotTail ( DataItem i )
{
return i.setKey ( i.getKey ( ) & 9223372036854775791L );
}
/**
* 0 未写入 1正在写入
*
* @param i
* @return
*/
public static boolean isWrite ( DataItem i )
{
return ( ( i.getKey ( ) ) & ( 8L ) ) == 8L;
}
public static boolean setIsWrite ( DataItem i )
{
return i.setKey ( i.getKey ( ) | 8L );
}
public static boolean setIsNotWrite ( DataItem i )
{
return i.setKey ( i.getKey ( ) & 9223372036854775799L );
}
/**
* 是否有线程在读
*/
public static boolean isReading ( DataItem i )
{
return ( ( i.getKey ( ) ) & ( 7L ) ) != 0L;
}
public boolean incrementReading ( DataItem i )
{
if ( ( ( i.getKey ( ) ) & ( 7L ) ) == 7L )
return true;
i.getBackOffAtomicLongKey ( ).incrementAndGet ( );
return true;
}
public boolean subtractReading ( DataItem i )
{
if ( ( ( i.getKey ( ) ) & ( 7L ) ) == 0L )
return true;
i.getBackOffAtomicLongKey ( ).subtractAndGet ( );
return true;
}
}
public class MemoryHashTable
{// 数组实现的哈希表,开放地址法之再哈希法
private DataItem[] hashArray; // 存数据的数组
private int arraySize;
private DataItem nonItem; // 已删除标志
private int contstant; // 二次hash函数因子。
MemoryHashTable ( int size )
{// 哈希表构造函数
arraySize = findPrimeNumber ( size );
hashArray = new DataItem[arraySize];
nonItem = new DataItem ( -1L , -1L );
contstant = findPrimeNumber ( arraySize / 10 );
}
public void displayTable ( )// 输出哈希表
{
System.out.print ( "Table: " );
for ( int j = 0 ; j < arraySize ; j++ )
{
if ( hashArray[j] != null )
System.out.print ( hashArray[j].getKey ( ) + " " );
else
System.out.print ( "** " );
}
System.out.println ( "" );
}
// 哈希函数1
private int hashFunc1 ( long key )
{
return Integer.parseInt ( Long.toString ( key % arraySize ) );
}
// 哈希函数2,不同于哈希函数1,用于再哈希。
private int hashFunc2 ( long key )
{
// array size must be relatively prime to 5, 4, 3, and 2
return Integer.parseInt ( Long.toString ( contstant - key % contstant ) );
}
// 哈希表中插入数据 这里的CAS是 Test and Test and Test and set
public void insert ( long key ,long value)
{
int hashVal = hashFunc1 ( key); // 求关键字的哈希值
int stepSize = hashFunc2 ( key ); // 再探测步长的大小
while ( hashArray[hashVal] != null && hashArray[hashVal].getKey ( ) != -1 )
{
if ( hashArray[hashVal].getKey ( ) == key)
{
//判断当前对象是我们要操作的对象
hashArray[hashVal].setValue ( value );
return ;
}
else
{
hashVal += stepSize; // 单元被占用,再探测
hashVal %= arraySize;
}
}
//此处存在线程不安全问题,如果两个线程中的hashkey完全相同,同时写这个hashVal位置会怎么样???
hashArray[hashVal] = new DataItem ( key , value );
}
// 在哈希表中删除
public DataItem delete ( long key )
{
int hashVal = hashFunc1 ( key );
int stepSize = hashFunc2 ( key );
while ( hashArray[hashVal] != null )
{// 直到一个空单元出现
if ( hashArray[hashVal].getKey ( ) == key )
{
DataItem temp = hashArray[hashVal];
hashArray[hashVal] = nonItem; // 作删除标记
return temp;
}
hashVal += stepSize; // 再探测
hashVal %= arraySize;
}
return null;
}
// 在哈希表中搜索
public long find ( long key )
{
int hashVal = hashFunc1 ( key );
int stepSize = hashFunc2 ( key );
while ( hashArray[hashVal] != null )
{
if ( hashArray[hashVal].getKey ( ) == key )
return hashArray[hashVal].getValue ( );
hashVal += stepSize;
hashVal %= arraySize;
}
return 0L;
}
/**
* 找出大于capacity 的最小质数,并且该质数容量是minseed的7分之10 hashtable的装载率不能大于70%
* 用开放地址探测的散列,要保证在一定步数内找到一个空位, 你必须让数组长度为一个质数。在装载率为70%的情况下,
* 一个质数长度的数组,基本就是几步之内你就一定能找到一个空位。
*
* @param capacity
* hashtable的容量。
*
* @return
*/
private Integer findPrimeNumber ( int capacity )
{
capacity = capacity * 10 / 7; // 预计装载量是hashtable容量的70%
if ( capacity % 2 == 0 )
{
// 质数肯定是奇数
capacity++ ;
}
if ( capacity <= 1 )
{
return 2;
}
if ( capacity == 2 || capacity == 3 )
{
return 5;
}
while ( true )
{
int sqrt = (int) Math.sqrt ( capacity );
for ( int i = 3 ; i <= sqrt ; i += 2 )
{
if ( capacity % i == 0 )
{
capacity += 2;
break;
}
}
return capacity;
}
}
}
分享到:
相关推荐
最快的排序算法 java实现哈希算法-Java–哈希算法–最快的实现,排序算法数据结构
参考网上博客的感知哈希算法的理论知识,实现基本的感知哈希算法,内有几张图片用来测试,程序可参考。
哈希算法C语言实现
暴雪公司有个经典的字符串的hash公式,先提一个简单的问题,假如有一个庞大的字符串数组,然后给你一个单独的字符串,让你从这个数组中查找是否有这个字符串并找到它,你会怎么做?有一个方法最简单,老老实实从头查...
哈希表算法C++实现 SGI 哈希表是一个线性存储结构,其关键是哈希函数与哈希值算法
基于python与哈希算法实现图像去重
最快的排序算法 javahash实现-Java-哈希算法-最快的实现,排序算法数据结构
内容概要: 1,哈希算法概念 2,哈希函数 3,冲突的解决方法 4,哈希算法应用
输入:待哈希数据序列 功能要求:输出哈希方法和解决冲突的方法(文字输出),输出哈希表
本文件为本人经过测试的能够直接应用于8位单片机的sha1-hash算法源码,解决了以往在PC机上实现或32位编译器实现的sha1算法无法兼容低端处理器的问题。
一致性哈希算法
附件中是布谷鸟算法的Java版本的代码实现,可以正常运行;下载者可以根据自己的应用场景来修改。
提供了获取哈希值接口、获取哈希算法标识已经使用算法值接口源码,接口都是正式封装的,IDEA编译,输出结果符合官方数据
SHA256函数是HASH算法中一种,区块链中广泛使用sHA256算法对交易信息进行加密。 该算法涉及到很多进制转换和二进制逻辑运算。
一致性哈希算法,广泛应用于分布式计算,C版实现,属于分布式服务器管理的核心算法。
哈希表算法实现 建哈希表 mid函数先把参数平方,然后取中间的第4、5位作为地址返回
多种哈希算法代码,用于文件校验、简单加密等场合。
每一章的末尾都会有一系列问题和对应的回答,旨在强调这一章的重要思想……《算法精解:C语言描述》中的代码尤为值得强调:所有实现都采用C语言编写,所有代码都优先用于教学目的,所有代码都在4种平台上经过完整测试...
哈希算法的实现c++
SHA256 哈希密码算法C语言实现 亲测好用。只要SHA256的实现。