HashMap底层原理及jdk1.8源码解读吐血整理1.3w字长文 _hashMap

知识为进步之母,而进步又为富强之源泉。这篇文章主要讲述HashMap底层原理及jdk1.8源码解读吐血整理1.3w字长文相关的知识，希望能为你提供帮助。
@[toc]
一、前言==写在前面：小编码字收集资料花了一天的时间整理出来，对你有帮助一键三连走一波哈，谢谢啦！！==
HashMap在我们日常开发中可谓经常遇到，HashMap 源码和底层原理在现在面试中是必问的。所以我们要掌握一下，也是作为两年开发经验必备的知识点！HashMap基于Map接口实现，元素以& lt; Key,Value& gt;的方式存储，并且允许使用null 键和null值，因为key不允许重复，因此只能有一个键为null，另外HashMap是无序的、线程不安全的。
HashMap继承类图快捷键Ctrl+alt+U

文章图片

二、存储结构介绍底层结构实例图

文章图片

三、源码分析之常用变量解读

/** * 默认初始容量 - 必须是 2 的幂。 */ static final int DEFAULT_INITIAL_CAPACITY = 1 < < 4; // aka 16/** * 最大容量，如果一个更高的值被任何一个带参数的构造函数隐式指定使用。必须是 2 < = 1< < 30 的幂。 * 简单理解为：最大容量2的30次幂，如果带容量也会转化为2的次幂 */ static final int MAXIMUM_CAPACITY = 1 < < 30; /** * 构造函数中未指定时使用的负载因子。经过官方测试测出减少hash碰撞的最佳值 */ static final float DEFAULT_LOAD_FACTOR = 0.75f; /** * 使用红黑树的计数阈值，超过8则转化为红黑树 */ static final int TREEIFY_THRESHOLD = 8; /** * 使用红黑树的计数阈值，低于6则转化为链表 */ static final int UNTREEIFY_THRESHOLD = 6; /** * 链表转化为红黑树，除了有阈值的限制，还有另外一个限制，需要数组容量至少达到64，才会转化为红黑树。 * 这是为了避免，数组扩容和树化阈值之间的冲突。 */ static final int MIN_TREEIFY_CAPACITY = 64; /** * 在首次使用时初始化，并根据需要调整大小。分配时，长度始终是 2 的幂。 * （我们还在某些操作中允许长度为零，以允许当前不需要的引导机制） */ transient Node< K,V> [] table; /** * 保存缓存的 entrySet()，也就是存放的键值对 */ transient Set< Map.Entry< K,V> > entrySet; /** * 此映射中包含的键值映射的数量，就是数组的大小 */ transient int size; /** * 记录集合的结构变化和操作次数（例如remove一次进行modCount++）。 * 该字段用于使 HashMap 的 Collection-views 上的迭代器快速失败。如果失败也就是我们常见的CME * （ConcurrentModificationException）异常 */ transient int modCount; /** * 数组扩容的大小 * 计算方法 capacity * load factor容量 * 加载因子 * @serial */ int threshold; /** * 哈希表的负载因子。 * @serial */ final float loadFactor;

四、源码分析之构造方法解读

/** * 构造一个具有指定初始容量和负载因子的构造方法 * 不建议使用这个构造方法，加载因子经过官方测试是效率最好的，所以为了效率应该保持默认 */ public HashMap(int initialCapacity, float loadFactor) // 参数为负数会抛出IllegalArgumentException异常 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的次幂，直接给你转化为2的次幂 // 传的参数为11，会自动转化为比参数大的最近的2的次幂的值，也就是16。 // 我们后面会详细说这个方法怎么进行转化的 this.threshold = tableSizeFor(initialCapacity); /** * 构造一个只有指定初始容量的方法 */ public HashMap(int initialCapacity) // 我们会发现还是调用上面两个参数的构造方法，自动帮我们设置了加载因子 this(initialCapacity, DEFAULT_LOAD_FACTOR); /** * 构造一个具有默认初始容量(16) 和默认负载因子(0.75)的构造方法 */ public HashMap() this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted/** * 指定map集合，转化为HashMap的构造方法 */ public HashMap(Map< ? extends K, ? extends V> m) // 使用默认加载因子 this.loadFactor = DEFAULT_LOAD_FACTOR; //调用PutMapEntries()来完成HashMap的初始化赋值过程 putMapEntries(m, false); /** * 将传入的子Map中的全部元素逐个添加到HashMap中 */ final void putMapEntries(Map< ? extends K, ? extends V> m, boolean evict) // 获得参数Map的大小，并赋值给s int s = m.size(); // 判断大小是否大于0 if (s > 0) // 证明有元素来插入HashMap // 判断table是否已经初始化如果table=null一般就是构造函数来调用的putMapEntries，或者构造后还没放过任何元素 if (table == null)// pre-size // 如果未初始化，则计算HashMap的最小需要的容量（即容量刚好不大于扩容阈值）。这里Map的大小s就被当作HashMap的扩容阈值，然后用传入Map的大小除以负载因子就能得到对应的HashMap的容量大小（当前m的大小 / 负载因子 = HashMap容量） // ((float)s / loadFactor)但这样会算出小数来，但作为容量就必须向上取整，所以这里要加1。此时ft可以临时看作HashMap容量大小 float ft = ((float)s / loadFactor) + 1.0F; // 判断ft是否超过最大容量大小，小于则用ft，大于则取最大容量 int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY); // 暂时存放到扩容阈值上,tableSizeFor会把t重新计算到2的次幂给扩容数组大小 if (t > threshold) threshold = tableSizeFor(t); // 如果当前Map已经初始化,且这个map中的元素个数大于扩容的阀值就得扩容 // 这种情况属于预先扩大容量，再put元素 else if (s > threshold) // 后面展开说 resize(); // 遍历map,将map中的key和value都添加到HashMap中 for (Map.Entry< ? extends K, ? extends V> e : m.entrySet()) K key = e.getKey(); V value = https://www.songbingjia.com/android/e.getValue(); // 调用HashMap的put方法的具体实现方法putVal来对数据进行存放。该方法的具体细节在后面会进行讲解 // putVal可能也会触发resize putVal(hash(key), key, value, false, evict);

五、源码分析之常用方法解读 1、tableSizeFor方法解读

/** * 返回给定目标容量的 2 次方。 */ static final int tableSizeFor(int cap) // cap = 10 int n = cap - 1; n |= n > > > 1; n |= n > > > 2; n |= n > > > 4; n |= n > > > 8; n |= n > > > 16; // 小于0就是1，如果大于0在判断是不是超过最大容量就是n=15+1 = 16，超过就按最大容量 return (n < 0) ? 1 : (n > = MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;

以cap为10为例：（右移规则为：==无符号位右移==）
10的二进制为：0000 0000 0000 0000 0000 0000 0000 1010
执行

int n = cap - 1;

二进制结果为：0000 0000 0000 0000 0000 0000 0000 1001
执行

n |= n &
gt;
&
gt;
&
gt;
 1;
（先进行右移，结果和原来的数进行或运算[==有1则1==]）

0000 0000 0000 0000 0000 0000 0000 1001
0000 0000 0000 0000 0000 0000 0000 0100n> > 1结果
————————————————————
0000 0000 0000 0000 0000 0000 0000 1101n |= n > > 1 结果
二进制结果为：0000 0000 0000 0000 0000 0000 0000 1101
执行

n |= n &
gt;
&
gt;
&
gt;
 2;

0000 0000 0000 0000 0000 0000 0000 1101
0000 0000 0000 0000 0000 0000 0000 0011n> > 2结果
————————————————————
0000 0000 0000 0000 0000 0000 0000 1111n |= n > > 2 结果
二进制结果为：0000 0000 0000 0000 0000 0000 0000 1111
执行

n |= n &
gt;
&
gt;
&
gt;
 4;

0000 0000 0000 0000 0000 0000 0000 1111
0000 0000 0000 0000 0000 0000 0000 0000n> > 4结果
————————————————————
0000 0000 0000 0000 0000 0000 0000 1111n |= n > > 4 结果
二进制结果为：0000 0000 0000 0000 0000 0000 0000 1111
执行

n |= n &
gt;
&
gt;
&
gt;
 8;

0000 0000 0000 0000 0000 0000 0000 1111
0000 0000 0000 0000 0000 0000 0000 0000n> > 8结果
————————————————————
0000 0000 0000 0000 0000 0000 0000 1111n |= n > > 8 结果
二进制结果为：0000 0000 0000 0000 0000 0000 0000 1111
执行

n |= n &
gt;
&
gt;
&
gt;
 16;

0000 0000 0000 0000 0000 0000 0000 1111
0000 0000 0000 0000 0000 0000 0000 0000n> > 16结果
————————————————————
0000 0000 0000 0000 0000 0000 0000 1111n |= n > > 16 结果
二进制结果为：0000 0000 0000 0000 0000 0000 0000 1111
我们会发现，当数小的的时候进行到4时就不会变了我们得到的值为15，即输入10，经过此方法后得到15。遇到大的数才会明显，大家可以找个大的数字进行试试就是先右移在进行或运算。最后进行三门运算进行+1操作，最后结果为16=2^4
2、hash方法解读

static final int hash(Object key) int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h > > > 16);

先判断key是否为空，若为空则返回0。上面说了HashMap仅支持一个key为null的。若非空，则先计算key的hashCode值，赋值给h，然后把h右移16位，并与原来的h进行异或处理（相同为1，不同为0）。
注释进行谷歌翻译：
计算 key.hashCode() 并传播（XOR）更高位的哈希降低。由于该表使用二次幂掩码，因此仅在当前掩码之上位变化的散列集将始终发生冲突。（已知的例子是在小表中保存连续整数的 Float 键集。）因此，我们应用了一种变换，将高位的影响向下传播。在位扩展的速度、实用性和质量之间存在折衷。因为许多常见的散列集已经合理分布（所以不要从传播中受益），并且因为我们使用树来处理 bin 中的大量冲突，我们只是以最简单的方式对一些移位的位进行异或，以减少系统损失，以及合并最高位的影响，否则由于表边界，这些最高位将永远不会用于索引计算。
==总结==：使用最简易的方式，及减少系统损失又减少了hash碰撞。
3、put方法解读

文章图片

/** * 将指定的值与此映射中的指定键相关联。即当前key应该存放在数组的哪个下标位置 * 如果映射先前包含键的映射，则替换旧的值。 */ public V put(K key, V value) return putVal(hash(key), key, value, false, true); /** * 这才是真正的保存方法 * @param hash经过hash运算后的key * @param key你要添加的key * @param value你要添加的value * @param onlyIfAbsent如果为真，则不要更改现有值，本次为FALSE，可以替换更改 * @param evict如果为 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; // 判断table是否为空 if ((tab = table) == null || (n = tab.length) == 0) // 如果空的话，会先调用resize扩容,resize我们后面展开讲解 n = (tab = resize()).length; // 把通过hash得到的值与数组大小-1进行与运算，这个运算就可以实现取模运算，而且位运算还有个好处，就是速度比较快。 // 得到key所对应的数组的节点，然后把该数组节点赋值给p,然后判断这个位置是不是有元素 if ((p = tab[i = (n - 1) & hash]) == null) // key、value包装成newNode节点，直接添加到此位置。 tab[i] = newNode(hash, key, value, null); // 如果当前数组下标位置已经有元素了，又分为三种情况。 else Node< K,V> e; K k; // 当前位置元素的hash值等于传过来的hash，并且他们的key值也相等 if (p.hash == hash & & ((k = p.key) == key || (key != null & & key.equals(k)))) // 则把p赋值给e，后续需要新值把旧值替换 e = p; // 来到这里说明该节点的key与原来的key不同，则看该节点是红黑树，还是链表 else if (p instanceof TreeNode) // 如果是红黑树，则通过红黑树的方式，把key-value存到红黑树中。后面再讲解这个方法 e = ((TreeNode< K,V> )p).putTreeVal(this, tab, hash, key, value); else // 来到这里说明结构为链表，把key-value使用尾插法插到链表尾。 // jdk1.7 链表是头插入法，在并发扩容时会造成死循环 // jdk1.8 就把头插入法换成了尾插入法，虽然效率上有点稍微降低一些，但是不会出现死循环 for (int binCount = 0; ; ++binCount) // 遍历该链表，知道知道下一个节点为null。 if ((e = p.next) == null) // 说明到链表尾部，然后把尾部的next指向新生成的对象 p.next = newNode(hash, key, value, null); // 如果链表的长度大于等于8 if (binCount > = TREEIFY_THRESHOLD - 1) // -1 for 1st // 则链表转化成为红黑树后面再补充 treeifyBin(tab, hash); break; // 如果在链表中找到了相同key的话，直接退出循环 if (e.hash == hash & & ((k = e.key) == key || (key != null & & key.equals(k)))) break; p = e; // 说明发生了碰撞，e代表的是旧值，需要替换为新值 if (e != null)// existing mapping for key V oldValue = https://www.songbingjia.com/android/e.value; // 判断是不是允许覆盖旧值，和旧值是否为空 if (!onlyIfAbsent || oldValue == null) // 把旧值替换 e.value = value; // hashmap没有任何实现，我们先不考虑 afterNodeAccess(e); // 返回新值 return oldValue; // fail-fast机制每次对结构改变进行+1 ++modCount; // 判断HashMap中的存的数据大小，如果大于数组长度*0.75，就要进行扩容 if (++size > threshold) resize(); // 也是一个空的实现 afterNodeInsertion(evict); return null;

4、resize方法解读
看不清查看原链接：高清图链接

文章图片

/** * 初始化或者是将table大小加倍,如果为空，则按threshold分配空间， * 否则加倍后，每个容器中的元素在新table中要么呆在原索引处，要么有一个2的次幂的位移 */ final Node< K,V> [] resize() // 原来的数据 Node< K,V> [] oldTab = table; // 获取原来的数组大小 int oldCap = (oldTab == null) ? 0 : oldTab.length; // 旧数组的扩容阈值，注意看，这里取的是当前对象的 threshold 值，下边的第2种情况会用到。 int oldThr = threshold; // 初始化新数组的容量和阈值 int newCap, newThr = 0; // 1.当旧数组的容量大于0时，说明在这之前肯定调用过 resize扩容过一次，才会导致旧容量不为0。 if (oldCap > 0) // 容量达到最大 if (oldCap > = MAXIMUM_CAPACITY) // 扩容的大小设置为上限 threshold = Integer.MAX_VALUE; // 直接返回默认原来的，无法在扩了 return oldTab; // 如果旧容量是在16到上限之间 else if ((newCap = oldCap < < 1) < MAXIMUM_CAPACITY & & oldCap > = DEFAULT_INITIAL_CAPACITY) // 新数组的容量和阈值都扩大原来的2倍 newThr = oldThr < < 1; // double threshold// 2. 到这里 oldCap < = 0， oldThr(threshold) > 0，这就是 map 初始化的时候， // 第一次调用 resize的情况 else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; // 3. 到这里，说明 oldCap 和 oldThr 都是小于等于0的。也说明我们的map是通过默认无参构造来创建的 else// zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; // 16 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 12// 只有经过2.才会进入 if (newThr == 0) float ft = (float)newCap * loadFactor; // 把计算后的ft符合大小，则赋值newThr newThr = (newCap < MAXIMUM_CAPACITY & & ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); // 最后得到要扩容的大小 threshold = newThr; // 用于抑制编译器产生警告信息 @SuppressWarnings("rawtypes","unchecked") // 在构造函数时，并没有创建数组，在第一次调用put方法，导致resize的时候，才会把数组创建出来。 // 这是为了延迟加载，提高效率。 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; // 如果第一个元素的下一个元素为null，说明链表只有一个 if (e.next == null) // 则直接用它的hash值和新数组的容量取模就行(这样运算效率高)，得到新的下标位置 newTab[e.hash & (newCap - 1)] = e; // 如果是红黑树 else if (e instanceof TreeNode) // 则拆分红黑树，这个小编就不带着往下深究了,感兴趣可以自己点进去看看 ((TreeNode< K,V> )e).split(this, newTab, j, oldCap); // 说明是链表且长度大于1 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; // 如果当前元素的hash值和oldCap做与运算为0，则原位置不变 if ((e.hash & oldCap) == 0) if (loTail == null) loHead = e; else loTail.next = e; loTail = e; // 不为0则把数据移动到新位置 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;

5、get和containsKey方法解读

/** * 根据key获取对应的value */ public V get(Object key) Node< K,V> e; // 调用后存在就获取元素的value返回 return (e = getNode(hash(key), key)) == null ? null : e.value; /** * 判断key是否在map中存在 */ public boolean containsKey(Object key) // 调用方法存在及不为null return getNode(hash(key), key) != null; /** * 我们发现底层都是getNode来进行干活的 */ final Node< K,V> getNode(int hash, Object key) Node< K,V> [] tab; Node< K,V> first, e; int n; K k; // 判断数组不能为空，然后取到当前hash值计算出来的下标位置的第一个元素 if ((tab = table) != null & & (n = tab.length) > 0 & & (first = tab[(n - 1) & hash]) != null) // 如果hash值和key都相等并不为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) // 则以红黑树的查找方式进行获取到我们想要的key对应的值 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); // 找不到key对应的值，返回null return null;

6、remove方法解读

/** * 如果key存在，就把元素删除 */ public V remove(Object key) Node< K,V> e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; /** * 删除方法的具体实现 * @param hash经过hash运算后的key * @param key你要移除的key * @param value你要移除的value * @param matchValue如果为真，则仅在值相等时删除，我们为FALSE，key相同即删除 * @param movable如果为假，则在删除时不要移动其他节点，我们为TRUE，删除移动其他节点 */ 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; // 判断table不为空，链表不为空 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 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 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; // p的下一个节点指向到node的下一个节点即可把node从链表中删除了 // 操作+1 ++modCount; // map大小-1 --size; // 空的实现 afterNodeRemoval(node); // 返回删除的节点 return node; return null;

六、总结Has和Map得底层还是很多的，里面用的一些逻辑和算法，都是很牛皮的、耐人琢磨的。oracle里的人才还是厉害啊，你看都看不明白，人家就能设计出来，实现出来。真的是你我皆为蝼蚁，只不过是一个个搬砖工具人呀。哈哈，对自己的一个自嘲哈，共勉！！看到这里了，点个赞吧，小编码字实属不易呀！！谢谢了！！
< hr>
部分注释理解来自于：参考博客
推广自己网站时间到了！！！
【HashMap底层原理及jdk1.8源码解读吐血整理1.3w字长文】点击访问！欢迎访问，里面也是有很多好的文章哦！