文章导航

HashMap源码学习：红黑树原理详解
HashMap源码学习：JDK1.8版本源码解析

目录

• 文章导航
• 前言
• 正文
• • HashMap重要属性
  • HashMap构造方法
  • HashMap扩容方法
  • HashMap链表迁移
  • HashMap红黑树迁移
  • HashMap链表转红黑树
  • HashMap红黑树转链表
  • HashMap添加数据
  • HashMap移除数据
  • HashMap查询数据
  • HashMap更新数据
• 总结

前言

上篇文章讲解了JDK1.8中HashMap红黑树的原理，以及节点插入、节点移除、红黑树平衡等代码流程，本篇文章对HashMap源码重点进行讲解。

正文

HashMap重要属性

		//hash桶的初始容量,默认是16.当超过阈值时会进行2倍扩容static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16//最大hash桶容量，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;//链化阈值，默认节点数小于等于8时，红黑树转链表static final int UNTREEIFY_THRESHOLD = 6;//最小数化阈值，hash桶数必须大于等于64才能进行转红黑树static final int MIN_TREEIFY_CAPACITY = 64;//扩容阈值，threshold（阈值）=capacity（hash桶长度）*factor（加载因子）int threshold;//加载因子int loadFactor;

HashMap构造方法

		//使用无参构造器实例化时，此时的加载因子为默认值0.75，由于未计算值，此时扩容阈值threshold为0，此时hash桶还未被创建，此时为nullpublic HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}//自定义hash桶容量public HashMap(int initialCapacity) {//调用第三个构造器this(initialCapacity, DEFAULT_LOAD_FACTOR);}//自定义hash桶容量何加载因子值public HashMap(int initialCapacity, float loadFactor) {if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);//当hash桶容量超过最大值，赋予最大默认值                                       if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +loadFactor);this.loadFactor = loadFactor;//计算阈值大小,这里会计算出最接近2的整数幂值  如传入17，则会算出32；传入15，则会算出16；this.threshold = tableSizeFor(initialCapacity);}

这里先介绍构造器的原因是在扩容的时候，有好几种场景，如果先看构造器就会比较清晰。

HashMap扩容方法

final Node[] resize() {//获取旧hash桶Node[] oldTab = table;//获取旧hash桶的容量，当第一次调用put方法时，此时旧hash桶为null，因为我们在构造函数中并没有看见hash桶的初始化int oldCap = (oldTab == null) ? 0 : oldTab.length;//获取旧扩容阈值，如果是调用有参构造器时，这里一定是有值的，否则为0；int oldThr = threshold;int newCap, newThr = 0;//旧hash桶容量不为空，证明是需要扩容if (oldCap > 0) {//如果之前的hash桶容量大于最大值时，则赋予最大默认值并返回if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}//将hash桶进行扩容*2，并且判断是否处于默认值与最大默认值直接，满足条件时，对旧扩容阈值进行2倍扩容else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}//能进入这个逻辑，证明旧的hash桶容量为0，即还未初始化中，此时如果是调用了有参构造器时，此时的旧扩容阈值是有值的，此时将新的hash桶容量大小=旧扩容阈值   标记：（1）else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;else {               // zero initial threshold signifies using defaults//进入到这里，证明之前是调用了无参构造器，所以旧扩容阈值和hash桶容量才为0，此时赋予默认值newCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}//进入这个逻辑证明之前是进入了 标记：（1）中的代码逻辑。此时重新计算新的扩容阈值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"})//创建一个新的hash桶，此时的hash桶容量就是前面计算好的新容量大小。此时的hash桶是一个空的，需要将旧值迁移至此。Node[] newTab = (Node[])new Node[newCap];table = newTab;if (oldTab != null) {//遍历旧hash桶for (int j = 0; j < oldCap; ++j) {Node e;//获取hash桶中第一个节点，根据第一个节点去关联其它链表节点或红黑树节点。将节点赋值给eif ((e = oldTab[j]) != null) {//移除旧hash桶中该下标的节点oldTab[j] = null;//如果第一个节点关联的下个节点为空，证明只有一个节点，此时重新计算在新Hash桶中的位置进行存放if (e.next == null)newTab[e.hash & (newCap - 1)] = e;else if (e instanceof TreeNode)//如果是红黑树((TreeNode)e).split(this, newTab, j, oldCap);else { // preserve order//链表的迁移过程，见下文图解Node loHead = null, loTail = null;Node hiHead = null, hiTail = null;Node next;//loHead ：第一个节点，用于存放e.hash & oldCap=0情况的节点//loHead ：最后一个节点，用于存放e.hash & oldCap=0情况的节点//hiHead ：第一个节点，用于存放e.hash & oldCap！=0情况的节点//hiTail ：最后一个节点，用于存放e.hash & oldCap！=0情况的节点//next：存放遍历当前节点的下一个节点do {next = e.next;if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.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;}

HashMap链表迁移

有读者可能对于链表的迁移过程不太理解，这边通过画图形式帮助理解。

对于(e.hash & oldCap) == 0）的情况：
因为容量是2的整数幂，所以高位第一位为1，后面都是0；由于两者进行&运算后的结果为0 ，所以其与容量高位为1对应的hash位数一定是0，如上图中oldCap=16，e.hash的第5位一定为0，这样才能保证其&运算结果为0的情形。故我们可以推断出进入该代码逻辑的e.hash从右到左第5位为0，hash桶下标计算只受hash的后4位影响。

newCap新hash桶容量又是旧hash桶容量的两倍，所以在二进制中新hash桶容量比旧hash桶容量多一位。

下标计算公式：e.hash&hash桶容量值-1

综上所述，我们可以总结出对于(e.hash & oldCap) == 0）的情况，节点在新旧hash桶中的位置是一样的。

对于(e.hash & oldCap) ！= 0）的情况：

由于(e.hash & oldCap) ！= 0），所以我们可以得出二进制中与旧hash桶容量高位对应的hash一定是1，这样才能保证&运算后的结果不为0；根据上图案例，我们可以推断出进入该条件的节点hash值第5位一定是1；

newCap新hash桶容量又是旧hash桶容量的两倍，所以在二进制中新hash桶容量比旧hash桶容量多一位。

下标计算公式：e.hash&hash桶容量值-1

十进制：oldCap(16)， oldCap-1(15)， newCap=2oldCap=(32)， newCap-1=(31)
二进制：oldCap(10000)， oldCap-1(01111)， newCap=2oldCap=(100000)， newCap-1=(011111)

从上图中，我们可以看出新hash桶计算出来的下标恰好比旧hash桶下标多出一位，且多出的高位为1；
最终我们得出结论：对于(e.hash & oldCap) ！= 0）的情况，新hash桶的下标=旧hash桶下标+旧hash桶的容量

HashMap红黑树迁移

红黑树迁移到新hash桶下标的计算与上文链表迁移的计算方式一致；

final void split(HashMap map, Node[] tab, int index, int bit) {//当前hash桶所在下标的第一个节点TreeNode b = this;// Relink into lo and hi lists, preserving orderTreeNode loHead = null, loTail = null;TreeNode hiHead = null, hiTail = null;//loHead ：第一个节点，用于存放e.hash & oldCap=0情况的节点//loHead ：最后一个节点，用于存放e.hash & oldCap=0情况的节点//hiHead ：第一个节点，用于存放e.hash & oldCap！=0情况的节点//hiTail ：最后一个节点，用于存放e.hash & oldCap！=0情况的节点  //统计两种情况的数量int lc = 0, hc = 0;//先使用链表的方式，将同个下标中的节点串起来，后面再进行红黑树转换for (TreeNode e = b, next; e != null; e = next) {next = (TreeNode)e.next;e.next = null;if ((e.hash & bit) == 0) {if ((e.prev = loTail) == null)loHead = e;elseloTail.next = e;loTail = e;++lc;}else {if ((e.prev = hiTail) == null)hiHead = e;elsehiTail.next = e;hiTail = e;++hc;}}if (loHead != null) {//如果分割后节点数小于等于6，则进行链表化if (lc <= UNTREEIFY_THRESHOLD)tab[index] = loHead.untreeify(map);else {tab[index] = loHead;//hiHead 和 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);}}}

上面方法操作的是红黑树，有读者可能有疑问，既然操作的是红黑树这么还有next属性。引入这些属性是方便树化和链化的转换。可以看下红黑树节点的属性结构：

    static final class TreeNode extends LinkedHashMap.Entry {TreeNode parent;  // 红黑树的父节点TreeNode left;		// 红黑树的左节点TreeNode right;	// 红黑树的右节点TreeNode prev;    // 指向链表的上个节点boolean red;

以上代码我们并没用看到next属性，但是可以看到其继承了LinkedHashMap…Entry父类，而LinkedHashMap…Entry继承了Node，所以红黑树也就拥有了next属性。

HashMap链表转红黑树

对于红黑树不熟悉的，可参考上篇文章《HashMap源码学习：红黑树原理详解》

        final void treeify(Node[] tab) {TreeNode root = null;for (TreeNode x = this, next; x != null; x = next) {//获取当前节点的下一个节点next = (TreeNode)x.next;x.left = x.right = null;//如果当前红黑树根节点为空时，将其作为根节点，并且将颜色置为黑色if (root == null) {x.parent = null;x.red = false;root = x;}else {//获取插入节点key值K k = x.key;//获取插入节点hash值int h = x.hash;Class kc = null;//从跟节点开始遍历for (TreeNode p = root;;) {int dir, ph;//dir：标记下个节点的方向//ph：当前节点的Hash值//pk：当前节点的key值K pk = p.key;//如果当前插入节点hash值小于当前节点的hash值，则下次查找应该是向左查找if ((ph = p.hash) > h)dir = -1;//如果当前插入节点hash值大于当前节点的hash值，则下次查找应该是向右查找else if (ph < h)dir = 1;//这里去获取key是否实现一些比较器，有则使用比较器来获取下次查询的方向else if ((kc == null &&(kc = comparableClassFor(k)) == null) ||(dir = compareComparables(kc, k, pk)) == 0)//尝试使用jdk自带的hash工具进行比较dir = tieBreakOrder(k, pk);//将红黑树当前所在节点赋值给xpTreeNode xp = p;//将p赋值为下个节点，如果下个节点为null，证明是找到插入位置了if ((p = (dir <= 0) ? p.left : p.right) == null) {//将插入节点的父亲指向xpx.parent = xp;//这里根据方向决定是插入左边还是右边if (dir <= 0)xp.left = x;elsexp.right = x;//插入之后，可能会破坏红黑树的特性，需要进行平衡操作，如变色、左旋、右旋。可参考上篇文章root = balanceInsertion(root, x);break;}}}}//保持根节点位于hash桶中所在下标的第一个节点moveRootToFront(tab, root);}

HashMap红黑树转链表

        final Node untreeify(HashMap map) {Node hd = null, tl = null;for (Node q = this; q != null; q = q.next) {//创建新的节点Node p = map.replacementNode(q, null);//tl为空，证明是第一次遍历时if (tl == null)//将当前新节点设置为头节点hd = p;elsetl.next = p;tl = p;}return hd;}

HashMap添加数据

    public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}

   final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node[] tab; Node p; int n, i;//如果hash桶为null或者长度为0，这时候需要调用resize方法进行初始化。if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;//计算插入节点在hash桶中的下标，该下标如果为空，则直接存入if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {//e用来保存存在相同hash值跟key值的节点，后面会进行值覆盖Node e; K k;//如果当前hash桶所在下标有值，其hash值跟key值与插入节点一致，则将值赋值给e,在后面的步骤会进行值覆盖if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;else if (p instanceof TreeNode)//插入节点是一个红黑树节点，此处返回的e不为空，证明存在相同key值跟hash值的情况。该方法在上篇文章中已进行讲解e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);else {//这里一直遍历获取下个节点，判断是否存在相同key值跟hash值的情况，有则赋值给e至后面覆盖；如果下个节点为空，则进行插入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 1sttreeifyBin(tab, hash);break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}//如果e不为空，则已存在该相同key情况的节点，需要将value值赋予新值if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;//值覆盖完成后进行回调。该方法为拓展方法，留于子类进行拓展实现；HashMap中没有进行代码实现。afterNodeAccess(e);return oldValue;}}++modCount;//如果当前hash桶存储容量大于阈值时，进行扩容if (++size > threshold)resize();//该方法为拓展方法，留于子类进行拓展实现；HashMap中没有进行代码实现。afterNodeInsertion(evict);return null;}

HashMap移除数据

    public boolean remove(Object key, Object value) {return removeNode(hash(key), key, value, true, true) != null;}

final Node removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable) {Node[] tab; Node p; int n, index;//如果hash桶为null、数量为0、计算后hash桶所在下标为null时，证明没数据存在。直接返回nullif ((tab = table) != null && (n = tab.length) > 0 &&(p = tab[index = (n - 1) & hash]) != null) {Node node = null, e; K k; V v;//如果其hash值、key值一致，则是查找到了，将其赋值给node,后面代码中会进行移除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)p).getTreeNode(hash, key);else {//一致遍历查找，直到最后一个值，看是否查询到，查询到则赋值给nodedo {if (e.hash == hash &&((k = e.key) == key ||(key != null && key.equals(k)))) {node = e;break;}p = e;} while ((e = e.next) != null);}}//如果找到了位置，还需要比较移除值是否一样（取决于开关：matchValue 值）。if (node != null && (!matchValue || (v = node.value) == value ||(value != null && value.equals(v)))) {if (node instanceof TreeNode)((TreeNode)node).removeTreeNode(this, tab, movable);else if (node == p)//如果移除节点是处于hash桶下标第一个时，将hash桶下标中的值移动到移除节点的下一个值tab[index] = node.next;else//将上个节点的next指向移除节点的next节点p.next = node.next;++modCount;--size;//回调函数，留于子类进行实现afterNodeRemoval(node);return node;}}return null;}

HashMap查询数据

    public V get(Object key) {Node e;return (e = getNode(hash(key), key)) == null ? null : e.value;}

    final Node getNode(int hash, Object key) {Node[] tab; Node first, e; int n; K k;//如果hash桶为null、数量为0、计算后hash桶所在下标为null时，证明没数据存在。直接返回nullif ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {//如果第一个节点的key跟hash值一致则返回if (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k))))return first;if ((e = first.next) != null) {//如果是红黑树，则调用红黑树方法查找if (first instanceof TreeNode)return ((TreeNode)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;}

HashMap更新数据

    @Overridepublic V replace(K key, V value) {Node e;if ((e = getNode(hash(key), key)) != null) {V oldValue = e.value;e.value = value;afterNodeAccess(e);return oldValue;}return null;}

总结

看完HashMap源码可以看到其设计很巧妙，尤其是下标计算、新旧Hash桶的迁移。
旧Hash桶迁移到新Hash桶时，其下标只有两种情况；一种是新旧位置一样的情形，一种是新Hash桶位置=旧Hash桶容量长度+旧Hash桶所在下标；