要哈希不要嘻哈

在阅读JAVA中HashMap的源码时，以前数据结构学的都又回到脑海中，JAVA中的HashMap是"链表散列"的结构。有些收获点在此记录。

1. 基本结构Entry为 key-value，HashMap中的Entry<K,V>结构大致如下：

static class Entry<K,V> implements Map.Entry<K,V>{

final K key;

V value;

Entry<K,V> next;

final int hash;

.......

}

HashMap这里的Entry<K,V>相当于《数据结构》中节点node，Entry包含key（常量），value，hash（哈希值）和指向下一个Entry结构的引用。这么一来，一个Entry就相当于一个链表了。

2. HashMap本身的成员变量如下：

//The table, resized as necessary. Length MUST Always be a power of two.

transient Entry[] table;

（核心结构，table是一个Entry类型的数组，每一个元素都是Entry节点的链表。）






//The default initial capacity - MUST be a power of two.
static final int  DEFAULT_INITIAL_CAPACITY = 16;



默认哈希表的初始容量，必须为2的多少次幂。为什么？正确答案：这是为了让元素在数组中分布均匀，而且为元素在数组中位置的计算速度优化做了铺垫。

考虑哈希表要添加一个元素，现在假设前提是某个Entry的hash值已经计算出来，那么我们都知道哈希表下一步就是根据这个hash值

把Entry放在table数组的某个位置。我们首先想到的就是把hash值对数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的。但是，“模”运算的消耗还是比较大。我们看一下Java的牛人是怎么写的。Java源码中indexFor(int h, int length) 方法用来计算某Entry对象应该保存在 table 数组的哪个索引处，其代码如下：

static int indexFor(int h, int length) {
return h & (length-1);
}
这个h为Entry的哈希值，length为table数组的长度。
这个方法简单而又非常巧妙，它通过 h & (table.length -1) 来得到该对象的保存位，而HashMap底层数组的长度总是 2 的 n 次方，这里就是HashMap在速度上优化的一个点。在 HashMap 构造器中有如下代码：


int capacity = 1;
   while (capacity < initialCapacity)
       capacity <<= 1;
   这段代码保证初始化时HashMap的容量总是2的n次方，即底层数组的长度总是为2的n次方。
当length总是 2 的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。

   这看上去很简单，其实比较有玄机的，我们举个例子来说明：
   假设数组长度分别为15和16，优化后的hash码分别为8和9，那么&运算后的结果如下：
       h & (table.length-1)         hash               table.length-1
       8 & (15-1)：                      0100      &              1110         =       0100
       9 & (15-1)：                      0101      &              1110         =       0100
       --------------------------------------------------------------------------------------
       8 & (16-1)：                      0100       &             1111         =       0100
       9 & (16-1)：                      0101       &             1111         =       0101
 
   从上面的例子中可以看出：当它们和15-1（1110）“与”的时候，产生了相同的结果，也就是说它们会定位到数组中的同一个位置上去，这就产生了碰撞，8和9会被放到数组中的同一个位置上形成链表，那么查询的时候就需要遍历这个链 表，得到8或者9，这样就降低了查询的效率。同时，我们也可以发现，当数组长度为15的时候，hash值会与15-1（1110）进行“与”，那么 最后一位永远是0，而0001，0011，0101，1001，1011，0111，1101这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！而当数组长度为16时，即为2的n次方时，2n-1得到的二进制数的每个位上的值都为1，这使得在低位上&时，得到的和原hash的低位相同，加之hash(int h)方法对key的hashCode的进一步优化，加入了高位计算，就使得只有相同的hash值的两个值才会被放到数组中的同一个位置上形成链表。

所以说，当数组长度为2的n次幂的时候，不同的key算得得index相同的几率较小，那么数据在数组上分布就比较均匀，也就是说碰撞的几率小，相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就较高了。现在明白为什么MUST be a power of two 了吧。Java在这里充分考虑了速度的优化。



static final int MAXIMUM_CAPACITY = 1 << 30;

//The load factor used when none specified in constructor.

static final float DEFAULT_LOAD_FACTOR = 0.75f;

这个0.75是HashMap的负载因子，即数据结构做题的时候算的那个 “散列表的实际元素数目(n)/ 散列表的容量(m)”。

负载因子衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。对于使用链表法的散列表来说，查找一个元素的平均时间是O(1+a)，因此如果负载因子越大，对空间的利用更充分，然而后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。

//The number of key-value mappings contained in this map.

transient int size;

size 用于记录Entry的总数

//The next size value at which to resize (capacity * load factor).

int threshold;

threshold为Entry数目的上限，为容量和负载因子的乘积。当size超过了threshold时，将table进行扩容。



/**

    * The number of times this HashMap has been structurally modified

    * Structural modifications are those that change the number of mappings in

    * the HashMap or otherwise modify its internal structure (e.g.,

    * rehash).  This field is used to make iterators on Collection-views of

    * the HashMap fail-fast.  (See ConcurrentModificationException).

    */

transient volatile int modCount;

modCount记录对HashMap结构性修改的次数，modCount声明为volatile，保证线程之间修改的可见性。我们知道 java.util.HashMap不是线程安全的，因此如果在使用迭代器的过程中有其他线程修改了map，那么将抛出 ConcurrentModificationException，这就是所谓fail-fast策略。

未完待续。。。



参考 http://beyond99.blog.51cto.com/1469451/429789