7000 字说清楚 HashMap，面试点都在里面了
我是风筝，公众号「古时的风筝」，一个兼具深度与广度的程序员鼓励师，一个本打算写诗却写起了代码的田园码农！ 文章会收录在 JavaNewBee 中，更有 Java 后端知识图谱，从小白到大牛要走的路都在里面。
这是上篇文章 有趣的条漫版 HashMap，25岁大爷都能看懂 的文字版。有不少同学说条漫版的比较有意思，简单易懂，但是毕竟图片画不了那么详细，只能从大面而上理解。
真正的了解细节，还得看这一篇。其实是这篇先写完，然后画了不少图片，所以就写了一篇图片版的。本篇 7000 多字，建议三连呦。
在 Java 中，最常用的数据类型是 8 中基本类型以及他们的包装类型以及字符串类型，其次应该就是 ArrayList和HashMap了吧。HashMap存的是键值对类型的数据，其存储和获取的速度快、性能高，是非常好用的一个数据结构，每一个 Java 开发者都肯定用过它。
而且 HashMap的设计巧妙，其结构和原理也经常被拿去当做面试题。其中有很多巧妙的算法和设计，比如 Hash 算法、拉链法、红黑树设计等，值得每一个开发者借鉴学习。
想了老半天，怎么才能简单易懂的把 HashMap说明白呢，那就从我理解它的思路和过程去说吧。要理解一个事物最好的方式就是先了解整体结构，再去追究细节。所以，我们先从结构谈起。
先从结构说起
拿我自身的一个体会来说吧，风筝我作为一个专业路痴，对于迷路这件事儿绝不含糊，虽然在北京混迹多年，但是只在中关村能分清南北，其他地方，哪怕是我每天住的小区、每天工作的公司也分不太清方向，回家只能认一条路，要是打车换条路回家，也得迷糊一阵，这么说吧，在小区前面能回家，小区后面找不到家。去个新地方，得盯着地图看半天。这时，我就在想啊，要是我能在城市上空俯瞰下面的街道，那我就再也不怕找不到回家的路了。这不就是三体里的降维打击吗，站在高维的立场，理解低维的事物，那就简单多了。
理解数据结构也是一个道理，大多数时候，我们都是停留在会用的层面上，理解一些原理也只是支离破碎的，困在数据机构的迷宫里跌跌撞撞，迫切的需要一张地图或者一架直升机。
先来看一下整个 Map家族的集成关系图，一看东西还不少，但其他的可能都没怎么用过，只有 HashMap最熟悉。
以下描述可能不够专业，只为简单的描述 HashMap的结构，请结合下图进行理解。
HashMap主体上就是一个数组结构，每一个索引位置英文叫做一个 bin，我们这里先管它叫做桶，比如你定义一个长度为 8 的 HashMap，那就可以说这是一个由 8 个桶组成的数组。当我们像数组中插入数据的时候，大多数时候存的都是一个一个 Node 类型的元素，Node 是 HashMap中定义的静态内部类。
当插入数据（也就是调用 put 方法）的时候，并不是按顺序一个一个向后存储的，HashMap中定义了一套专门的索引选择算法，叫做散列计算，但散列计算存在一种情况，叫哈希碰撞，也就是两个不一样的 key 散列计算出来的 hash 值是一致的，这种情况怎么办呢，采用拉链法进行扩展，比如图中蓝色的链表部分，这样一来，具有相同 hash 值的不同 key 即可以落到相同的桶中，又保证不会覆盖之前的内容。
但随着插入的元素越来越多，发生碰撞的概率就越大，某个桶中的链表就会越来越长，直到达到一个阈值，HashMap就受不了了，为了提升性能，会将超过阈值的链表转换形态，转换成红黑树的结构，这个阈值是 8 。也就是单个桶内的链表节点数大于 8 ，就会将链表变身为红黑树。
以上概括性的描述就是 HashMap的整体结构，也是我们进一步研究细节的蓝图。我们将从中抽取出几个关键点一一解释，从整体到细节，降维打击 HashMap。
接下来就是说明为什么会设计成这样的结构以及从单纯数组到桶内链表产生，接着把链表转换成红黑树的详细过程。
认清几个关键概念
存储容器
因为HashMap内部是用一个数组来保存内容的，数组定义如下：
transient Node<K,V>[] table;
Node 类型
table 是一个 Node类型的数组，Node是其中定义的静态内部类，主要包括 hash、key、value 和 next 的属性。比如之后我们使用 put 方法像其中加键值对的时候，就会转换成 Node 类型。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
TreeNode
前面说了，当桶内链表到达 8 的时候，会将链表转换成红黑树，就是 TreeNode类型，它也是 HashMap中定义的静态内部类。
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
}
容量和默认容量
容量就是 table 数组的长度，也就是我们所说的桶的个数。其定义如下
int threshold;
默认是 16，如果我们在初始化的时候没有指定大小，那就是 16。当然我们也可以自己指定初始大小，而 HashMap 要求初始大小必须是 2 的 幂次方。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
元素个数
容量是指定了桶的个数，而 size 是说 HashMap中实际存了多少个键值对。
transient int size;
最大容量
table 的长度也是有限制的，不能无限大，HashMap规定最大长度为 2 的30次方。
static final int MAXIMUM_CAPACITY = 1 << 30;
负载因子
这是一个系数，它和 threshold 结合起作用，默认是 0.75。一般情况下不要改。
final float loadFactor;
扩容阈值
阈值 = 容量 x 负载因子，假设当前 HashMap的容量是 16，负载因子是默认值 0.75，那么当 size 到达 16 x 0.75= 12 的时候，就会触发扩容。
初始化 HashMap
使用 HashMap肯定要初始化吧，很多情况下都是用无参构造方法创建。
Map<String,String> map = new HashMap<>();
这种情况下所有属性都是默认值，比如容量是 16，负载因子是 0.75。
另外推荐的一种初始化方式，就是给定一个默认容量，比如指定默认容量是 32。
Map<String,String> map = new HashMap<>(32);
但是 HashMap 要求初始大小必须是 2 的 n 次方，但是又不能要求每个开发人员指定初始容量的时候都按要求来，比如我们指定初始大小为为 7、18 这种会怎么样呢？
没关系，HashMap中有个方法专门负责将传过来的参数值转换为最接近、且大于等于指定参数的 2 的 n 次方的值，比如指定大小为 7 的话，最后实际的容量就是 8 ，如果指定大小为 18的话，那最后实际的容量就是 32 。
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);
}
执行这个转换动作的就是 tableSizeFor方法，经过转换后，将最终的结果赋值给 threshold变量，也就是初始容量，也就是本篇中所说的桶个数。
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;
}
tableSizeFor这个方法就有意思了，先把初始参数减 1，然后连着做或等于和无符号右移操作，最后算出一个接近的 2 的幂次方，下图演示了初始参数为 18 时的一系列操作，最后得出的初始大小为 32。
这个算法很有意思了，比如你给的初始大小是 63，那得到的结果就是 64，如果初始大小给定 65 ，那得到的结果就是 128，总是能得出不小于给定初始大小，并且最接近的2的n次方的最终值。
从 put 方法解密核心原理
put方法是增加键值对最常用的方法，也是最复杂的过程，增加键值对的过程涉及了 HashMap最核心的原理，主要包括以下几点：
- 什么情况下会扩容，扩容的规则是什么？
- 插入键值对的时候如何确定索引，
HashMap可不是按顺序插入的，那样不就真成了数组了吗。 - 如何确保 key 的唯一性？
- 发生哈希碰撞怎么处理？
- 拉链法是什么？
- 单桶内的链表如何转变成红黑树？
以下是 put 方法的源码，我在其中做了注释。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
HashMap.Node<K,V>[] tab; // 声明 Node 数组 tab
HashMap.Node<K,V> p; // 声明一个 Node 变量 p
int n, i;
/**
* table 定义 transient Node<K,V>[] table; 用来存储 Node 节点
* 如果 当前table为空，则调用resize() 方法分配数组空间
*/
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// n 总是为 2 的幂次方，(n-1) & hash 可确定 tab.length （也就是table数组长度）内的索引
// 然后 创建一个 Node 节点赋给当前索引
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//如果当前索引位置已经有值了，怎么办
// 拉链法出场
HashMap.Node<K,V> e;
K k;
// 判断 key 值唯一性
// p 是当前待插入索引处的值
// 哈希值一致并且（当前位置的 key == 待插入的key(注意 == 符号)，或者key 不为null 并且 key.equals(k)）
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))) //如果当前节点只有一个元素，且和待插入key一样 则覆盖
// 将 p（当前索引）节点临时赋予 e
e = p;
else if (p instanceof HashMap.TreeNode) // 如果当前索引节点是一颗树节点
//插入节点树中 并返回
e = ((HashMap.TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 当前索引节点即不是只有一个节点，也不是一颗树，说明是一个链表
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) { //找到没有 next 的节点，也就是最后一个
// 创建一个 node 赋给 p.next
p.next = newNode(hash, key, value, null);
// 如果当前位置+1之后大于 TREEIFY_THRESHOLD 则要进行树化
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//执行树化操作
treeifyBin(tab, hash);
break;
}
//如果又发生key冲突则停止 后续这个节点会被相同的key覆盖
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 当实际长度大于 threshold 时 resize
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
首次初始化数组和扩容
在执行 put方法时，第一步要检查 table 数组是否为空或者长度是否为 0，如果是这样的，说明这是首次插入键值对，需要执行 table 数组初始化操作。
另外，随之键值对添加的越来越多，HashMap的 size 越来越大，注意 size 前面说了，是实际的键值对数量，那么 size 到了多少就要扩容了呢，并不是等 size 和 threshold（容量）一样大了才扩容，而是到了阈值就开始扩容，阈值上面也说了，是容量 x 负载因子。
为什么放在一起说呢，因为首次初始化和扩容都是用的同一个方法，叫做 resize()。以下是我注释的 resize()方法。
final HashMap.Node<K,V>[] resize() {
// 保存 table 副本，接下来 copy 到新数组用
HashMap.Node<K,V>[] oldTab = table;
// 当前 table 的容量，是 length 而不是 size
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 当前桶大小
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) { //如果当前容量大于 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; // double threshold
}
else if (oldThr > 0) // 初始化的场景（给定默认容量），比如 new HashMap(32)
newCap = oldThr; //将容量设置为 threshold 的值
else { // 无参数初始化场景，new HashMap()
// 容量设置为 DEFAULT_INITIAL_CAPACITY
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"})
HashMap.Node<K,V>[] newTab = (HashMap.Node<K,V>[])new HashMap.Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
HashMap.Node<K,V> e;
//遍历 获得得到元素 赋给 e
if ((e = oldTab[j]) != null) { //如果当前桶不为空
oldTab[j] = null; // 置空回收
if (e.next == null) //节点 next为空的话 重新寻找落点
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof HashMap.TreeNode) //如果是树节点
//红黑树节点单独处理
((HashMap.TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // 保持原顺序
HashMap.Node<K,V> loHead = null, loTail = null;
HashMap.Node<K,V> hiHead = null, hiTail = null;
HashMap.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;
}
首次初始化
put方法中线先检查 table 数组是否为空，如果为空就初始化。
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
首次初始化分为无参初始化和有参初始化两种情况，前面在讲 HashMap初始化的时候说了，无参情况默认就是 16，也就是 table 的长度为 16。有参初始化的时候，首先使用 tableSizeFor()方法确定实际容量，最后 new 一个 Node 数组出来。
HashMap.Node<K,V>[] newTab = (HashMap.Node<K,V>[])new HashMap.Node[newCap];
其中 newCap就是容量，默认16或者自定义的。
而这个过程中还有很重要的一步，就是维护扩容阈值。
扩容
put方法中，判断当 size（实际键值对个数）到达 threshold （阈值）时，触发扩容操作。
// 当实际长度大于 threshold 时 resize
if (++size > threshold)
resize();
HashMap遵循两倍扩容规则，每次扩容之后的大小是扩容前的两倍。另外，说到底，底层的存储还是一个数组，Java 中没有真正的动态数组这一说，数组初始化的时候是多大，那它就一直是这么大，那扩容是怎么来的呢，答案就是创建一个新数组，然后将老数组的数据拷贝过去。
拷贝的时候可能会有如下几种情况：
- 如果节点 next 属性为空，说明这是一个最正常的节点，不是桶内链表，也不是红黑树，这样的节点会重新计算索引位置，然后插入。
- 如果是一颗红黑树，则使用
split方法处理，原理就是将红黑树拆分成两个 TreeNode 链表，然后判断每个链表的长度是否小于等于 6，如果是就将 TreeNode 转换成桶内链表，否则再转换成红黑树。 - 如果是桶内链表，则将链表拷贝到新数组，保证链表的顺序不变。
确定插入点
当我们调用 put方法时，第一步是对 key 进行 hash 计算，计算这个值是为了之后寻找落点，也就是究竟要插入到 table 数组的哪个桶中。
hash 算法是这样的，拿到 key 的 hashCode，将 hashCode 做一次16位右位移，然后将右移的结果和 hashCode 做异或运算，这段代码叫做「扰动函数」，之所以不直接拿 hashCode 是为了增加随机性，减少哈希碰撞次数。
/**
* 用来计算 key 的 hash 值
**/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
拿到这个 hash 值之后，会进行这样的运算 i = (n - 1) & hash，其中 i就是最终计算出来的索引位置。
有两个场景用到了这个索引计算公式，第一个场景就是 put方法插入键值对的时候。第二个场景是在 resize 扩容的时候，new 出来新数组之后，将已经存在的节点移动到新数组的时候，如果节点不是链表，也不是红黑树，而是一个普通的 Node 节点，会重新计算，找到在新数组中的索引位置。
接着看图，还是图说的清楚。
HashMap 要求容量必须是 2 的 n 次方，2的 n 次方的二进制表示大家肯定都很清楚，2的6次方，就是从右向左 6 个 0，然后第 7 位是 1，下图展示了 2 的 6 次方的二进制表示。
然后这个 n-1的操作就厉害了，减一之后，后面之前二进制表示中 1 后面的 0 全都变成了 1，1 所在的位变为 0。比如 64-1 变为 63，其二进制表示是下面这样的。
下图中，前面 4 行分别列出了当 map 的容量为 8、16、32、64的时候，假设容量为 n，则对应的 n-1 的二进制表示是下面这样的，尾部一片红，都是 1 ，能预感到将要有什么骚操作。
没错，将这样的二进制表示代入这个公式 (n - 1) & hash中，最终就能确定待插入的索引位了。接着看图最下面的三行，演示了假设当前 HashMap的容量为 64 ，而待插入的一个 key 经过 hash 计算后得到的结果是 99 时，代入公式计算 index 的值，也就是 （64-1）& 99，最终的计算结果是 35，也就是这个 key 会落到 table[35] 这个位置。
为什么 HashMap一定要保证容量是 2 的幂次方呢，通过二进制表示可以看出，如果有多位是 1 ，那与 hash 值进行与运算的时候，更能保证最后散列的结果均匀，这样很大程度上由 hash 的值来决定。
如何确保 key 的唯一性
HashMap中不允许存在相同的 key 的，那怎么保证 key 的唯一性呢，判断的代码如下。
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
首先通过 hash 算法算出的值必须相等，算出的结果是 int，所以可以用 == 符号判断。只是这个条件可不行，要知道哈希碰撞是什么意思，有可能两个不一样的 key 最后产生的 hash 值是相同的。
并且待插入的 key == 当前索引已存在的 key，或者 待插入的 key.equals(当前索引已存在的key)，注意== 和 equals 是或的关系。== 符号意味着这是同一个对象， equals 用来确定两个对象内容相同。
如果 key 是基本数据类型，比如 int，那相同的值肯定是相等的，并且产生的 hashCode 也是一致的。
String 类型算是最常用的 key 类型了，我们都知道相同的字符串产生的 hashCode 也是一样的，并且字符串可以用 equals 判断相等。
但是如果用引用类型当做 key 呢，比如我定义了一个 MoonKey 作为 key 值类型
public class MoonKey {
private String keyTile;
public String getKeyTile() {
return keyTile;
}
public void setKeyTile(String keyTile) {
this.keyTile = keyTile;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
MoonKey moonKey = (MoonKey) o;
return Objects.equals(keyTile, moonKey.keyTile);
}
}
然后用下面的代码进行两次添加，你说 size 的长度是 1 还是 2 呢？
Map<MoonKey, String> m = new HashMap<>();
MoonKey moonKey = new MoonKey();
moonKey.setKeyTile("1");
MoonKey moonKey1 = new MoonKey();
moonKey1.setKeyTile("1");
m.put(moonKey, "1");
m.put(moonKey1, "2");
System.out.println(hash(moonKey));
System.out.println(hash(moonKey1));
System.out.println(m.size());
答案是 2 ，为什么呢，因为 MoonKey 没有重写 hashCode 方法，导致 moonkey 和 moonKey1 的 hash 值不可能一样，当不重写 hashCode 方法时，默认继承自 Object的 hashCode 方法，而每个 Object对象的 hash 值都是独一无二的。
划重点，正确的做法应该是加上 hashCode的重写。
@Override
public int hashCode() {
return Objects.hash(keyTile);
}
这也是为什么要求重写 equals 方法的同时，也必须重写 hashCode方法的原因之一。 如果两个对象通过调用equals方法是相等的，那么这两个对象调用hashCode方法必须返回相同的整数。有了这个基础才能保证 HashMap或者HashSet的 key 唯一。
发生哈希碰撞怎么办
前面刚说了相等的对象产生的 hashCode 也要相等，但是不相等的对象使用 hash方法计算之后也有可能产生相同的值，这就叫做哈希碰撞。虽然通过算法已经很大程度上避免碰撞的发生，但是却无法避免。
产生碰撞之后，自然得出的在 table 数组的索引（也就是桶）也是一样的，这时，怎么办呢，一个桶里怎么放多个键值对？
拉链法
文章刚开头就提到了，HashMap可不是简单的数组而已。当碰撞发生就坦然接收。有一种方法叫做拉链法，不是衣服上那种拉链。而是，当碰撞发生了，就在当前桶上拉一条链表出来，这样解释就合理了。
前面介绍关键概念的时候提到了 Node类型，里面有个属性叫做 next，它就是为了这种链表设计的，如下图所示。node1、node2、node3都落在了同一个桶中，这时候就得用链表的方式处理了，node1.next = node2，node2.next = node3，这样将链表串起来。而 node3.next = null，则说明这是链表的尾巴。
当有新元素准备插入到链表的时候，采用的是尾插法，而不是头插法了，JDK 1.7 的版本采用的是头插法，但是头插法有个问题，就是在两个线程执行 resize() 扩容的时候，很可能造成环形链表，导致 get 方法出现死循环。
链表转换成树
链表不是碰撞处理的终极结构，终极结构是红黑树，当链表长度到达 8 之后，再有新元素进来，那就要开始由链表到红黑树的转换了。方法 treeifyBin是完成这个过程的。
使用红黑树是出于性能方面的考虑，红黑树的查找速度要优于链表。那为什么不是一开始就直接生成红黑树，而是链表长度大于 8 之后才升级成树呢？
首先来说，哈希碰撞的概率还是很小的，大部分情况下都是一个桶装一个 Node，即便发生碰撞，都碰撞到一个桶的概率那就更是少之又少了，所以链表长度很少有机会能到 8 ，如果链表长度到 8 了，那说明当前 HashMap中的元素数量已经非常大了，那这时候用红黑树来提高性能是可取的。而反过来，如果 HashMap总的元素很少，即便用红黑树对性能的提升也不大，况且红黑树对空间的使用要比链表大很多。
get 方法
T value = map.get(key);
例如通过上面的语句通过 key 获取 value 值，是我们最常用到的方法了。
看图理解，当调用 get方法后，第一步还是要确定索引位置，也就是我们所说的桶的位置，方法和 put方法时一样，都是先使用 hash这个 扰动函数 确定 hash 值，然后用 (n-1) & hash获取索引。这不废话吗，当然得和 put的时候一样了，不一样还怎么找到正确的位置。
确定桶的位置后，会出现三种情况：
单节点类型： 也就是这个桶内只有一个键值对，这也在 HashMap中存在最多的类型，只要不发生哈希碰撞都是这种类型。其实 HashMap最理想的情况就是这样，全都是这种类型就完美了。
链表类型： 如果发现 get 的 key 所在的是一个链表结构，就需要遍历链表，知道找到 key 相等的 Node。
红黑树类型： 当链表长度超过 8 就转变成红黑树，如果发现找到的桶是一颗红黑树，就使用红黑树专有的快速查找法查找。
另外，Map.containsKey方法其实用的就是 get方法。
remove 方法
remove与put、get方法类似，都是先求出 key 的 hash 值，然后 (n-1) & hash获取索引位置，之后根据节点的类型采取不同的措施。
单节点类型： 直接将当前桶元素替换为被删除 node.next ，其实就是 null。
链表类型： 如果是链表类型，就将被删除 node 的前一个节点的 next 属性设置为 node.next。
红黑树类型： 如果是一棵红黑树，就调用红黑树节点删除法，这里，如果节点数在 2~6之间，就将树结构简化为链表结构。
非线程安全
HashMap没有做并发控制，如果想在多线程高并发环境下使用，请用 ConcurrentHashMap。同一时刻如果有多个线程同时执行 put 操作，如果计算出来的索引（桶）位置是相同的，那会造成前一个 key 被后一个 key 覆盖。
比如下图线程 A 和 线程 B 同时执行 put 操作，很巧的是计算出的索引都是 2，而此时，线程A 和 线程B都判断出索引为 2 的桶是空的，然后就是插入值了，线程A先 put 进去了 key1 = 1的键值对，但是，紧接着线程B 又 put 进去了 key2 = 2，线程A 表示痛哭流涕，白忙活一场。最后索引为2的桶内的值是 key2=2，也就是线程A的存进去的值被覆盖了。
总结
前面没说，HashMap搞的这么复杂不是白搞的，它的最大优点就是快，尤其是 get数据，是 O(1)级别的，直接定位索引位置。
HashMap不是单纯的数组结构，当发生哈希碰撞时，会采用拉链法生成链表，当链表大于 8 的时候会转换成红黑树，红黑树可以很大程度上提高性能。
HashMap容量必须是 2 的 n 次方，这样设计是为了保证寻找索引的散列计算更加均匀，计算索引的公式为 (n - 1) & hash。
HashMap在键值对数量达到扩容阈值「容量 x 负载因子」的时候进行扩容，每次扩容为之前的两倍。扩容的过程中会对单节点类型元素进行重新计算索引位置，如果是红黑树节点则使用 split方法重新考量，是否将红黑树变为链表。
壮士且慢，先给点个赞吧，总是被白嫖，身体吃不消！
我是风筝，公众号「古时的风筝」。一个兼具深度与广度的程序员鼓励师，一个本打算写诗却写起了代码的田园码农！你可选择现在就关注我，或者看看历史文章再关注也不迟。
