Loading... ## HashMap原理解析 ### HashMap是什么? HashMap是AbstractMap的子类,Map的实现类,且实现了序列化和克隆接口。是我们经常使用到的一种集合,那它到底是如何存储数据,又如何保障数据不冲突的呢? ### HashMap的成员变量 ```java //默认初始容量(数组默认的大小),必须是2的整数次方。默认为16 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 //最大容量,为2^30,即1073741824 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; /*最小树形化容量阈值。即 当哈希表中的容量 > 该值时,才允许树形化链表(即将链表转换成红黑树)否则,若桶内元素太多时,则直接扩容,而不是树形化。为了避免进行扩容、树形化选择的冲突,这个值不能小于 4 * TREEIFY_THRESHOLD*/ static final int MIN_TREEIFY_CAPACITY = 64; //存储元素的数组 transient Node<K,V>[] table; //保存缓存的entrySet transient Set<Map.Entry<K,V>> entrySet; //存储元素的数量 transient int size; //记录结构修改的次数 transient int modCount; //如果尚未分配表数组,此字段保存初始数组容量,零表示 DEFAULT_INITIAL_CAPACITY。分配数组后,当实际大小(size * loadFactor)大于临界值时,会进行扩容 int threshold; //哈希表的加载因子 final float loadFactor; ``` **为什么成员变量的值使用的是移位运算,而不是指定值?** 实际上在Class编译后,移位运算就会计算为正常的int值储存在常量池里面。主要目的是为了防止人为的失误,将大小写成非2次幂的值。 **为什么大小要设置为2的整数次方?** 为了后面计算hash以及根据hash桶下标,保证均匀散列。 为了在扩容时,能保持链表或树的均匀分布。 **为什么装载因子是0.75?** 在空间利用率合理的情况下,减少hash冲突的发生。按照HashMap注释来看和泊松分布有关。 **Node节点** ```java static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } ...... } ``` ### HashMap的构造函数 HashMap提供了四种构造方法 1. new HashMap() ```java public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // 其余的值都为默认初始值,即:加载因子0.75、初始容量16、最大容量1073741824 } ``` 2. new HashMap(int) ```java public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } ``` 3. new HashMap(int, float) ```java //传入参数初始容量、加载因子 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; //计算初始容量返回最近的2次幂数值 this.threshold = tableSizeFor(initialCapacity); } 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; } ``` 4. new HashMap(Map) ```java public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); } ``` 可以从上面4个构造方法看出,除了第四种传入一个Map集合之外,其余3种初始化操作都仅仅是对成员变量进行赋值操作。所以通过前三种构造方法创建的HashMap对象并不会立即创建其内部存储数据的数组。那么是在什么环节创建的呢? ### put() 通过无参构造创建一个HashMap,往其put一个key-value。可以通过Debug进入put方法内部,并查看HashMap的成员变量的值。可以发现: ```java transient Node<K,V>[] table = null;//数组未创建。 int threshold = 0;//数组未创建时,0代表使用默认值16作为数组大小。 final float loadFactor = 0.75;//默认的加载因子 ``` 所以当HashMap初始化后,第一次put会进行数组的初始化。公有的put方法内部调用了final的putVal方法,且首先会调用`hashKey()`这个方法来计算当前存放key的hash值。 ```java public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } ``` **为何要使用`hashCode ^ (hashCode >>> 16)`计算hash值?** int类型占32位,那么 h >>> 16右移16位,与其本身进行异或,即高16位不变(右移后,高16位都变为0,0或1与0异或都为原值)。低16位与高16位进行异或,使得散列得更加均匀。 #### 源码阅读 ```java final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { //定义存储数组 tab,原来位置的元素 p,当前数组长度 n,put索引 i Node<K,V>[] tab; Node<K,V> p; int n, i; //判断当前数组是否未初始化或者为空,如果为空,调用resize进行初始化 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //判断当前put的元素所在的桶是否有元素,如果没有则直接把元素放进桶内。 //为什么使用(n - 1) & hash?因为n必然是2的次幂,所以他的二进制码只会有一位是1,减去一后,即1所在位变0,1后面的0都变成1。&运算后,就相当于结果必然是小于等于n-1的。因为前面的所有都是0,&运算后也必然为0;模拟了取余操作,加快了运算速度 if ((p = tab[i = (n - 1) & hash]) == null) //封装节点存储在当前下标 tab[i] = newNode(hash, key, value, null); else { //如果计算出来的桶位已经有元素了。 Node<K,V> e; K k; //判断他们的hash值是否一致,如果一致, 且key相同,则直接取原来的元素做处理。 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //不是相同元素,则判断是链表还是树。如果是树,则调用putTreeVal方法将节点放入树内 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); //当前桶存储的是一个链表 else { //binCount计算链表长度,如果当前节点的下一个节点不为空,且不是当前put的key。则自增 for (int binCount = 0; ; ++binCount) { //p的next为空,代表已经到了链表末尾。 if ((e = p.next) == null) { //将节点放进末尾, p.next = newNode(hash, key, value, null); //判断链表长度如果大于等于树化阈值-1(进行树化) 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; //元素指针后移(第一个if做的e = p.next) p = e; } } //如果e不是空节点,是重复元素 if (e != null) { // existing mapping for key V oldValue = e.value; //判断是否传入了onlyIfAbsent值为true,如果是true,仅当oldValue为空时进行更新 if (!onlyIfAbsent || oldValue == null) e.value = value; //模板方法,在子类LinkedHashMap中实现。目的是为了实现节点存储顺序。 afterNodeAccess(e); return oldValue; } } //操作次数加1 ++modCount; //判断新加元素后长度是否大于阈值(0.75 * capacity)在第一次resize后,threshold已不再是0;如果是则进行扩容 if (++size > threshold) resize(); //同样是模板方法,在子类LinkedHashMap中实现。 afterNodeInsertion(evict); return null; } ``` #### 流程概括 **`putVal()`的大致流程如下:** 1. 判断数组是否为空,如果为空则调用`resize()`方法进行初始化扩容 2. 根据put元素的hash值算出需要存放的桶位置,如果当前桶是空的,则直接存放。 3. 如果当前桶已经有元素,即发生了冲突,做如下判断: - 如果hash值以及key都相同,那么是相同元素,直接进行后续value覆盖操作。 - 如果当前桶元素是个红黑树,那么就调用红黑树的`putTreeVal()`方法存储元素。 - 如果当前是个链表,则遍历整个链表,判断是否有重复元素,如果有,则进行后续value覆盖,如果没有则插入到链表尾部 - 如果链表长度超过树化阈值TREEIFY_THRESHOLD也就是8时,则调用`treeifyBin()`方法进行转树操作。转树时,会判断数组长度是否小于64,如果小于则先调用`resize()`进行数组扩容。 - 判断put元素是否存在重复元素,如果存在,则根据条件对value进行值覆盖。并直接结束put方法返回旧值。 4. 判断数组新加元素后长度是否大于扩容阈值。如果大于则调用`resize()`方法进行扩容。 **整个put过程中有几个重要的方法调用** - `resize()`:对存储数组进行扩容 - `TreeNode$putTreeVal()`:插入一个树节点 - `treeifyBin`():进行链表转换树的操作 ### rezise() 首先是`resize()`方法,其主要是在元素插入以及链表长度树化过程中调用。主要是对HashMap内部的数组进行扩容,避免频繁的hash碰撞以及链表长度过长。 #### 源码阅读 ```java final Node<K,V>[] resize() { //原来的数组 Node<K,V>[] oldTab = table; //判断原数组是否为空,即初始化状态,第一次访问数组时进行初始化扩容。 int oldCap = (oldTab == null) ? 0 : oldTab.length; //factor * capacity 或者 0; int oldThr = threshold; //定义新数组的长度,新的阈值 int newCap, newThr = 0; //如果原数组长度大于0,即不是初始化扩容 if (oldCap > 0) { //判断是否超过最大阈值,2^30,超过则设置阈值为2^31-1 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; //不再进行扩容,直接返回原数组。 return oldTab; } //扩容后的容量小于2^30,且大于初始值16,则将扩容阈值翻倍。 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } //如果原数组容量小于等于0,且原扩容阈值大于0,新数组容量=原扩容阈值 这种情况如何发生? else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaults //原数组容量小于等于0,且原扩容阈值小于等于0,即初始化前。将数组容量设置为默认16,阈值设置为0.75 * 16 newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } //防止扩容阈值溢出。如果新数组长度为2^30,那么设置threshold=2^31-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"}) //创建新数组并将原数组table指针指向新数组。 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) { //置空,help GC oldTab[j] = null; //只有头元素,则将该元素的值重新计算下标并赋值 if (e.next == null) newTab[e.hash & (newCap - 1)] = e; //如果当前元素是树节点,则调用split方法进行rehash 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; do { next = e.next; //e.hash & oldCap == 0代表索引位置不变,!=0代表索引位置等于原索引位置+旧数组长度 //可以通过e.hash = hashCode ^ (hashCode >>> 16)进行推导;oldCap和16同是2的次幂。只有一位是1 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; } ``` #### 流程概括 **整个resize过程可以分为以下两部分:** 1. 判断原数组长度并计算新数组长度newCap以及扩容阈值newThr - 原数组长度大于0时,判断是否超过最大容量2^30,超过则将threshold设置为Integer.MaxValue并返回原数组。没超过则将newCap设置为2 * oldCap。并判断newCap是否还在(16,2^30)区间,如果在则设置newThr = 2 * oldThr。如果不在,且newCap超过2^30,则设置newThr=Integer.MaxValue,意味着HashMap理论最大存储容量就是Integer.MaxValue。 - 原数组长度小于等于0时,则代表初始化,oldThr>0则将newCap设置为oldThr。oldThr<=0则设置默认初始值,即16和12。 2. 创建新数组,并变量原数组将结点数据复制到新数组。 - 当前下标只有头元素,直接将该元素rehash到新数组。 - 当前下标是链表,则利用`(e.hash & oldCap) == 0`将链表元素分为低位元素和高位元素,低位元素直接存放在新数组的当前下标,高位元素存放在当前索引+旧数组长度的位置。 - 当前下标元素是红黑树,调用红黑树的`split()`方法分配到新数组。分配过程中如果与链表类似,都是采用`(e.hash & oldCap) == 0`分为高位和低位元素,且判断对应长度是否需要进行树化或退化链表,如果rehash后的长度小于等于6,则退化为链表。 ### get() ```java public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } /** * Implements Map.get and related methods. * * @param hash hash for key * @param key the key * @return the node, or null if none */ 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) { //如果根据hash找到的头元素hash值和查询元素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) { //如果头元素是树节点,则调用TreeNode$getTreeNode方法查找,红黑树也是个二叉搜索树 if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); //循环链表查找,找到返回,没找到就返回null do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; } ``` ### remove() ```java public V remove(Object key) { Node<K,V> e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; } /** * Implements Map.remove and related methods. * * @param hash hash for key * @param key the key * @param value the value to match if matchValue, else ignored * @param matchValue if true only remove if value is equal * @param movable if false do not move other nodes while removing * @return the node, or null if none */ 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。 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与当前remove的hash相同,就直接remove头元素。 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) node = p; else if ((e = p.next) != null) { //和get方法流程一致,找到对应的结点元素。 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); } } //如果按照key和hash找到对应的元素,且value相等则进行删除。 if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) { //树节点调用removeTreeNode方法 if (node instanceof TreeNode) ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable); //头结点就是要移除的元素,则将头结点的next节点存入对应下标 else if (node == p) tab[index] = node.next; //链表节点,将前一个节点的指针指向当前节点的next节点。1->2->3变成1->3 else p.next = node.next; //操作次数+1 ++modCount; //size - 1 --size; //LinkedHashMap实现元素移除的回调方法 afterNodeRemoval(node); return node; } } return null; } ``` ### **JDK1.7与1.8的HashMap区别** - 存储结构不同,1.7采用的数组+链表,1.8采用的是数组+链表/红黑树 - 1.7链表插入采用的是头插法,每次都会将元素放在链表头部,多线程情况下扩容会导致死链。1.8采用的尾插法,不会产生死链。 © Allow specification reprint Support Appreciate the author AliPayWeChat Like 3 If you think my article is useful to you, please feel free to appreciate