集合源码-HashMap

1、简介

HashMap采用key/value存储结构，底层基于散列算法实现，HashMap 允许 null 键和 null 值，它是非线程安全的，且不保证元素存储的顺序，在计算哈键的哈希值时，null 键哈希值为 0。

2、继承体系

实现了Cloneable，可以被克隆。实现了Serializable，可以被序列化。实现了Map接口，具有Map的所有功能。

3、存储结构

在jdk1.8 中，HashMap的实现采用了数组 + 链表 + 红黑树的结构；在添加元素时，先根据hash值算出元素在数组中的位置，如果该位置没有元素，则直接把元素放置在此处，如果该位置有元素了，则把元素以链表的形式放置在链表的尾部。

当一个链表的元素个数达到一定的数量（且数组的长度达到一定的长度）后，则把链表转化为红黑树，从而提高效率；数组的查询效率为O(1)，链表的查询效率是O(k)，红黑树的查询效率是O(log k)，k为桶中的元素个数。

4、源码分析

4.1 属性

// 默认初始化大小16 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 最大容量为2^30 static final int MAXIMUM_CAPACITY = 1 << 30; // 默认扩展因子0.75 static final float DEFAULT_LOAD_FACTOR = 0.75f; // 当一个桶中的元素个数大于等于8时进行树化 static final int TREEIFY_THRESHOLD = 8; // 当一个桶中的元素个数小于等于6时把树转化为链表 static final int UNTREEIFY_THRESHOLD = 6; // 当桶的个数达到64的时候才进行树化 static final int MIN_TREEIFY_CAPACITY = 64; // 数组，又叫作桶（bucket），不进行序列化 // table 多数情况下是无法被存满的，序列化未使用的部分，浪费空间 // 同一个键值对在不同 JVM 下，所处的桶位置可能是不同的，在不同的JVM下反序列化table可能会发生错误 transient Node<K,V>[] table; // 作为entrySet()的缓存 transient Set<Map.Entry<K,V>> entrySet; // 元素的数量 transient int size; // 修改次数，用于在迭代的时候执行快速失败策略 transient int modCount; // 当桶的使用数量达到多少时进行扩容,threshold = capacity * loadFactor int threshold; // 装载因子 final float loadFactor;

4.2 关键内部类

// Node是一个典型的单链表节点，其中，hash用来存储key计算得来的hash值 static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; } // 红黑树节点 static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; // red-black tree links TreeNode<K,V> left; TreeNode<K,V> right; TreeNode<K,V> prev; // needed to unlink next upon deletion boolean red; } // LinkedHashMap.Entry static class Entry<K,V> extends HashMap.Node<K,V> { Entry<K,V> before, after; Entry(int hash, K key, V value, Node<K,V> next) { super(hash, key, value, next); } }

4.3 构造函数

// 默认构造函数 public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; } // 设置容量大小 public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } // 设置容量大小与扩展因子 public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; // 检查装载因子是否合法 if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; // 计算扩容上限 this.threshold = tableSizeFor(initialCapacity); } public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); } 注意： 初始阈值 threshold: 一般情况下，都会使用无参构造方法创建 HashMap。但当我们对时间和空间复杂度有要求的时候，使用默认值有时可能达不到我们的要求，这个时候我们就需要手动调参。在 HashMap 构造方法中，可供我们调整的参数有两个，一个是初始容量 initialCapacity，另一个负载因子 loadFactor。通过这两个设定这两个参数，可以进一步影响阈值大小。但初始阈值 threshold 仅由 initialCapacity 经过移位操作计算得出。 负载因子（loadFactor）: 对于 HashMap 来说，负载因子是一个很重要的参数，该参数反应了 HashMap 桶数组的使用情况（假设键值对节点均匀分布在桶数组中）。通过调节负载因子，可使 HashMap 时间和空间复杂度上有不同的表现。当我们调低负载因子时，HashMap 所能容纳的键值对数量变少。扩容时，重新将键值对存储新的桶数组里，键的键之间产生的碰撞会下降，链表长度变短。此时，HashMap 的增删改查等操作的效率将会变高，这里是典型的拿空间换时间。相反，如果增加负载因子（负载因子可以大于1），HashMap 所能容纳的键值对数量变多，空间利用率高，但碰撞率也高。这意味着链表长度变长，效率也随之降低，这种情况是拿时间换空间。至于负载因子怎么调节，这个看使用场景了。一般情况下，我们用默认值就可以了。 // 找到大于或等于 cap 的最小2的幂 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; // n小于0 取MAXIMUM_CAPACITY；n大于等于0时，如果小于MAXIMUM_CAPACITY，取n+1 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }

4.4 插入元素

public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } // 计算key的hash static final int hash(Object key) { int h; // 为空时hash=0 // 并让高16位与整个hash异或，这样做是为了使计算出的hash更分散 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; // 初始化桶数组 table，table 被延迟到插入新数据时再进行初始化 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 桶中对应位置不存在，直接放入 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; // 如果桶中第一个元素的key与待插入元素的key相同，保存到e中用于后续修改value值 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 如果桶中的引用类型为 TreeNode，则调用红黑树的插入方法 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { // binCount计算链表长度 for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { // 尾插入 p.next = newNode(hash, key, value, null); // 大于阈值8时进行树化 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } // 如果待插入的key在链表中找到了，则退出循环 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; // 指向下一个节点 p = e; } } // 判断要插入的键值对是否存在 HashMap 中 if (e != null) { V oldValue = e.value; // 存在时进行value覆盖旧值 if (!onlyIfAbsent || oldValue == null) e.value = value; // LinkedHashMap回调 afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); // LinkedHashMap回调 afterNodeInsertion(evict); return null; }

流程： 1）当桶数组 table 为空时，通过扩容的方式初始化 table 2）查找要插入的键值对是否已经存在，存在的话根据条件判断是否用新值替换旧值 3）如果不存在，则将键值对链入链表中，并根据链表长度决定是否将链表转为红黑树 4）判断键值对数量是否大于阈值，大于的话则进行扩容操作

扩容机制 final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; // 桶数组 table 已经被初始化 if (oldCap > 0) { // 大于最大容量时，阈值也设置为最大值 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } // 否则容量与阈值均扩大为2倍 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } // threshold > 0，且桶数组未被初始化 // 调用 HashMap(int) 和 HashMap(int, float) 构造方法时会产生这种情况 else if (oldThr > 0) // initial capacity was placed in threshold // 如果旧容量为0且旧扩容门槛大于0，则把新容量赋值为旧门槛 newCap = oldThr; // 调用 HashMap() 构造方法会产生这种情况 // 桶数组未被初始化，且 threshold 为 0 else { // 阈值为默认容量与默认负载因子乘积 newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // 第一个条件分支未计算 newThr 或嵌套分支在计算过程中导致 newThr 溢出归零 if (newThr == 0) { // 如果新扩容门槛为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 { // 遍历链表，并将链表节点按原顺序进行分组 // 则分化成两个链表插入到新的桶中去 // 1种在原链，1种在新链（高于当前index） Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; // (e.hash & oldCap) == 0的元素放在低位链表中 // 比如，3 & 4 == 0 if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } // (e.hash & oldCap) != 0的元素放在高位链表中 // 比如，7 & 4 != 0 else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); // 遍历完成分化成两个链表了 // 低位链表在新桶中的位置与旧桶一样（即3和11还在三号桶中） if (loTail != null) { loTail.next = null; newTab[j] = loHead; } // 高位链表在新桶中的位置正好是原来的位置加上旧容量 if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }

流程： 1) 计算新桶数组的容量 newCap 和新阈值 newThr 2) 根据计算出的 newCap 创建新的桶数组，桶数组 table 也是在这里进行初始化的 3) 将键值对节点重新映射到新的桶数组里。如果节点是 TreeNode 类型，则需要拆分红黑树。如果是普通节点，则节点按原顺序进行分组。

红黑树 final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; // 桶数组容量小于 MIN_TREEIFY_CAPACITY，优先进行扩容而不是树化 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); else if ((e = tab[index = (n - 1) & hash]) != null) { TreeNode<K,V> hd = null, tl = null; do { TreeNode<K,V> p = replacementTreeNode(e, null); if (tl == null) hd = p; else { p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) != null); if ((tab[index] = hd) != null) // 将树形链表转换成红黑树 hd.treeify(tab); } } // 将普通节点替换成树形节点 TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) { return new TreeNode<>(p.hash, p.key, p.value, next); }

在扩容过程中，树化要满足两个条件： 1) 链表长度大于等于 TREEIFY_THRESHOLD 2) 桶数组容量大于等于 MIN_TREEIFY_CAPACITY

由于树化过程需要比较两个键对象的大小，在键类没有实现 comparable 接口的情况下，怎么比较键与键之间的大小了就成了一个棘手的问题。为了解决这个问题，HashMap 是做了三步处理，确保可以比较出两个键的大小，如下： 1) 比较键与键之间 hash 的大小，如果 hash 相同，继续往下比较 2) 检测键类是否实现了 Comparable 接口，如果实现调用 compareTo 方法进行比较 3) 如果仍未比较出大小，就需要进行仲裁了，仲裁方法为 tieBreakOrder 链表转成红黑树后，原链表的顺序仍然会被引用仍被保留了，我们仍然可以按遍历链表的方式去遍历上面的红黑树。

红黑树扩容重映射 扩容后，普通节点需要重新映射，红黑树节点也不例外。按照一般的思路，我们可以先把红黑树转成链表，之后再重新映射链表即可。这种处理方式是大家比较容易想到的，但这样做会损失一定的效率。不同于上面的处理方式，HashMap 实现的思路则是上好佳（上好佳请把广告费打给我）。如上节所说，在将普通链表转成红黑树时，HashMap 通过两个额外的引用 next 和 prev 保留了原链表的节点顺序。这样再对红黑树进行重新映射时，完全可以按照映射链表的方式进行。这样就避免了将红黑树转成链表后再进行映射，无形中提高了效率。 final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) { TreeNode<K,V> b = this; // Relink into lo and hi lists, preserving order TreeNode<K,V> loHead = null, loTail = null; TreeNode<K,V> hiHead = null, hiTail = null; int lc = 0, hc = 0; // 红黑树节点仍然保留了 next 引用，故仍可以按链表方式遍历红黑树 for (TreeNode<K,V> e = b, next; e != null; e = next) { next = (TreeNode<K,V>)e.next; e.next = null; if ((e.hash & bit) == 0) { if ((e.prev = loTail) == null) loHead = e; else loTail.next = e; loTail = e; ++lc; } else { if ((e.prev = hiTail) == null) hiHead = e; else hiTail.next = e; hiTail = e; ++hc; } } if (loHead != null) { if (lc <= UNTREEIFY_THRESHOLD) tab[index] = loHead.untreeify(map); else { tab[index] = loHead; if (hiHead != null) // (else is already treeified) loHead.treeify(tab); } } if (hiHead != null) { if (hc <= UNTREEIFY_THRESHOLD) tab[index + bit] = hiHead.untreeify(map); else { tab[index + bit] = hiHead; if (loHead != null) hiHead.treeify(tab); } } } 红黑树链化 final Node<K,V> untreeify(HashMap<K,V> map) { Node<K,V> hd = null, tl = null; // 遍历 TreeNode 链表，并用 Node 替换 for (Node<K,V> q = this; q != null; q = q.next) { Node<K,V> p = map.replacementNode(q, null); if (tl == null) hd = p; else tl.next = p; tl = p; } return hd; } Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) { return new Node<>(p.hash, p.key, p.value, next); }

4.5 删除元素

public V remove(Object key) { Node<K,V> e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; } final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { Node<K,V>[] tab; Node<K,V> p; int n, index; if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) { Node<K,V> node = null, e; K k; V v; // 等于首个节点 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) node = p; else if ((e = p.next) != null) { // 在树中 if (p instanceof TreeNode) node = ((TreeNode<K,V>)p).getTreeNode(hash, key); else { // 链表中节点 do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { node = e; break; } p = e; } while ((e = e.next) != null); } } if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) { if (node instanceof TreeNode) // 在树中移除 ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable); else if (node == p) // 首节点移除 tab[index] = node.next; else // 链表中移除 p.next = node.next; ++modCount; --size; afterNodeRemoval(node); return node; } } return null; }