HashMap源码阅读（上）
1.HashMap数据结构简介
HashMap就是数据结构中的散列表，是以key、value的形式进行存储数据的。数组具有查找定位快，但是插入操作性能差的特点；链表具有查找慢插入快的特点，而HashMap可以说是这两种方式的一种折中。
HashMap采用数组与链表相结合的方式实现，其数据结构示意图如下图所示：
HashMap的特点
- 可以存储null值（HashMap可以接受为null的键或值）
- 非线程安全
- 存储查找速度快
HashMap的性能
影响HashMap性能的因素：
- 哈希函数均匀：HashMap是通过hash函数来定位数组下标，进而确定对象存储位置的，最坏的情况是通过hash函数计算出的下标都为相同，那么HashMap就退化成链表了，最好的情况是都不相同那么就能达到O(1)的效率，所以hash计算出来冲突产生越多，那么查找效率就越低。冲突越少查找效率越高。
- 处理冲突的方法：既要有较高的查找性能，又要有较高的插入性能，那么冲突就无法避免，解决冲突的方式也决定了其性能的优劣。
2.HashMap具体实现
从key到数组的下标
- 首先根据key调用hashCode()方法生成hashCode
- 调用hash()方法根据生成的hashCode生成hash值
- 利用hash值与数组table的length - 1求余得到数组下标（为了使得到的数组在数组区间内）
hash()
1 2 3 4
| static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
|
这段代码叫扰动函数，大家都知道上面代码中的key.hashCode()函数调用的是key键值类型自带的哈希函数，返回int型散列值。
理论上散列值是一个int型，如果直接拿散列值作为下标访问HashMap主数组的话，考虑到带符号的int表值范围前后加起来大概40亿的映射空间，只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。
但问题是一个40亿长度的数组，内存是放不下的。HashMap扩容之前的数组初始大小才16，所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算，得到的余数才能用来访问数组下标。源码中模运算是在类似indexFor()函数里这样完成的：
1 2 3 4 5
| bucketIndex = indexFor(hash, table.length); static int indexFor(int h, int length) { return h & (length-1); }
|
这正好解释了为什么HashMap的数组长度要取2的整次幂，因为这样（数组长度 - 1）正好相当于一个“低位掩码”，“与”操作的结果就是散列值得高位全部归零，只保留低位值，用来做下标访问。以初始长度为16示例，16 - 1 = 15，2进制表示就是00000000 00000000 00001111。和某散列值做“与”操作如下，结果就是截取了最低的四位值。
1 2 3 4
| 10100101 11000100 00100101 & 00000000 00000000 00001111 ---------------------------------- 00000000 00000000 00000101 //高位全部归零，只保留末四位
|
但这时候问题就来了，就算散列值分布再分散，要是只取最后几位的话，碰撞也会很严重，更要命的是如果散列本身做得不好，分布上成等差数列的漏洞，恰好使最后几个低位呈现规律性重复，就会造成很严重的后果。
这时候“扰动函数”的价值就体现出来了，如下图：
右位移16位，正好是32bit的一半，自己的高半区和低半区做异或，就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性。而且混合后的低位参杂了高位的部分特征，这样高位的信息也被变相保留下来。
参考：
JDK 源码中 HashMap 的 hash 方法原理是什么？
数组大小
这里涉及到一个非常有趣且niubi的函数tableSizeFor()，其源码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13
| static final int MAXIMUM_CAPASITY = 1 << 30; * Returns a power of two size for the given target capacity. */ static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }
|
这个方法被调用的地方：
1 2 3 4 5
| public HashMap(int initialCapacity, float loadFactor) { this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); }
|
上面的方法就是数组大小生成的方法，永远生成的是一个2的幂的数，也就是说例如输入15，返回的结果就是16。
为什么这个方法总能在给定一个值之后返回一个大于它同时最接近它或者等于它的2次幂呢？
首先看下下面这段二进制数据：
1 2 3 4 5
| 2的0次方2进制 0000 0001 十进制 1 2的1次方2进制 0000 0010 十进制 2 2的2次方2进制 0000 0100 十进制 4 2的3次方2进制 0000 1000 十进制 8 2的4次方2进制 0001 0000 十进制 16
|
我们发现临近的两个2的幂的高位是相邻的。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| 例如7要取到8 所以将 0000 0111 无符号右移 0000 0111 >>>1 等于 0000 0011 进行与操作 （只要存在1那么是1） 0000 0111 | 0000 0011 等于 0000 0111 n + 1（源码三目运算符） 0000 0111 + 0000 0001=0000 1000 给定数字为4最后通过右移变成8 0000 0100 无符号右移1 0000 0100 >>>1 等于 0000 0010 进行与操作 （只要存在1那么是1） 0000 0100 | 0000 0010 等于 0000 0110 接着因为已经有2位达到变成1的目的，所以接着就是移动2位 0000 0110 >>> 0000 0011 进行与操作 （只要存在1那么是1） 0000 0110 | 0000 0011 等于 0000 0111 n + 1（源码三目运算符） 0000 0111 + 0000 1000 =8
|
借助两个2的幂之间的高位是相邻的的方式。然后通过无符号右移使得给定的数高位以后全变成1这样最后进行n+1就获取到了最小大于它的2的幂。
至于源码为什么到了16就不操作了，是因为int类型是占4个字节，每个字节8位，共32位。而向右移动16位后，可以从高位第一个出现1的位置开始向右连续32位为1，已经超越了int的最大值，所以不用在进行位移操作了，这也是代码中只是移动16位后就结束的原因。
注意：得到的这个capacity却被赋值给了threshold：
1
| this.threshold = tableSizeFor(initialCapacity);
|
按理说，应该这么写：
1
| this.threshold = tableSizeFor(initialCapacity) * this.loadFactor;
|
但是，请注意，在构造方法中，并没有对table这个成员变量进行初始化，table的初始化被推迟到了put方法中，在put方法中会对threshold进行重新运算。
HashMap是怎么进行扩容的
扩容（resize）就是重新计算容量，向HashMap对象里不停的添加元素，而HashMap对象内部的数组无法转载更多的元素时，对象就需要扩大数组的长度，以便能装入更多的元素。当然Java里的数组是无法自动扩容的，方法是使用一个新的数组代替已有的容量小的数组，就像我们用一个小桶装水，如果想装更多的水，就得换大水桶。
resize()
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84
| final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; } else if (oldThr > 0) newCap = oldThr; else { newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }
|
经过观测可以发现，我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。看下图可以明白这句话的意思，n为table的长度，图（a）表示扩容前的key1和key2两种key确定索引位置的示例，图（b）表示扩容后key1和key2两种key确定索引位置的示例，其中hash1是key1对应的哈希与高位运算结果。
元素重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit（红色），因此新的index就会发生这样的变化：
因此，我们在扩充HashMap的时候，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”，可以看看下图为16扩充为32的resize示意图：
参考：resize()函数解析
HashMap中的内部类
Node类：每个node都含有hash、key、value、next等成员变量
- hash：key的hash值
- key、value：node的键和值
- next：node的下一个node，在产生冲突的时候next才有值
注意Node类重写了equals()和hashCode()方法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
| static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key + "=" + value; } public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } }
|
Node中存储了key的hash值，键值对，同时还有下一个链表元素。我们重点关注一些equals这个方法，这个方法在什么时候会用到呢？当我们算出的key的hash值相同时，put方法并不会报错，而是继续向这个hash值的链表中添加元素。我们会调用equals方法来比对key和value是否相同，如果equals方法返回false，会继续向链表的尾部添加一个键值对。
未完待续…
接下来将会就put和get方法展开源码的阅读…