HashTable

HashTable In Java 7
在线程安全的 HashTable中，其hash的实现：

  hash = key.hashCode();
   index = (hash & 0x7FFFFFFF) % tab.length;

可见，和HashMap的“&”不同的是，直接取模“%”

1.为何把hash值和0x7FFFFFFF做一次按位与操作呢？

Because:

• 0x7FFFFFFF is 0111 1111 1111 1111 1111 1111 1111 1111 : all 1 except the sign bit.

• (hash & 0x7FFFFFFF) will result in a positive integer.

• (hash & 0x7FFFFFFF) % tab.length will be in the range of the tab length.
  哈哈，说人话就是
  为了保证得到的index的第一位为0，也就是为了得到一个正数。因为有符号数第一位0代表正数，1代表负数。

HashTable采用简单的取模是有一定的考虑在的。这就要涉及到HashTable的构造函数和扩容函数了。由于篇幅有限，这里就不贴代码了，直接给出结论：

HashTable默认的初始大小为11，之后每次扩充为原来的2n+1。

也就是说，HashTable的链表数组的默认大小是一个素数、奇数。之后的每次扩充结果也都是奇数。

由于HashTable会尽量使用素数、奇数作为容量的大小。当哈希表的大小为素数时，简单的取模哈希的结果会更加均匀。（这个是可以证明出来的，由于不是本文重点，暂不详细介绍，可参考：http://zhaox.github.io/algorithm/2015/06/29/hash）

2.关于hash函数为什么要选择对素数求余?
一组均匀分布的key，其中同m公约数为1的那部分，余数后在[0,m-1]上还是均匀分布的，但同m公约数不为1的那部分，余数在[0, m-1]上就不是均匀分布的了。把m选为素数，正是为了让所有key同m的公约数都为1，从而保证余数的均匀分布，降低冲突率。
例子：一组key值 12、5、7、16、22 同m=5公约数分别为2、1、1、3、4
同m公约数不为1的那部分，余数是0、2
但同m公约数不为1的那部分，余数是 2、2、1可见不是均匀分布的；