文章导航
目录
文章导航
前言
正文
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桶还未被创建，此时为null public 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<K,V>[] resize() { //获取旧hash桶 Node<K,V>[] 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 threshold newCap = 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<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; if (oldTab != null) { //遍历旧hash桶 for (int j = 0; j < oldCap; ++j) { Node<K,V> e; //获取hash桶中第一个节点，根据第一个节点去关联其它链表节点或红黑树节点。将节点赋值给e if ((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<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order //链表的迁移过程，见下文图解 Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> 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; 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; }
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<K,V> map, Node<K,V>[] tab, int index, int bit) { //当前hash桶所在下标的第一个节点 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; //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<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) { //如果分割后节点数小于等于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<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; // 红黑树的父节点 TreeNode<K,V> left; // 红黑树的左节点 TreeNode<K,V> right; // 红黑树的右节点 TreeNode<K,V> prev; // 指向链表的上个节点 boolean red;
以上代码我们并没用看到next属性，但是可以看到其继承了LinkedHashMap…Entry<K,V>父类，而LinkedHashMap…Entry<K,V>继承了Node<K,V>，所以红黑树也就拥有了next属性。
HashMap链表转红黑树
对于红黑树不熟悉的，可参考上篇文章《HashMap源码学习：红黑树原理详解》
final void treeify(Node<K,V>[] tab) { TreeNode<K,V> root = null; 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 { //获取插入节点key值 K k = x.key; //获取插入节点hash值 int h = x.hash; Class<?> kc = null; //从跟节点开始遍历 for (TreeNode<K,V> 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); //将红黑树当前所在节点赋值给xp TreeNode<K,V> xp = p; //将p赋值为下个节点，如果下个节点为null，证明是找到插入位置了 if ((p = (dir <= 0) ? p.left : p.right) == null) { //将插入节点的父亲指向xp x.parent = xp; //这里根据方向决定是插入左边还是右边 if (dir <= 0) xp.left = x; else xp.right = x; //插入之后，可能会破坏红黑树的特性，需要进行平衡操作，如变色、左旋、右旋。可参考上篇文章 root = balanceInsertion(root, x); break; } } } } //保持根节点位于hash桶中所在下标的第一个节点 moveRootToFront(tab, root); }
HashMap红黑树转链表
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); //tl为空，证明是第一次遍历时 if (tl == null) //将当前新节点设置为头节点 hd = p; else tl.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<K,V>[] tab; Node<K,V> 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<K,V> 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<K,V>)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 1st treeifyBin(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 key V 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<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { Node<K,V>[] tab; Node<K,V> p; int n, index; //如果hash桶为null、数量为0、计算后hash桶所在下标为null时，证明没数据存在。直接返回null 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; //如果其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<K,V>)p).getTreeNode(hash, key); else { //一致遍历查找，直到最后一个值，看是否查询到，查询到则赋值给node do { 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<K,V>)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<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; //如果hash桶为null、数量为0、计算后hash桶所在下标为null时，证明没数据存在。直接返回null if ((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<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; }
HashMap更新数据
@Override public V replace(K key, V value) { Node<K,V> 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桶所在下标；
