为了能够快速存取，HashMap的底层是由数组来实现的，根据 Key 的 Hash 值来计算数组下标index，可是不同Key的hash值可能会相同，意味着hash冲突，那么此时就通过链表（java8中，如果链表长度超过8，则把链表转换为红黑树）来维护hash冲突的元素，链表中冲突的元素通过 Key 的equal()方法来确定。
所以，HashMap底层是由多个结构组合实现的。本文主要从这四方面来进行剖析：** put 操作 、 get 操作 、 hash的实现 、 resize的流程 **。
put 操作
put 的大致过程为：
1、对key的hashCode()做hash，然后再计算index;
2、如果没碰撞直接放到bucket里；
3、如果碰撞了，以链表的形式存在buckets里；
4、如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD，默认为8)，就把链表转换成红黑树；
5、如果节点已经存在就替换old value(保证key的唯一性)；
6、如果bucket满了(超过load factor * current capacity)，就进行resize。
来看具体代码：
public V put(K key, V value) {
// 取关键字key的哈希值
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// ((n - 1) & hash)作为key在tab[]数组中的下标，
if ((p = tab[i = (n - 1) & hash]) == null)
// 如果该下标下没有节点，则直接新建一个Node放在该位置。
tab[i] = newNode(hash, key, value, null);
else { // 如果哈希表当前位置上已经有节点的话，说明有hash冲突
Node<K,V> e; K k;
// hash和key都相等，则该Key已存在，获得该节点。
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)// 该链为树，用红黑树的方式进行处理
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {// 该链为链表
for (int binCount = 0; ; ++binCount) {// 遍历链表
if ((e = p.next) == null) {// 如果为空，构造链表上的新节点
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// hash和key都相等，则该Key已存在，获得该节点并break。
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 如果找到了节点，说明关键字相同，进行覆盖操作，直接返回旧的关键字的值
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 如果目前键值对个数已经超过阀值，重新构建
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
get 操作
get 的大致过程为：
1、对key的hashCode()做hash，然后再计算index;
2、如果该 index 下没有值，则直接返回 null；
3、index 下有值，判断 table 数组中该下标处第一个节点是否命中，命中则直接返回；
3、未命中，则判断去树结构中查找，或者去链表结构中查找，找到则返回。
来看具体代码：
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 如果哈希表容量为0或者关键字没有命中，直接返回null
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 通过hash和key判断是否为第一个节点
if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode) // 以红黑树的方式查找
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do { // 遍历链表查找
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
hash的实现
在设计hash函数时，因为目前的table长度n为2的幂，而计算下标的时候，是这样实现的(使用 & 位操作，而非 % 求余)：
// index的计算方式
(n - 1) & hash
设计者认为这方法很容易发生碰撞。为什么这么说呢？不妨思考一下，在n - 1为15(0x1111)时，其实散列真正生效的只是低4bit的有效位，当然容易碰撞了。
因此，设计者想了一个顾全大局的方法(综合考虑了速度、作用、质量)，就是把高16bit和低16bit异或了一下。设计者还解释到因为现在大多数的hashCode的分布已经很不错了，就算是发生了碰撞也用O(logn)的tree去做了。仅仅异或一下，既减少了系统的开销，也不会造成的因为高位没有参与下标的计算(table长度比较小时)，从而引起的碰撞。
static final int hash(Object key) {
int h;
// 使用（hashCode的值）以及（hashCode的值无符号右移16位）做异或操作
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
我们来看一下这个过程：
如果还是产生了频繁的碰撞，会发生什么问题呢？之前的jdk中，在获取HashMap的元素时，基本分两步：
1、首先根据hashCode()做hash，然后根据hash确定bucket的index；
2、如果bucket的节点的key不是我们需要的（也就是发生了冲突），则通过keys.equals()在链中查找。
在Java 8之前的实现中是用链表解决冲突的，在产生碰撞的情况下，进行get时，两步的时间复杂度是O(1)+O(n)。因此，当碰撞很厉害的时候n很大，O(n)的速度显然是影响速度的。
因此在Java 8中，利用红黑树替换链表，这样复杂度就变成了O(1)+O(logn)了，这样在n很大的时候，能够比较理想的解决这个问题，具体参考Java8：HashMap的性能提升。
resize流程
在put操作时，如果发现目前的bucket占用程度已经超过了Load Factor所希望的比例，那么就会发生resize。resize的过程，简单的说就是把bucket扩充为2倍，之后重新计算index，把节点再放到新的bucket中。
主要流程为：
1、无节点，不处理；
2、单节点，重新计算index（hash & (newCap - 1)）。
3、多节点，跟单节同样的情况，只是没有重新计算所有的index，而是看看原来的hash值新增的那个bit是1还是0（因为容量扩大了一倍，因此影响结果的是hash之前没有参与运算的最右侧位值，通过 hash & oldCap 便能得到），是0的话索引没变，是1的话索引变成“原索引+oldCap”。
下图是容量从8扩容到16的示意图：
这就是为什么扩容为原来的2倍，因为要维持容量大小为2的幂，这样可以快速计算出 index 的值，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，相对均匀地把之前冲突的节点分散到新的bucket里了。
来看具体代码：
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) { // 如果老容量大于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) // 根据thresold初始化数组
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) { // 扩容之后进行rehash操作
Node<K,V> e;
if ((e = oldTab[j]) != null) { // 无节点，不做处理
oldTab[j] = null;
if (e.next == null) // 单节点，重新计算index
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) {
// 第一次 loTail 为空，则 loHead 和 loTail 都指向了e
if (loTail == null)
loHead = e;
else// 然后 loTail 不断向后移动来添加新的e
loTail.next = e;
loTail = e;
}
else { // 原索引+oldCap，方法同上
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 原索引放到bucket里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引+oldCap放到bucket里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
网友评论