HashMap类图.png
0、HashMap 简介
HashMap是由数组、链表或红黑树组成的，应该是我们Java开发工作中用到的非常普遍的数据结构之一了，它以key-value键值对的形式进行存储。
HashMap是线程不安全的，如果你想使用线程安全的HashMap，那么请使用HashTable或者ConcurrentHashMap，主推ConcurrentHashMap，因为HashTable采用的是全表锁，效率低下，而Java 8里的ConcurrentHashMap采用的是节点锁，效率较高。
关于HashTable和ConcurrentHashMap我们后面会专门进行讲解。
1、HashMap 属性
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 默认初始容量
默认初始容量为16，必须是2的n次幂，HashMap在确定数组下标Index的时候，采用(length-1) & hash按位与的方式，只有当length为2的指数幂的时候才能较均匀的分布元素。
static final int MAXIMUM_CAPACITY = 1 << 30; 最大容量
必须是2的n次幂，最接近int最大值的2个指数幂用位运算符表示就是 1 << 30
static final float DEFAULT_LOAD_FACTOR = 0.75f; 默认加载因子
当构造函数中未指定加载因子时，使用的是0.75f这个默认值。
loadFactor加载因子是控制数组存放数据的疏密程度，loadFactor越趋近于1，那么 数组中存放的数据(entry)也就越多，也就越密，也就是会让链表的长度增加，loadFactor越小，也就是趋近于0，数组中存放的数据(entry)也就越少，也就越稀疏。
loadFactor太大导致查找元素效率低，太小导致数组的利用率低，存放的数据会很分散。loadFactor的默认值为0.75f是官方给出的一个比较好的临界值。
关于负载因子，我们在这里好好聊聊，当负载因子为 0.75 时，箱子中元素个数和概率的关系如下：
| 数量 | 概率 |
|---|---|
| 0 | 0.60653066 |
| 1 | 0.30326533 |
| 2 | 0.07581633 |
| 3 | 0.01263606 |
| 4 | 0.00157952 |
| 5 | 0.00015795 |
| 6 | 0.00001316 |
| 7 | 0.00000094 |
| 8 | 0.00000006 |
这就是为什么我们将0.75设为负载因子，同时针对箱子中链表长度超过8以后要做另外的优化（一是优化的概率较小，不一定能碰撞8次，二是优化过后的效率提升明显）。
所以，一般情况下负载因子不建议修改；同时如果在数量为8的链表的概率较大，则几乎可以认为是哈希函数设计有问题导致的。
static final int TREEIFY_THRESHOLD = 8; 树化阀值
节点对应的链表容量大于等于阀值时，链表转换为红黑树进行存储
static final int UNTREEIFY_THRESHOLD = 6; 树还原链表阀值
节点对应的红黑树容量小于等于阀值时，红黑树转换为链表进行存储
static final int MIN_TREEIFY_CAPACITY = 64; 最小的树形化容量
当链表的容量超过树化阀值时，一定会转换为红黑树吗？
不一定！因为在进行树化时，会判断当前HashMap的容量是否大于等于这个MIN_TREEIFY_CAPCITY
- 是，则进行链表的树化
- 否，会对HashMap（准确的说是tables数组）进行扩容，扩容时会对链表内节点再进行一次hash散列抖动，确定最终位置后，有可能链表的大小没有改变，那么很有可能在下次hash碰撞的时候进行树化或者再次扩容。
static class Node<K,V> 节点，真正存放键值对的节点
implements Map.Entry
Node的内部属性为：
- int hash 当前node的hash值
- K key 当前node对应的key，也就是存储的key
- V value 当前node对应的value，也就是存储的value
- Node<K,V> next 表示指向下一node的指针，hash值相同的node通过next进行遍历查找
Node的内部方法为：
-
Node(int hash, K key, V value, Node<K,V> next)有参构造函数 -
getKey()获取key值 -
getValue()获取value值 -
hashCode()通过对key和value的hashCode做 ^（异或操作）返回node的hashcode -
setValue()设置node值 -
equals()重写equals方法 - 要么内存地址一样 - 要么就是key && value 相等 -
toString()toString()方法
transient Node<K,V>[] table; tables数组
以Node数组的形式存放信息，在必要时会重新调整大小，但长度总是2的n次幂
transient Set<Map.Entry<K,V>> entrySet; 保存缓存的entrySet()
注意，使用了AbstractMap字段用于keySet()和values()。
transient int size; map中key-value的数量
这个数量没有用volatile修饰，因为没有实际意义，HashMap并不是线程安全的，所以也就没有必要用volatile修饰的必要。
transient int modCount; 被修改的次数
这个HashMap在结构上被修改的次数结构修改是指改变HashMap中映射的数量或修改其内部结构的次数。
此字段用于使HashMap集合视图上的迭代器快速失败。(见ConcurrentModificationException)。在迭代的时候不允许修改HashMap，就是用这个参数做校验的。
int threshold; 临界值，当实际大小(容量*填充因子)超过临界值时，会进行扩容
capacity * load factor
final float loadFactor; 加载因子
一般情况下负载因子不建议修改，它是衡量哈希表的空/满程度，一定程度上也能体现查询的效率，负载因子越大，意味着哈希表越满，越容易导致冲突，因而查询效率也就更低。
其计算公式为：负载因子 = 总键值对数 / 箱子数量
2、HashMap 构造函数
-
public HashMap(int initialCapacity, float loadFactor)有参构造函数
第一个参数是初始容量，第二个是加载因子- 对内置loadFactor赋值
- 经过taleSizeFor方法计算，得出离initialCapacity最近的2的正数次幂的数，然后赋值给threshold
-
public HashMap(int initialCapacity)有参构造函数
参数是初始容量大小，然后调用内部双参构造函数，加载因子为默认值0.75f -
public HashMap()无参构造函数
加载因子为默认值0.75f -
public HashMap(Map<? extends K, ? extends V> m)有参构造函数
参数是Map子类实例，加载因子为默认值0.75f
调用putMapEntries()方法，将Map子类实例的Entries放入到当前HashMap中
在调用前三种构造函数时，HashMap内部的tables数组并未初始化，tables采用的是lazy模式的，只有我们调用put时，才会对tables进行初始化。
在调用第四种构造函数时，HashMap需要将m存储的键值对"转存"到自己内部的tables数组，所以在putVal方法中会对tables数组进行初始化（resize）。
3、HashMap 核心解读
3.1 我们从从下面代码进行解读
public class OneTest {
@Test
public void test() {
Map<String, String> map = new HashMap();
map.put("k1", "v1");
map.get("k1");
}
}
上面代码很简单，使用HashMap无参构造，实例化一个HashMap，然后进行put和get操作
解读：
3.1.1 通过HashMap的空构造函数示例化了一个对象map
HashMap空构造函数源代码如下：
public HashMap() {
// 加载因子使用默认的 0.75f
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
3.1.2 map调用put()方法，存入键值对
HashMap.put()源码如下：
public V put(K key, V value) {
// 在调用putVal方法时，首先获取key的hash值
return putVal(hash(key), key, value, false, true);
}
hash方法的源码：
/**
* hashCode的高16位不变，低16位与高16位做一个异或。
* 这样做的目的是同时把高16位和低16位的影响都考虑进来以减少小容量HashMap的散列冲突。
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
putVal方法的源码：
/**
* 向HashMap存储键值对
* @param hash 经过计算的key的hash值
* @param key 对应的key
* @param value 要存储的value
* @param onlyIfAbsent 如果为true不改变存在的值
* @param evict 如果为false则处于创建模式
* @return 旧值，如果没有则为空
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
// 局部变量
Node<K,V>[] tab;
Node<K,V> p;
// ntables数组长度
int n, i;
// 判断当前内部的tables数组是否已初始化
if ((tab = table) == null || (n = tab.length) == 0)
// 内部tables数组初始化
n = (tab = resize()).length;
// 经过hash散列抖动得出下标，不存在对应值，直接进行赋值
if ((p = tab[i = (n - 1) & hash]) == null)
// 直接进行赋值操作
tab[i] = newNode(hash, key, value, null);
// 很不幸，即便对hash进行了散列抖动，但是依然发生了hash碰撞
else {
Node<K,V> e;
K k;
/*
已存在的头节点hash值和传入的hash值是否相等 && key是否相等
- 是 表示要进行覆盖操作
- 否 表示就是单纯的hash碰撞
*/
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);
/*
是否大于树化阀值
- 是 转为红黑树
- 否 break循环即可
*/
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 = e;
}
}
// 是否存在覆写的情况，存在则返回旧值
if (e != null) { // existing mapping for key
V oldValue = e.value;
/*
!onlyIfAbsent（即是否不改变存在的值）或者 oldValue为null 都要进行覆写操作
*/
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// 为LinkedHashMap留的后路？
afterNodeAccess(e);
return oldValue;
}
}
// 覆写操作不累加修改次数
++modCount;
/*
存储后的容量是否大于临界值
- 是 进行扩容操作
*/
if (++size > threshold)
resize();
// 为LinkedHashMap留的后路？
afterNodeInsertion(evict);
return null;
}
resize方法源码：
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* tables 扩容 || 初始化
*
* @return the table
*/
final Node<K,V>[] resize() {
// 局部变量
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
/*
局部变量存储当前`临界值`
两种可能
- 调用无餐构造，默认的为0
- 传递了初始容量，然后在构造函数里计算出来的
*/
int oldThr = threshold;
// 新的数组容量、下次数组调整的大小
int newCap, newThr = 0;
// step-1 如果数组长度大于0 说明不是第一次进来
if (oldCap > 0) {
/*
判断如果tables数组的长度大于 1<<30（即2的30次幂）
说明已经是最大长度了，无法再扩容了
*/
if (oldCap >= MAXIMUM_CAPACITY) {
// 将`下次调整数组大小的阀值`设置为Integer.MAX_VALUE （即int最大值，2的31幂）
threshold = Integer.MAX_VALUE;
// 返回现有的tables数组
return oldTab;
}
/*
如果当前数组的容量，向左位移1位后小于最大容量 && 当前数组大于或等于默认初始容量
那么将原threshold向左位移1位得到的数赋值给newThr
*/
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// step-2 第一次进来，说明在实例化时传递了初始容量大小
else if (oldThr > 0)
// 将`临界值`赋值给newCap
newCap = oldThr;
// step-3 第一次进来
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
threshold = newThr;
// 实例化一个容量为newCap的数组
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
// 将tables指针指向newTab
table = newTab;
/*
这里就是判断是否第一次进来
- 是，直接将上面实例化后的数组返回
- 否，需要将原数组的内容"转移"到新数组里
*/
if (oldTab != null) {
// 循环将数据导入到新数组
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
// 数组的每一个格子并不一定会被使用，所以需要判断，当前的下标是否存在数据
if ((e = oldTab[j]) != null) {
// 将原数组格子清空
oldTab[j] = null;
// 如果当前node没有链表，也就是说这个下标未发生key的hash碰撞
if (e.next == null)
// 将原值导入到新数组对应的位置
newTab[e.hash & (newCap - 1)] = e;
// 如果当前node的类型为树节点（红黑树）
else if (e instanceof TreeNode)
// 将树节点的数据导入到新数组对应的位置
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 当前node为链表状了
else {
// 下标不变的头结点、尾节点
Node<K,V> loHead = null, loTail = null;
// 下标发生变化的头结点、尾节点
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// 遍历链表
do {
// 当前节点的下一个node节点
next = e.next;
/*
这行代码我愣是看了好长时间，一直在推敲这行代码的意义
后来想通了，扩容以后，数组的长度增加了，会影响改变到hash散列抖动后的下标
也就是说，在原数组里发生hash碰撞的key，在新数组里可能不再发生碰撞，所以要重新计算一下节点下标是否发生了变化
在put时确定数组下标的代码是这样的：
(length - 1) & hash
*/
// 下标不变
if ((e.hash & oldCap) == 0) {
// 尾节点为null 赋值头结点=当前节点
if (loTail == null)
loHead = e;
// 尾节点不为null 赋值尾节点=当前节点
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;
// 原下标+oldCap 放到新数组里
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
-
因为tables数组还未初始化，所以会对当前HashMap的
tables进行扩容操作。 -
进入resize方法内部，
tables数组还未初始化，即oldCap为0，实例化对象时，调用的是空构造函数，在空构造函数并未对threshold进行相关赋值，即oldThr为0，进入step-3分支。 -
step-3步骤中：
-
对新数组容量变量
newCap，赋值为默认的初始容量（16） -
对触发扩容的条件变量
newThr赋值为(int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY
-
-
将HashMap的
threshold指向newThr -
初始化容量为
newCap的新数组，并将tables指向newTab -
将新数组
newTab返回 -
==resize方法结束==
-
key的hash值和数组长度-1进行按位与计算，得出下标，不存在对应值，直接进行赋值操作
-
累加修改次数
-
判断存储后的HashMap容量是否大于threshold（临界值）
-
return null
3.1.3 map调用get()方法，获取key对应的value。
-
get()方法源码：
/** * 通过key获取value，如果key没有对应的值，则返回null */ public V get(Object key) { Node<K,V> e; // 首先获取key的hash值 return (e = getNode(hash(key), key)) == null ? null : e.value; } -
getNode方法源码：
/** * Implements Map.get and related methods. * 通过hash 和 key 获取node */ 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 while循环找到对应的节点 do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }get()方法其实并不难，只是在getNode方法里需要注意节点类型即可。
知识点总结：
HashMap
基于数组实现的散列表，继承于AbstractMap骨架抽象类（此类是为了减少实现Map接口需要做的工作量），实现Map接口。以key-value的形式进行put，以key的形式get
1、容量
默认初始容量16，且容量都是2的n次幂整数，用户可以在调用构造函数时，传递一个容量数值，假使传递的是3，实际的HashMap容量是4而不是3。
因为在构造函数里，有调用tableSizeFor(int)方法，此方法的源码如下：
static final int tableSizeFor(int cap) {
/*
为什么要减1？
因为如果我们传递8，如果不减1，就会返回16，所以在进行计算之前进行了-1的操作
*/
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;
}
这个方法的目的在于返回大于（输入参数-1）且最近的2的整数次幂的数。
在HashMap第一次进行put的时候，会初始化保存数据的数组（table）大小。
ps：不包括调用
public HashMap(Map<? extends K, ? extends V> m)构造函数，因为在这个构造函数里，会对table进行初始化。公式为((float)m.size() / loadFactor) + 1.0F
2、加载因子 & 扩容
提到扩容，必须提到loadFactor（加载因子），这个加载因子是什么意思呢？又在哪里用到呢？
作为一般规则，默认负载因子（.75）是时间和空间成本之间的良好折中。 更高的值会降低空间开销，但会增加查找成本。
在调用构造函数时，用户可以传递加载因子（float），如不传，默认是.75f
使用到的地方：
1、 public HashMap(Map<? extends K, ? extends V> m)构造函数
传递一个Map类型的实例，并将次m的所有元素放入HashMap，其内部调用了putMapEntries(Map<? extends K, ? extends V> m, boolean evict)。
putMapEntries源码：
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
// 获取传入的map容量大小
int s = m.size();
// 如果容量大于0才进行操作
if (s > 0) {
/*
为什么加上 table == null判断，因为HashMap有个构造函数就是传递Map实例，进行实例化的，在实例化期间，table肯定weinull
*/
if (table == null) { // pre-size
/*
为了避免再次扩容，采用的是((实际存储容量 / 加载因子) + 1)的公式，来获取初步的HashMap容量
为什么+1？因为在putVal中，++size > threshold 就会触发resize操作，如果不+1，就会产生两次扩容，影响性能和效率
*/
float ft = ((float)s / loadFactor) + 1.0F;
// 得到最终的HashMap容量，如果大于内置的最大容量阀值，则使用最大阀值
int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);
// 这条件判断为什么要加上，是为了以防万一吗？
if (t > threshold)
/*
获取离t最近的2的整数次幂的数
赋值临界值
*/
threshold = tableSizeFor(t);
}
// 如果不是初始化时传递Map实例，则判断map容量是否大于下次调整的值
else if (s > threshold)
// 调整HashMap大小
resize();
// 将Map实例的key 和value全部导入到当前的HashMap中
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
在放入m的所有元素前，HashMap会对内部的table进行初始化，容量的大小是通过公式((float)m.size() / loadFactor) + 1.0F得出的。
这里用到了loadFactor
2、HashMap的扩容方法resize()
在HashMap扩容时，通过加载因子计算出下一次扩容的触发临界值（threshold属性）。
3、在反序列化HashMap时
有兴趣可以看看源码里的readObject方法。
从上，我们知道了，加载因子的作用，就是通过公式容量 * 加载因子而计算出触发HashMap扩容的临界值。
网上有一道经典的HashMap扩容面试题：
准备用HashMap存1w条数据，构造时传1w还会触发扩容吗？
解析题目：
- 调用HashMap的构造函数并传递10000作为HashMap的容量，同时计算出threshold（触发扩容临界值）的数值为16384（调用了tableSizeFor方法得出的）。
- 在第一次put的时候会触发HashMap的扩容，初始化数组容量大小（newCap）为threshold（源码就是这么写的）即16384，同时重新赋值threshold为
16384*0.75f即12288，也就是说，触发下次HashMap扩容的临界值是12288。 - 当我们put到第1w条数据时，由于10000 < 12288，所以不会触发HashMap的扩容机制。
ps：如果在构造时传小于（1w / 16384）的加载因子，在put时，是可以触发扩容机制的。
3、存储key-value
HashMap底层是采用数组+链表or红黑树来存储数据的，通过计算出key的散列值，来确定数组的存储位置（下标）。
key 和 value 都可以为null
3.1 put
hash方法源码：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
因为key的hashCode为int型，也就是4个字节，32位，所以HashMap在计算散列值时，使用高16位和低16位做异或，这样做的目的是同时把高16位和低16位的影响都考虑进来以减少小容量HashMap的散列冲突。
当进行put操作时，计算出key的hash值后与(table.length - 1)做 &（按位与）得出数组的存储位置（下标）。
3.2 hash冲突
我们知道，即使我们散列值的再均匀分散，也有可能会产生冲突，如果hash冲突，HashMap会怎么处理呢？
在数据结构的相关书籍中有介绍，解决这种冲突的方法有几种，分离链接法（链表法）、开放地址法、再散列和公共溢出区。
而HashMap采用的是分离链接法，但是我这里说采用分离链接法是不准确的，因为Java 8的HashMap采用的是链表 + 红黑树（当链表长度超过8 且 当前table的长度大于64时会将链表转化为红黑树进行存储）。
Java 7里的HashMap采用的是纯正的分离链接法，且插入链表的方式是头插，Java 8 插入链表的的方式是尾插
3.3 尾插法
为什么Java 8采用尾插？
因为在Java 7的HashMap在多线程并发的场景下，执行扩容会导致环形链，在之后调用get方法或者扩容，会产生死循环的bug（可以称之为bug，即使HashMap宣称了自己是线程不安全的，但是这个死循环却是设计理念引起的，而不是共享资源引起的）。
具体原因就是因为使用了头插法，想了解原理可以查阅Java 7扩容方法源码。
Java 8 采用尾插法可以避免死循环的bug，但是，在多线程的情况下，依然是线程不安全的。
3.4 树化
为什么在链表长度大于8 & table.length >= MIN_TREEIFY_CAPACITY(64)，将链表转换为红黑树。
链表长度为什么大于8？而不是6、10、16、20等等？这其实是和加载因子有点关系。
在源码中有这样一段注释
Because TreeNodes are about twice the size of regular nodes, we
use them only when bins contain enough nodes to warrant use
(see TREEIFY_THRESHOLD). And when they become too small (due to
removal or resizing) they are converted back to plain bins. In
usages with well-distributed user hashCodes, tree bins are
rarely used. Ideally, under random hashCodes, the frequency of
nodes in bins follows a Poisson distribution
(http://en.wikipedia.org/wiki/Poisson_distribution) with a
parameter of about 0.5 on average for the default resizing
threshold of 0.75, although with a large variance because of
resizing granularity. Ignoring variance, the expected
occurrences of list size k are (exp(-0.5) * pow(0.5, k) / factorial(k)).
The first values are:
0: 0.60653066
1: 0.30326533
2: 0.07581633
3: 0.01263606
4: 0.00157952
5: 0.00015795
6: 0.00001316
7: 0.00000094
8: 0.00000006
more: less than 1 in ten million
- 理想情况下，在随机哈希码下，节点出现的频率在table桶中遵循泊松分布。当加载因子是0.75f时，碰撞8次的概率微乎其微。
- 同时针对箱子中链表长度超过8以后要做另外的优化（一是优化的概率较小，不一定能碰撞8次，二是优化过后的效率提升明显）。
如果table.length < MIN_TREEIFY_CAPACITY(64)，那么会触发HashMap扩容机制，table的长度调整为现table长度的2倍，扩容后会重新计算桶中各节点的新位置下标。
初始化传入的容量为32
+---+
| 0 |
+---+
+---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+
| 1 | -> |i1 | -> |i2 | -> |i3 | -> |i4 | -> |i5 | -> |i6 | -> |i7 | -> |i8 |
+---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+
+---+
| 2 |
+---+
+---+
| 3 |
+---+
more than...
在put i9到下标为1的桶中时，会触发是否转换为红黑树的条件判定，最后得出，需要对当前table进行扩容，扩容后重新计算桶中各节点的新位置下标，有可能是下面的情况：
+---+
| 0 |
+---+
+---+ +---+ +---+ +---+ +---+
| 1 | -> |i1 | -> |i2 | -> |i3 | -> |i4 |
+---+ +---+ +---+ +---+ +---+
+---+ +---+ +---+ +---+ +---+
| 2 | -> |i5 | -> |i6 | -> |i7 | -> |i8 |
+---+ +---+ +---+ +---+ +---+
+---+
| 3 |
+---+
实际情况会产生各种各样的情况，这里我只是举个例子。这样一来put i9到下标为1的桶中时，就不会将桶1中的链表转换为红黑树。
3.5 回归链表存储
当我们某个桶中的红黑树容量退化到UNTREEIFY_THRESHOLD（6）时，会将红黑树转化为链表进行存储。
remove方法和红黑树节点的拆分方法，会触发校验是否退回到链表。
网友评论