Java集合之探究HashMap的源码

1 概述

HashMap的底层跟HashTable一样是个哈希表,所有的动作都是围绕着一个Map.Entry<K, V>[] table数组来的。我们姑且称为这个table数组的每一个位置为桶,那么HashMap的结构可以理解为
image.png

2 底层原理

2.1 key 所在的桶

  • HashMap 通过 hash & (table.length - 1)来定位key在哪个桶, 由于 table.length 是 2^n 所以 table.length - 1 = 2^ - 1
    它的二进制一定是末尾 n 个 1, (hash & (table.length - 1)) <= 2^n - 1 必然成立

2.2 扩容

  • threshold = capacity * loadFactory; 当 size(key-value对的数量)大于 threshold时,触发调用
    resize()
  • resize()
    • 当桶的数量为MAXIMUM_CAPACITY(2^30)时, 直接将threshold设置为Integer.MAX_VALUE 不扩容且阻止下一次扩容
    • 当桶的数量大于0且没有达到MAXIMUM_CAPACITY时, 桶的数量double, 如果double后桶的数量仍然小于MAXIMUM_CAPACITY且原来桶的容量不为0,threshold也double
    • 当桶的数量为0且threshold大于0时, 将桶的设置为 threshold
    • 当桶的数量和threshold都等于0时,使用默认值,桶的数量设定为16, threshold = 16 * 0.75 = 12
    • 桶的数量扩充之后,也需要对桶里的元素进行重新分桶
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) { // oldCap >= 2^30 不扩容 threshold = Integer.MAX_VALUE; return oldTab; } // 假定newCap = oldCap * 2 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) // newThr也double newThr = oldThr << 1; // double threshold } else if (oldThr > 0) // initial capacity was placed in threshold // oldCap = 0 且 oldThr > 0走到这 newCap = oldThr; else { // zero initial threshold signifies using defaults // oldCap = 0 且 oldThr = 0走到这, 说明这是一个未初始化的map newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { // 设置 threshold 的值,假定为 newCap * loadFactory, 不能超过 Integer.MAX_VALUE 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的重新分桶方法 ((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; 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; }

2.3 添加元素 put(Key, Value)

  • put(Key, Value)
    • 先检查table数组是否初始化,如果没有,调用resize()将桶的数量初始化成 16
    • 定位key在哪个桶,如果桶为空,直接加到桶里, 如果key冲突(hash相同且equals返回true),覆盖
    • 如果桶已经有元素了
      • 桶没有树化且链表长度小于 8,key冲突则覆盖,不冲突就追加到末尾
      • 桶没有树化且链表长度等于 8,key冲突则覆盖,不冲突先树化后追加到树里
      • 桶已经树化, key冲突则覆盖,否则追加
    • 检查容量,是否扩容
    • 若覆盖,返回被覆盖的值,否则返回null
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为空或者是长度为0, 初始化table if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // n 为resize()之后tab(table)的长度 // (n-1) & hash 来定位 index(怎么保证 index < n?) if ((p = tab[i = (n - 1) & hash]) == null) // tab[index]为空,说明是index这个桶为空,直接添加 tab[i] = newNode(hash, key, value, null); else { // p为table[index]存储的Node Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) // 依然是使用 hash相等和equals相等来判断,使用 == 兼容 null e = p; // key相等 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // p 的类型为treeNode, else { // key 与table[index]的key不相等 for (int binCount = 0; ; ++binCount) { // 死循环遍历p if ((e = p.next) == null) { // 遍历到末尾 p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); // 链表长度大于8时,树化 break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; // 找到需要覆盖的节点 } } if (e != null) { // existing mapping for key // 覆盖并返回原value V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } // 没找到匹配的key ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }

2.4 get(key)

  • get(Key) 委托给了下面这个方法,没什么技术含量,先定位key所在的桶,然后比较第一个。
    如果第一个key不是,再根据这个桶是否树化,如果没有树化,就是用单向链表迭代比较,如果树化了就调用二叉查找树的search方法
final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && // 根据key的hash定位桶 (first = tab[(n - 1) & hash]) != null) { // 桶里有元素走到这里 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; } // TreeNode里的方法 final TreeNode<K,V> find(int h, Object k, Class<?> kc) { TreeNode<K,V> p = this; do { int ph, dir; K pk; TreeNode<K,V> pl = p.left, pr = p.right, q; if ((ph = p.hash) > h) p = pl; else if (ph < h) p = pr; else if ((pk = p.key) == k || (k != null && k.equals(pk))) return p; else if (pl == null) p = pr; else if (pr == null) p = pl; else if ((kc != null || (kc = comparableClassFor(k)) != null) && (dir = compareComparables(kc, k, pk)) != 0) p = (dir < 0) ? pl : pr; else if ((q = pr.find(h, k, kc)) != null) return q; else p = pl; } while (p != null); return null; }

2.5 树化

  • 树化 这个就不看细节了,我们知道红黑树是一个二叉查找树,所以避免不了需要比较两个key的大小,在java中如果一个类实现了Comparable接口,
    可以很方便地定义两个key的大小,但是如果作为Key的类没有实现这个接口,树化的过程是怎么做的呢?看TreeNode的treeify(Node[])方法
    • 如果Key实现了Comprable接口,使用这个接口比较
    • 如果Key没实现Comprable接口, 静态方法tieBreakOrder(a, b)进行比较
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 { K k = x.key; int h = x.hash; Class<?> kc = null; for (TreeNode<K,V> p = root;;) { int dir, ph; K pk = p.key; if ((ph = p.hash) > h) dir = -1; else if (ph < h) dir = 1; // 以下几行代码说明,如果Key的类实现了Comparable接口,使用Compareable接口 // 否则调用默认的方法 tieBreakOrder(k, pk) else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0) dir = tieBreakOrder(k, pk); TreeNode<K,V> xp = p; if ((p = (dir <= 0) ? p.left : p.right) == null) { x.parent = xp; if (dir <= 0) xp.left = x; else xp.right = x; root = balanceInsertion(root, x); break; } } } } moveRootToFront(tab, root); } 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; }

3 总结

Q1: 为什么桶的数量要设置为 2^n
A1: 对一个普通的长度为l的哈希表,我们分桶的时候需要取模%来定位元素在哪个桶,如果哈希表的长度为 2^n,因为 2^-1 的二进制永远是前面为0后面跟着一串1,这样就可以使用效率更高的 位与& 运算来代替模运算了


Q2: loadFactory的作用是什么?怎么设置?
A2: loadFactory可以在作为构造器参数传入 new HashMap<>(initCapacity, loadFactory), 用来衡量Map的饱满度,因为决定扩容的阈值 threshold = 桶的数量 * loadFactory, 当Map的元素数量大于threshold时,就会触发扩容, 所以loadFactory越大就越不容易触发扩容机制,此时就是用更少的桶存储更多的节点,空间利用率变高,但是由于桶的数量少,分到同一个桶的key就越多,再put和get的效率就越低。相反,如果loadFactory设置地很小,就越容易触发扩容,桶的数量就越多,每个桶的链表长度或树的长度就会越短,也更快达到扩容上限,put和get的效率就会越高,但是因为Map不饱满,空间利用率就很低。所以,当你对Map的性能要求高,而且内存充足的时候,可以把loadFactory设置小一点,反之设置大一点。没有特殊要求的化就用默认的0.75,这是大佬觉得比较均衡的一种策略。


Q3: 为什么要进行树化?为什么是红黑树?为什么不一开始就使用红黑树
A3: 单向链表长度过长的时候,迭代查找的时间复杂度 O(n),使用红黑树的时间复杂度为O(lgn).优先使用链表的原因是,我们期望我们的算法有较少的冲突,而且因为扩容的原因,我们不断增加桶来稀释这种冲突,链表在节点少的时候性能不错,空间利用率高。使用红黑树只是在情况不妙的时候做的备选。


Q4: 在初始化HashMap的时候传入的值是实际初始化桶的数量吗?
A4: 不一定,实际桶的数量永远是2^n, 初始化的时候initCapacity被用来确定初始的threshold。只有在第一次调用put方法时才会真正初始化table数组

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); }
阅读(50)
评论(2)
updated@2020-11-02
评论区
2
234
2020-11-16
12332
目录