HashMap源码分析下

HashMap

环境 JDK11

HashMap是用哈希表结构（链表散列：数组+链表）实现，结合数组和链表的优点。扩容时当链表长度超过 6 时，链表转换为红黑树。

public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {transient Node<K,V>[] table;transient Set<Map.Entry<K,V>> entrySet;transient int size;transient int modCount;// 指定容量，它才会有初始值int threshold;// 一个比例因素，默认0.75，默认这个table数组是不会填满的，达到这个比例因素就会扩容// 除非HashMap存了太多的值，已经满了，这时候table剩下的空间也会被用final float loadFactor;static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16static final int MAXIMUM_CAPACITY = 1 << 30;// 0.75这个跟一个统计学里很重要的原理——泊松分布有关,泊松分布是统计学和概率学常见的离散概率分布，适用于描述单位时间内随机事件发生的次数的概率分布。static final float DEFAULT_LOAD_FACTOR = 0.75f;static final int TREEIFY_THRESHOLD = 8;static final int UNTREEIFY_THRESHOLD = 6;static final int MIN_TREEIFY_CAPACITY = 64;.....
}

构造函数

public HashMap(int initialCapacity, float loadFactor) {....      this.loadFactor = loadFactor;this.threshold = tableSizeFor(initialCapacity);
}public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);
}public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}public HashMap(Map<? extends K, ? extends V> m) {this.loadFactor = DEFAULT_LOAD_FACTOR;putMapEntries(m, false);
}

HashMap.TreeNode

一颗红黑树上的节点，HashMap中红黑树还可以是链表结构

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {TreeNode<K,V> parent;  // red-black tree linksTreeNode<K,V> left;TreeNode<K,V> right;TreeNode<K,V> prev;    // needed to unlink next upon deletionboolean red;TreeNode(int hash, K key, V val, Node<K,V> next) {super(hash, key, val, next);}......
}

root

返回这颗红黑树的根节点

final TreeNode<K,V> root() {for (TreeNode<K,V> r = this, p;;) {if ((p = r.parent) == null)return r;r = p;}
}

Integer::numberOfLeadingZeros

这个函数是在求一个数前面有多少个0。算这个数干什么呢？是为了后面得出一个数，这个数比这个函数的参数大，但是又是2的幂次方。

第一种，简单遍历每一位，直到遇到1

// 轮询bit位
int numberOfLeadingZerors(int x) {int n = 0;for (int i = 31; i >= 0; i--) {if ( x & (1 << i) != 0) {break;}else n++;}return n;
}

这样，最多需要循环32次

第二种，二分法

// 二分搜索计算前导0
int numberOfLeadingZeros(int x) {if (x == 0) return 32;int n = 0;// 判断高16位是否为0：先通过高16位，判断该数是否位于较小的一半，如果是，说明至少会有16个0，再把该数左移16位if (x <= 0x0000FFFF) { n = n + 16; x = x << 16; } // 判断高8位if (x <= 0x00FFFFFF) { n = n + 8; x = x << 8; }   // 判断高4位if (x <= 0x0FFFFFFF) { n = n + 4; x = x << 4; } // 判断高2位if (x <= 0x3FFFFFFF) { n = n + 2; x = x << 2; } // 判断高1位if (x <= 0x7FFFFFFF) { n = n + 1; } return n;
}

// 二分搜索计算前导0，左移版本
int numberOfLeadingZeros(int x) {if (x == 0) return 32;int n = 0;// 判断高16位是否为0：先通过高16位，判断该数是否位于较小的一半，如果是，说明至少会有16个0，再把该数左移16位if ((x & 0xFFFF0000) == 0) { n = n + 16; x = x << 16; } if ((x & 0xFF000000) == 0) { n = n + 8; x = x << 8; }   // 判断高8位if ((x & 0xF0000000) == 0) { n = n + 4; x = x << 4; } // 判断高4位if ((x & 0xC0000000) == 0) { n = n + 2; x = x << 2; } // 判断高2位if ((x & 0x80000000) == 0) { n = n + 1; }  // 判断高1位return n;
}

// 二分搜索计算前导0,右移版本
int numberOfLeadingZeros(int x) {if (x == 0) return 32;int n = 1;if ((x >> 16) == 0) { n = n + 16; x = x << 16; }if ((x >> 24) == 0) { n = n + 8; x = x << 8; } if ((x >> 28) == 0) { n = n + 4; x = x << 4; }if ((x >> 30) == 0) { n = n + 2; x = x << 2; }n = n - (x >> 31);return n;
}

JDK源码

public static int numberOfLeadingZeros(int i) {// HD, Count leading 0'sif (i <= 0)return i == 0 ? 32 : 0;// 大于等于0的数，最多有31个0，最高位要是1就是负数了int n = 31;// i 大于等于 1<<16,说明，i的前导0还在32~16bit位之间，把n减去16，同时i无符号向右移动16位，保留好高16位if (i >= 1 << 16) { n -= 16; i >>>= 16; }// 再继续二分if (i >= 1 <<  8) { n -=  8; i >>>=  8; }if (i >= 1 <<  4) { n -=  4; i >>>=  4; }// if (i >= 1 <<  2) { n -=  2; i >>>=  2; }return n - (i >>> 1);
}

tableSizeFor

/*** Returns a power of two size for the given target capacity.*/
static final int tableSizeFor(int cap) {int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

比如，

cap=1，2的0次方就等于1，返回的是就是4

cap=3，2的2次方就等于4，返回的是就是4

cap=10，2的4次方就等于16，返回的是就是16

所以这个函数就是计算出一个2次方的数，第一个大于等于定数cap

很简单：

比如10 ,它的二进制数：

0000_0000_0000_0000_0000_0000_0000_1010

只要让最前面的那个1向左移动一位，就大于等于这个数，且还是2的幂次方。

0000_0000_0000_0000_0000_0000_0001_0000

那么就要先计算出cap前导0的数量，然后移位就可以算出来

为什么源码中还要cap - 1呢？如果这个cap刚好是2的幂次方呢，即4,8,16,32,64等这样的，这样的数已经满足条件了，再减去1，把数变成3,7,31,63

比如现在把cap=10，它的前导0有28位，-1 >>>28,就变成

0000_0000_0000_0000_0000_0000_0000_1111

再加1，就会进位，变成16

0000_0000_0000_0000_0000_0000_0001_0000

resize

数组空间不够时，重新扩容，扩容都是之前的2倍。

final Node<K,V>[] resize() {// 如果是HashMap刚刚初始化，就进行put，这个table是nullNode<K,V>[] oldTab = table;// 数组之前的容量int oldCap = (oldTab == null) ? 0 : oldTab.length;// 之前的阈值，不会比数组的容量大int oldThr = threshold;// 重新定义新的容量和阈值int newCap, newThr = 0;if (oldCap > 0) {// 之前已经初始化过table，那么oldCap就大于0if (oldCap >= MAXIMUM_CAPACITY) {// 已经是最大值了，不能再扩容了// 也就是说HashMap有最大容量限制 1<<30,// 一般来说table数组是不会被填满的，除非数据太多，已经超过MAXIMUM_CAPACITY，没办法，最后的数组空间也要使用了threshold = Integer.MAX_VALUE;return oldTab;}// 之前的容量还没有超过最大容量，新容量newCap扩大一倍后还比最大容量小else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)// 新容量阈值扩大一倍newThr = oldThr << 1; // double threshold}// 下面两个else处理第一次扩容else if (oldThr > 0) // initial capacity was placed in threshold// oldCap == 0，说明table还没有初始化// 我们给HashMap定义了容量newCap = oldThr;else {               // zero initial threshold signifies using defaults// 如果直接使用new HashMap()，即没有传容量，那么threshold就等于0// 默认容量16newCap = DEFAULT_INITIAL_CAPACITY;// 数组的阈值计算出12newThr = (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)// 元素e后面没有链表，// 重新计算数组中的位置newTab[e.hash & (newCap - 1)] = e;else if (e instanceof TreeNode)// e是红黑树的根节点((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else { // preserve order// e后面有链表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;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;
}

关于e.hash & oldCap：

前提oldCap一定是2的整数次幂。e.hash & (oldCap-1)表示e在数组中的索引位置，oldCap是2的整数次幂，即

我们假设 oldCap = 16

16 - 1 = 15, 二进制表示为 0000_0000_0000_0000_0000_0000_0000_1111

可见除了低4位, 其他位置都是0，则 (16-1) & hash 只会取hash值的低4位。

当我们将oldCap扩大两倍后即32

32 - 1 = 31,二进制表示为 0000_0000_0000_0000_0000_0000_0001_1111， (32-1) & hash 就只会取低5位

假如有一个hash值是0000_0000_0000_0000_0000_0000_0000_1001，那么这个e在数组容量为16或者32大小时，它的索引都是不变的。

如果这个索引的值是0000_0000_0000_0000_0000_0000_0001_1001，那么在16和32容量下计算出来的所以就不同了。

当 oldCap ==16，再来看e.hash & oldCap == 0，即hash值的第5为是0，这样在扩容到32后，取索引得出来的结果还是和16的一样；e.hash & oldCap == 1，即hash值的第5为是1，这样在扩容到32后，取索引得出来的结果就和16的不一样了，索引位置比oldCap大了一个oldCap值；

如果 (e.hash & oldCap) == 0 则该节点在新表的下标位置与旧表一致都为 j
如果 (e.hash & oldCap) == 1 则该节点在新表的下标位置 j + oldCap

在这里插入图片描述

put

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

//evict: 是否在插入后进行驱逐操作,比如LinkedHashMap实现颗LRU算法，会把老的数据删除
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为null,先初始化tableif ((tab = table) == null || (n = tab.length) == 0)   n = (tab = resize()).length;// 如果(n - 1) & hash这个位置没有元素，就直接插入一个Nodeif ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {// 如果这个位置有元素，说明有碰撞，就会产生链表Node<K,V> e; K k;if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))// hash一样，key也相等，说明是put("1",1),put("1",2)这样的调用。e = p;// hash一样，但是key不相等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);// 当这个链表大小超过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))))// hash一样，key相等，覆盖break;// 继续往链表中找p = e;}}if (e != null) { // existing mapping for keyV oldValue = e.value;// 如果onlyIfAbsent为false,即不管这个节点的值是不是null，都会替换if (!onlyIfAbsent || oldValue == null)// 当这个节点上的值是null的时候，可以替换// 可以使用 putIfAbsent方法e.value = value;afterNodeAccess(e);return oldValue;}}// ++modCount;// 数组中的元素数量超过阈值，就会扩容if (++size > threshold)resize();afterNodeInsertion(evict);return null;
}

(n - 1) & hash相当于n % hash,求余数，n是一个2的幂次方数，减去1，即后面全是1，前面全是0，与上这个hash，只能保证经过运算，结果都会在n - 1范围内。

treeifyBin

final void treeifyBin(Node<K,V>[] tab, int hash) {int n, index; Node<K,V> e;// 如果table的长度太小，不要转化为红黑树，直接扩容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就是root节点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);
}

treeify

树行化，即把链表中的节点变成红黑树

final void treeify(Node<K,V>[] tab) {TreeNode<K,V> root = null;// x是待插入的节点for (TreeNode<K,V> x = this, next; x != null; x = next) {next = (TreeNode<K,V>)x.next;x.left = x.right = null;// 先初始化根节点if (root == null) {x.parent = null;x.red = false;// 初始化红黑树根节点root = x;}else {// 待插入节点x的keyK k = x.key;int h = x.hash;Class<?> kc = null;// 下面就是插入节点xfor (TreeNode<K,V> p = root;;) {int dir, ph;K pk = p.key;if ((ph = p.hash) > h)// 父节点的hash值大于x的hash值，则x需要往红黑树左边插入dir = -1;else if (ph < h)// 往父节点p右边插入dir = 1;// 和父节点p的hash值相等，就要看这个key有没有实现Comparable接口else if ((kc == null &&(kc = comparableClassFor(k)) == null) ||// 如果k实现了Comparable接口，就调用它的compareTo方法，比较k和pk的大小(dir = compareComparables(kc, k, pk)) == 0)// compareTo方法比较也是相等的// 就比较x节点key和父节点key的identityHashCodedir = tieBreakOrder(k, pk);TreeNode<K,V> xp = p;// 找到红黑树的叶子节点，一会把x插入到叶子节点子节点上if ((p = (dir <= 0) ? p.left : p.right) == null) {// xp已经是叶子节点了// 初始化x节点的父节点x.parent = xp;if (dir <= 0)xp.left = x;elsexp.right = x;// 重新平衡红黑树，返回树的根节点root = balanceInsertion(root, x);// 插入一个节点结束，继续下一个节点break;}}}}moveRootToFront(tab, root);
}

untreeify

该方法将红黑树转化为链表

final Node<K,V> untreeify(HashMap<K,V> map) {Node<K,V> hd = null, tl = null;for (Node<K,V> q = this; q != null; q = q.next) {Node<K,V> p = map.replacementNode(q, null);if (tl == null)hd = p;elsetl.next = p;tl = p;}return hd;
}

static int tieBreakOrder(Object a, Object b) {int d;if (a == null || b == null ||(d = a.getClass().getName().compareTo(b.getClass().getName())) == 0)d = (System.identityHashCode(a) <= System.identityHashCode(b) ?-1 : 1);return d;
}

moveRootToFront

static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {int n;if (root != null && tab != null && (n = tab.length) > 0) {// 红黑树根节点在数组中的位置int index = (n - 1) & root.hash;TreeNode<K,V> first = (TreeNode<K,V>)tab[index];// 经过插入或者删除操作，这个红黑树重新平衡，会导致根节点发生变化，之前保存在table数组中的可能已经不是红黑树的根节点了if (root != first) {Node<K,V> rn;// 把数组index位置的元素替换为根节点对象tab[index] = root;// -----------------就是把root节点从链表中删除---------------------     // 获取根节点对象的前一个节点TreeNode<K,V> rp = root.prev;if ((rn = root.next) != null)// 如果后节点不为空 // 相当于把root从链表中摘除((TreeNode<K,V>)rn).prev = rp;if (rp != null)// 如果root的前节点不为空// 到这就说明这个链表就和root无关了rp.next = rn;//---------------------------------------------------------  // ---------------把root节点放在链表首位----------------------if (first != null)// 如果数组该位置上原来的元素不为空// 相当于root目前位于链表的首位first.prev = root;root.next = first;root.prev = null;//---------------------------------------------------------  }assert checkInvariants(root);}
}

remove

public V remove(Object key) {Node<K,V> e;return (e = removeNode(hash(key), key, null, false, true)) == null ?null : e.value;
}

// matchValue为true表示还需要对比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 && // table数组要存在(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;elsep.next = node.next;++modCount;--size;afterNodeRemoval(node);// 把删掉的节点返回return node;}}return null;
}

split

resize() 方法的作用就是初始化或者扩容哈希表。当扩容时，如果当前桶中元素结构是红黑树，并且元素个数小于链表还原阈值 UNTREEIFY_THRESHOLD （默认为 6），就会把桶中的树形结构缩小或者直接还原（切分）为链表结构，调用的就是 split()

重点是理解e.hash & bit，理解这个就知道这个函数在干嘛了，具体可以看resize方法讲解

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 orderTreeNode<K,V> loHead = null, loTail = null;TreeNode<K,V> hiHead = null, hiTail = null;int lc = 0, hc = 0;// Node不仅是红黑树的节点，也是双向链表// 扩容时所以根据链表将这个分成2组新链表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;elseloTail.next = e;loTail = e;++lc;}else {if ((e.prev = hiTail) == null)hiHead = e;elsehiTail.next = e;hiTail = e;++hc;}}if (loHead != null) {if (lc <= UNTREEIFY_THRESHOLD)// 小于等于6，就不要用红黑树了，用链表tab[index] = loHead.untreeify(map);else {// 说明大于6，用红黑树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);}}
}

hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}

if (loHead != null) {if (lc <= UNTREEIFY_THRESHOLD)// 小于等于6，就不要用红黑树了，用链表tab[index] = loHead.untreeify(map);else {// 说明大于6，用红黑树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);}
}

}