Hash Map 源码解读之初篇

Hash Map 一直在用，但是没想过要看下源码，理解下原理，遇到个好老大，让我去弄懂原理。为了验证自己的掌握程度，在这里做个输出。

第一次看源码，没能完全理解，所以就输出下自己了解到的一些内容。

上源码截图之前先说明两个概念：

    a.  hash map 中，被存储的key-value键值对，可以理解为一个entry。即Node<K,V> implements Map.Entry<K,V>。

    b.  DEFAULT_INITIAL_CAPACITY 默认容量，即Node<K,V>[] tab 的size。很多文章上写这个是个buckets size，我没有找到出处，为了不在后续的说明里让大家感到困惑，这里先标注一下。

另外， 源码上面的注释我就不翻译了，大家可以自行去阅读，还是很有帮助的。

源码截图1：

图1 主要默认属性值

DEFAULT_INITIAL_CAPACITY：hash map的默认初始化容量16。如果没有指定初始化大小，那么当 hash map的entry size超过 16 * load_factor (0.75f) = 12 这个容量时，自动resize，内部调整hash map的大小到原来的2倍。

MAXIMUM_CAPACITY：最大容量1073741824，即2的30次方。

DEFAULT_LOAD_FACTOR：负载因子0.75f，可以把这个值看作是调整默认容量的一个阀值。

TREEIFY_THRESHOLD：是否转成树的阀值。当buckets的某个index上的链表过长(大于等于TREEIFY_THRESHOLD)，就把链表转换成红黑树。

源码截图2:

图2 node class

基本的hash bin node，用于大多数条目，我的理解就是Map.Entry的实现。

源码截图3:

图3 hash方法

上面的英文注释已经写的很清楚了，通过hash方法获得hash值，再通过获得的hash值计算buckets下标。即获得key.hashCode()，然后右移16位，再跟key.hashCode()进行异或操作，获得hash值。

那到这里就要引出一个概念：collisions 碰撞。即2个不同key的hash值一样，就会产生碰撞。

原文的注释说：设计者认为这方法很容易发生碰撞。因为，在n - 1为15(0x1111)时，其实散列真正生效的只是低4bit的有效位，当然容易碰撞了。因此，设计者想了一个顾全大局的方法就是把高16bit和低16bit异或了一下。设计者还解释到因为现在大多数的hashCode的分布已经很不错了，就算是发生了碰撞也用O(logn)的tree去做了。仅仅异或一下，既减少了系统的开销，也不会造成的因为高位没有参与下标的计算(table长度比较小时)，从而引起的碰撞。

那既然说到碰撞了，我们看下putVal的源码：

图4 put方法

图5 putVal方法

我们看到通过hash(key)获得hash值后，(n -1) &hash 获得buckets下标。

如果没碰撞直接放到buckets里，如果碰撞了，将entry加到链表头部，避免尾部遍历。（我看代码是插入尾部，但是看资料写的头部，等我深入理解再来修正。）

如果节点已经存在就替换old value(保证key的唯一性)。

如果buckets满了(超过load factor*current capacity)，就内部resize。

如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD)，就把链表转换成红黑树；

图6 entry for tree bin