前言
HashMap是Java程序员应用最多的数据结构之一，同时也是面试必问的知识点，随着JDK的进化与倒退，JDK 1.8也对底层实现进行了优化，例如引入红黑树的数据结构和扩容的优化等。本文将联合JDK 1.7和1.8的源码，深入探讨HashMap的构造实现和性能原理，篇幅有些长请急躁看完。
简介
HashMap和ArrayList一样也是继承一个实现一个，继承关系简直统一，只是把List换成了Map。
Java为数据结构中的映射定义了一个接口java.util.Map，此接口次要有四个罕用的实现类，别离是HashMap、HashTable、LinkedHashMap和TreeMap，HashMap类继承关系如下图所示：
基本原理
根本数据结构
HashMap的根本数据结构是数组 + 链表/红黑树，小规模状况下以数组 + 链表（相似于桶存储）为主，大量数据的时候会转换为红黑树，这里须要提的是何时会转换为红黑树，这是一个咱们必须要关注的问题，会在前面讲到。
put原理
在进行put源码剖析之前咱们须要先理解一个叫扰动函数的货色，用于计算存储的hash值。
// 扰动函数static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}从上述函数咱们能够看出几个比拟要害的信息：
- HashMap反对key为null存储，为null的时候返回为0。
- 如果间接拿散列值作为下标拜访HashMap主数组的话，思考到2进制32位带符号的int表值范畴从-2147483648到2147483648，很难呈现碰撞，不过这个hash值不能间接拿来用，因为hashmap的初始值才16。
- 如何解决hash值：在这之前会有一个函数叫做indexFor去解决，次要是联合长度进行模运算。在JDK8中这一操作被放到了putVal中间接解决。
- *
说完了扰动函数咱们正式进入put原理的剖析。
public V put(K key, V value) { return putVal(hash(key), key, value, false, true);}上述源码put函数最外层的办法，putVal为HashMap理论应用的办法，其实HashMap的源码很简单，其它的每一个局部都能写一篇文章，用来阐明如此精妙的数据结构是如何设计进去的。
putVal源码正文解析
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则执行resize，并将长度赋值给n，做必要的初始化 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) // 此处 & 代替了 % （除法散列法进行散列） // 如果hash进去的值为空，则新建一个结点并插入到指定地位（意思就是tab[i]的地位此时还没有数据插入） tab[i] = newNode(hash, key, value, null); // 这里的p结点是依据hash值算进去对应在数组中的元素，如果为空就代表还未插入。 else { Node<K,V> e; K k; // 如果插入的key雷同，进行笼罩操作 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)// -1 for 1st// 将链表转换成红黑树。treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; // 及时更新p p = e; } } // 如果e存在，就进行笼罩 if (e != null) {// existing mapping for keyV oldValue = e.value; // 判断是否容许笼罩，并且oldValue此时的状态 if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); // 回调以容许LinkedHashMap后置操作 return oldValue; } } ++modCount; // 更改操作次数 // 如果容量超标，则执行resize进行扩容 if (++size > threshold) resize(); // 完结Node插入之后的操作 afterNodeInsertion(evict); // 回调以容许LinkedHashMap后置操作 return null;}对于HashMap putVal 操作次要分为如下几个步骤：
1）初始化并筹备好结点。
2）判断须要进行的操作，进行创立赋值（雷同key，红黑树结点，链表操作）。
3）将创立玩的结点利用到Map中去。
4）容量检测。
这里咱们有几个关注点：
1）在数组中如何存储对应的结点数据：通过(n - 1) & hash计算出地位再放入的。
2）链表在什么时候会转换为红黑树：binCount 大于7的时候就会转换为红黑树，当其小于6的时候就会变会链表。
get原理
public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value;}利用key以及put时候的同款hash计算方法找到对应的值。
getNode返回一个数的数据结点，如果为空则返回null；
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 &&// 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;}1）通过 hash & (table.length - 1)获取该key对应的数据节点的hash槽。
2）判断首个结点是否为空，如果为空就间接返回null。
3）判断首个结点的hash是否与待查找的hash值雷同，如果雷同间接返回取出。
4）进入链表迭代的循环，流程图如下所示。
当Node为红黑树的状况下getNode返回的是key对应的红黑树节点。
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;}Hash碰撞
顾名思义就是多个值的hashCode计算雷同，都处于同以空间的时候，put的时候发生冲突。
在Java HashMap中采纳“拉链法”解决HashCode的碰撞问题，具体图片如下所示。
HashMap应用链表来解决碰撞问题，当碰撞产生了，对象将会存储在链表的下一个节点中。hashMap在每个链表节点存储键值对对象。当两个不同的键却有雷同的hashCode时，他们会存储在同一个bucket地位的链表中
红黑树
R-B Tree，全称是Red-Black Tree，又称为“红黑树”，它一种非凡的二叉查找树。红黑树的每个节点上都有存储位示意节点的色彩，能够是红(Red)或黑(Black)。
红黑树特色：
（1）每个节点或者是彩色，或者是红色。
（2）根节点是彩色。
（3）每个叶子节点（NIL）是彩色。[留神：这里叶子结点，是只为空的叶子结点！]
（4）如果一个节点是红色的，则它的子节点必须是彩色的。
（5）从一个节点到该节点的子孙节点的所有门路上蕴含雷同数目的黑结点。
下图就是一个简略的红黑树。
链表到红黑树的转换
// 链表转双向链表操作final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; // 如果元素总个数小于64，则持续进行扩容，结点指向调节 if (tab == null || (n = tab.length) <MIN_TREEIFY_CAPACITY) resize(); // 先找到那个链表的头 else if ((e = tab[index = (n - 1) & hash]) != null) { TreeNode<K,V> hd = null, tl = null; // hd：树头部 do { // 创立红黑树根结点 TreeNode<K,V> p = replacementTreeNode(e, null); if (tl == null) hd = p; else { p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) != null); if ((tab[index] = hd) != null) // 此处才是真正的转为红黑树（树化其实就是红黑树的创立，这里就不过多剖析了） hd.treeify(tab); }}上述是一个红黑树入口办法，当HashMap须要转换为红黑树的时候，此时便会进入这个办法。
1）当结点数量为空，或少于64个的时候会主动触发resize()。
2）递归构建TreeNode，构建实现调用treeify实现树化。
扩容机制
理解一个数据结构，咱们必须要晓得的就是其扩容算法，在HashMap之中通过resize实现扩容，接下来将解析resize的扩容机制。
final Node<K,V>[] resize() { // 取得旧元素数组的各种信息 Node<K,V>[] oldTab = table; // 获取旧容量长度 int oldCap = (oldTab == null) ? 0 : oldTab.length; // 扩容的临界点 int oldThr = threshold; // 定义新数组的长度，以及扩容的临界值 int newCap, newThr = 0; // 如果旧的容量 > 0 也就是原有table不为空。 if (oldCap > 0) { // 如果数组长度达到最大值，则批改临界值为Integer.MAX_VALUE if (oldCap >=MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } // 上面就是扩容操作（2倍） else if ((newCap = oldCap << 1) <MAXIMUM_CAPACITY&& oldCap >=DEFAULT_INITIAL_CAPACITY) // 阈值也变为二倍 newThr = oldThr << 1;} else if (oldThr > 0)// 旧阈值倍设置为新容量newCap = oldThr; else { // 如果是新的初始化，则cap设置为默认容量newCap =DEFAULT_INITIAL_CAPACITY; // 如果阈值设置为默认阈值 newThr = (int)(DEFAULT_LOAD_FACTOR*DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { // 如果临界值为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; // 最初返回新的table data；}下面就是一份残缺的扩容的源代码，总体分为两个局部：扩容新空间，调整原有数据的地位。我曾经在必要的中央进行了些许正文阐明，其实光看代码，有些问题咱们并不能晓得，接下来为将针对性的解决几个问题。
什么时候会触发resize呢？
影响HashMap触发resize的起因如下：
Capacity：以后HashMap的长度
LoadFactor：负载因子，默认值为0.75f。
当capacity > currentCapacity * LoadFactor的时候，就回去触发resize进行扩容。
如何扩容？
分为两步：
- 扩容新建一个新的数组，长度为原来的两倍（这一点在源码正文上有提到）。
- 把原数组，从新Hash过后放入新的数组中去。
为何是reHash之后寄存而不是间接寄存？
这一点须要联合咱们新增时候的hash扰动函数来说，(n - 1) & hash咱们在计算出地位的时候是通过n和hash之间的模运算得出的，如果此时咱们的n产生了变动还沿用以前的地位就会呈现找不到地位的状况，具体示意图如下所示。
扩容前的地位：
未扩容前，有一个容量为3的HashMap存储桶，此时其中的数据如下所示，此时须要对HashMap进行扩容。
如果扩容后间接复制过来：
如果未进行rehash，那么此时的地位如上图所示，而此时因为是曾经扩容实现的，那么getNode那边在获取到对应HashMap的size将是6，而不是原来的3，那么试想一下(6 - 1) & hash 等于 (3 - 1) & hash么？答案不言而喻是不等的，那么resize过后如果不从新resize，所有的以前的Node都拿不到了。
从新rehash之后的后果：
如果此时从新rehash了，就不会存在此类问题，能够间接获取到对应的值。
总结
HashMap这样的知识点还有很多，一篇文章是说不完的，所以我并没有介绍一些HashMap的基本知识，将更多的篇幅放在了一些比拟要害局部的介绍，至于更多的玄机须要咱们一起去摸索。
相干视频举荐：
【Android面试必问的HashMap源码解析】03-HashMap的表构造原理
【Android面试题精选】资深架构师带你逐题详解Android大厂精选高频面试题
)
本文转自 https://juejin.cn/post/6967650737429938183，如有侵权，请分割删除。