哈希表实现与优化：理解哈希算法与位运算的应用

*********************************************
http://www.hollischuang.com/archives/2091
****************************************
Hash 
HashTable  线程安全 效率低 key 和 value 不能为null 
ConCurrentMap

Hash,一般称散列，也可称作 哈希。
Hash 表综合了数组和链表的优点。实际上是一个数组链表 ，数组元素是一个链表。

hash算法通过 对不同的输入，通过散列算法，计算得出一个相同长度的输出。以这个值确定数组的下标。

hash()调用 hashCode()方法计算哈希值。对于不同的输入，哈希值可能会相同，如果相同的话就调用，equals()比较元素的内容是否相同。如果这两个方法
比较后都是相同的话则判定为同一元素。
如果，该哈希值位置已有元素的话。则将该元素放置在链表的第一位。

hash()方法将Object转换成一个整形
indexFor()将hash生成的整形转换成链表数组的下标

位运算&效率比取模效率%要高很多。位运算直接对内存数据进行操作，不需要转成十进制，因此处理速度特别快。
*********************************************
X % 2^n = X & (2^n – 1)
2^n表示2的n次方，也就是说，一个数对2^n取模 == 一个数和(2^n – 1)做按位与运算 。
假设n为3，则2^3 = 8，表示成2进制就是1000。2^3 = 7 ，即0111。
此时X & (2^3 – 1) 就相当于取X的2进制的最后三位数。
从2进制角度来看，X / 8相当于 X >> 3，即把X右移3位，此时得到了X / 8的商，而被移掉的部分(后三位)，则是X % 8，也就是余数。
***********************************************************************
其实，使用位运算代替取模运算，除了性能之外，还有一个好处就是可以很好的解决负数的问题。因为我们知道，hashcode的结果是int类型，而int的取值范围是-2^31 ~ 2^31 – 1，即[ -2147483648, 2147483647]；这里面是包含负数的，我们知道，对于一个负数取模还是有些麻烦的。如果使用二进制的位运算的话就可以很好的避免这个问题。首先，不管hashcode的值是正数还是负数。length-1这个值一定是个正数。那么，他的二进制的第一位一定是0（有符号数用最高位作为符号位，“0”代表“+”，“1”代表“-”），这样里两个数做按位与运算之后，第一位一定是个0，也就是，得到的结果一定是个正数。
****************************************************************************
HashTable默认的初始大小为11，之后每次扩充为原来的2n+1。