史上最强算法论战：请不要嘻哈，这是哈希 文章中算法的java实现

  最近在学习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;
		}
	}
	
}