本文最后更新于:January 31, 2022 am
前言 HashMap使用键值对的存储结构。其底层使用数组实现,应用链地址散列法,并配合红黑树,实现了高效的查找逻辑。本文的HashMap源码基于jdk1.8。
源码解析 变量 下文经常提到的桶 就是其实就是table数组中的任意一个位置
这里变量的含义不理解没关系,看完后面的方法调用就知道了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4 ;static final int MAXIMUM_CAPACITY = 1 << 30 ;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 ;transient Node<K,V>[] table;transient Set<Map.Entry<K,V>> entrySet;transient int size;transient int modCount;int threshold;final float loadFactor;
构造方法 构造方法总共有4个
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 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 ); }
tableSizeFor(int cap) 方法 在构造方法3中,threshold是通过tableSizeFor
计算的,看一下这个方法
1 2 3 4 5 6 7 8 9 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 ; return (n < 0 ) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1 ; }
该方法的作用是找到一个最小k使得2^k>=cap
,这一操作使得不论构造函数中传入的initialCapacity是多少,最终都会被tableSizeFor
处理成2^k
形式 ,这一操作后续会解释作用。
简单解释一下为什么tableSizeFor可以实现这种效果。假设cap=6,则n=6-1=5。n的二进制即为101
,无符号右移之后变为010
,则101 | 010 = 111
。新的n为111
,那么后续再移位之后,因为进行的是或
操作,所以每次得到的结果都是111
。最终return了n+1,即1000
对应十进制的8,也就是2^3
。
可以看出,每次的移位取或操作都让n的二进制高位开始的连续1的数量翻倍,因为在构造函数3中限制了initialCapacity的最大值为MAXIMUM_CAPACITY=1 << 30
,所以最极端的情况下,n最终的二进制会对应30个1,最后再加1,正好是2^30
。
那么第一步取n的时候,为什么要令n=cap-1呢?假如一开始cap就是2^k
,那么如果一开始不进行减1的操作,最终的n会等于2^(k+1)
,这显然不是我们想要的结果。所以先让cap减1,这时n对应的二进制就是k个1,移位取或操作对其没有影响。最后return时,n+1又变回了2^k
。
put(K key, V value)方法 存入键值对的方法,实际是通过putVal方法实现
1 2 3 public V put (K key, V value) { return putVal(hash(key), key, value, false , true ); }
hash(Object key)方法 计算key的hash值,因为key.hashCode是一个int值,(h = key.hashCode()) ^ (h >>> 16)
相当于把高16位和低16位进行异或,使分布更松散。具体原因可以参看知乎的这个高赞答案 。
1 2 3 4 static final int hash (Object key) { int h; return (key == null ) ? 0 : (h = key.hashCode()) ^ (h >>> 16 ); }
putVal方法 介绍putVal前,我们先看一张图,直观的感受一下hashmap是如何存储数据的。可以看出当table中的一个桶的结点数目超过临界值时,会把原先的链表转化成红黑树。这里的转化还有个前提条件是table的长度要大于等于64,图中为了方便没有体现这点。
方法流程
如果一开始table为空则调用扩容方法初始化table
如果待插入的桶为空则直接插入
如果这个桶已经有元素,并且第一个元素的hash值和待插入元素相同,转到后续处理,否则转到4
处理hash冲突,如果是树节点,则按照红黑树逻辑处理;如果是普通结点,则遍历链表寻找是否存在与待插入元素相同的key。如果找到了key,跳出遍历,转到5,否则转到6
根据onlyIfAbsent判断是否需要更新旧的value,return oldValue之后方法结束
在链表末尾插入新结点,并判断结点数量是否到达临界值,达到临界值则树化。转到7
结点总数加1,并判断是否需要扩容
下面看具体代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 final V putVal (int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; 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; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; 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 ); if (binCount >= TREEIFY_THRESHOLD - 1 ) treeifyBin(tab, hash); break ; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break ; p = e; } } if (e != null ) { V oldValue = e.value; if (!onlyIfAbsent || oldValue == null ) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null ; }
现在解释一下上文注释中提到的问题
(n - 1) & hash的作用
首先hash是一个int范围的数,在java中即为-2147483648 至2147483647。如果直接把所有的hash都对应到table数组的索引,那table.length
要超过40亿!这显然不科学。因此,我们可以把hash % n
当作索引值,这样范围就小很多了。
而对于计算机来说,&运算要比%快。并且,只有table的长度是2的k次幂时 ,(n - 1) & hash
才等于hash % n
。这又是为什么?首先,当n = 2^k
时,n-1对应的2进制是k个1,所以(n - 1) & hash
取到的是hash中的最后k位的值,因为hash的二进制中,倒数第k位之前的部分代表的值一定是n的倍数,所以必然为0,因此最后k位代表的值正是hash % n
的结果。这也解释了为什么table的长度一定要是2的k次幂。
下面给出示意图,以n=8,hash=75为例
resize() 扩容方法 用于初始化table或者将table容量翻倍
方法流程
旧容量大于0,判断容量翻倍后是否超过上限,如果不超过则翻倍。如果旧门槛翻倍后溢出,转到4
旧容量等于0,旧门槛大于0时,让新容量等于旧门槛。转到4
旧容量和旧门槛都是0,则用默认值进行初始化
用newCap * loadFactor计算出新门槛
按照新容量建立新数组
将旧数组的元素映射到新数组,并且将原来桶中的链表拆成两部分,低位的还在原来桶的位置j,高位的放到oldCap+j的位置,oldCap是旧容量
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 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 ) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap << 1 ) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1 ; } else if (oldThr > 0 ) newCap = oldThr; else { newCap = DEFAULT_INITIAL_CAPACITY; newThr = (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 ) newTab[e.hash & (newCap - 1 )] = e; else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this , newTab, j, oldCap); else { 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; }
get(Object key)方法 根据key获取value
方法流程
根据key的hash值查找table对应的位置,如果不为空则转到2,否则直接返回null
判断桶中第一个元素是不是想要的,如果是,直接返回,否则到3
如果桶中结点不止一个,则树节点使用二叉平衡树的逻辑查找,普通结点遍历链表查找
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 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; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1 ) & hash]) != null ) { if (first.hash == hash && ((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 ; }
getTreeNode(int h, Object k) getTreeNode是TreeNode类的方法,这里放上简化后的TreeNode类
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 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; final TreeNode<K,V> getTreeNode (int h, Object k) { return ((parent != null ) ? root() : this ).find(h, k, null ); } 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 ; } }
remove(Object key)方法 根据key删除元素
方法流程
根据key的hash值查找对应的桶
如果是空桶直接返回null
如果桶不为空,且第一个元素就是要删除的,用node保留这个结点。否则转到4
查看后续元素,如果是树结点,则调用树的逻辑,普通结点则遍历链表
如果找到了要删除的结点,则进行删除,否则返回null
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 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 ; }
总结 本文分析了从HashMap最常用的put、get、remove方法入手,分析了其关联方法的代码。
其中,红黑树的插入删除逻辑等文中没有具体分析。计划之后专门写一篇红黑树的文章,再将这部分补充上。
参考文章 https://juejin.cn/post/6844903817855631373#heading-17
https://segmentfault.com/a/1190000012926722