hashmap
承灿 2023/9/14
# HashMap底层源码解析
# 1. HashMap的基本特性
- HashMap存储键值对实现快速存取，允许为null。key值不可重复，若key值重复则覆盖。
- 非同步，线程不安全。
- 底层是hash表，不保证有序(比如插入的顺序)
# 2. HashMap简介
① JDK1.8 之前 HashMap 由 数组+链表 组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的，当一个元素放入集合时，会计算key的Hash值，即hash(key)，然后对数组的大小进行按位与运算计算一个桶下标（索引）。将key放入数组对应的桶下标索引处，将key尽可能的分散在不同的桶下标下面，可以让查找更加快速，时间复杂度为O(1)， 但是不同的key也有可能计算出相同的桶下标（索引），此时需要通过equals()方法来查找key，虽然查找性能会有损失，但是可以解决桶下标冲突。
死链的并发问题会发在扩容的时候，随着数组内元素越来越多，必然导致链表的长度也越来越长，查找性能就会受到影响，jdk7和jdk8都是在数组长度超过一个阈值时就会发生扩容，这个阈值就是数组的长度的四分之三（12）发生扩容，扩容的方式会重新计算桶下标，让容量翻倍。
② JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（或者红黑树的边界值，默认为 8）并且当前数组的长度大于64时，此时此索引位置上的所有数据改为使用红黑树存储。
哈希冲突：两个不同的key经过hash函数计算出相同的桶下标索引
# 3. 成员变量和构造函数
//当桶(bucket)上的结点数大于8时会转成红黑树
static final int TREEIFY_THRESHOLD = 8;
//当桶(bucket)上的结点数小于这个值时树转链表
static final int UNTREEIFY_THRESHOLD = 6;
//桶中结构转化为红黑树对应的数组长度最小的值
static final int MIN_TREEIFY_CAPACITY = 64;
//集合的初始化容量为16，初始化容量一定是2的n次幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//集合最大容量的上限是：2的30次幂
static final int MAXIMUM_CAPACITY = 1 << 30;
//负载因子默认大小
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//存储元素的数组，长度必须是2的n次幂
transient Node<K,V>[] table;
//存放元素的个数，注意这个不等于数组的长度。
transient int size;
//HashMap被改变的次数
transient int modCount;
//临界值 当实际大小(容量*负载因子)超过临界值时，会进行扩容
int threshold;
//存储负载因子的常量
final float loadFactor;
//默认的构造函数
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//指定容量大小的构造函数
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/*
指定“容量大小”和“加载因子”的构造函数
initialCapacity: 指定的容量
loadFactor:指定的加载因子
*/
public HashMap(int initialCapacity, float loadFactor) {
//判断初始化容量initialCapacity是否小于0
if (initialCapacity < 0)
//如果小于0，则抛出非法的参数异常IllegalArgumentException
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
//判断初始化容量initialCapacity是否大于集合的最大容量MAXIMUM_CAPACITY-》2的30次幂
if (initialCapacity > MAXIMUM_CAPACITY)
//如果超过MAXIMUM_CAPACITY，会将MAXIMUM_CAPACITY赋值给initialCapacity
initialCapacity = MAXIMUM_CAPACITY;
//判断负载因子loadFactor是否小于等于0或者是否是一个非数值
if (loadFactor <= 0 || Float.isNaN(loadFactor))
//如果满足上述其中之一，则抛出非法的参数异常IllegalArgumentException
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
//将指定的加载因子赋值给HashMap成员变量的负载因子loadFactor
this.loadFactor = loadFactor;
/*
tableSizeFor(initialCapacity) 判断指定的初始化容量是否是2的n次幂，如果不是那么会变为比指定初始化容量大的最小的2的n次幂。
但是注意，在tableSizeFor方法体内部将计算后的数据返回给调用这里了，并且直接赋值给threshold边界值了。有些人会觉得这里是一个bug,应该这样书写：
this.threshold = tableSizeFor(initialCapacity) *this.loadFactor;
这样才符合threshold的意思（当HashMap的size到达threshold这个阈值时会扩容）。
但是，请注意，在jdk8以后的构造方法中，并没有对table这个成员变量进行初始化，table的初始化被推迟到了put方法中，在put方法中会对threshold重新计算
*/
this.threshold = tableSizeFor(initialCapacity);
}
/**
Returns a power of two size for the given target capacity.
返回比指定初始化容量大的最小的2的n次幂
*/
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;
}
# 3.1 为什么初始化容量必须是2的n次方？
① 先生成 key 的哈希值（必须是整数）
② 再让 key 的哈希值跟数组的大小进行相关运算，生成一个索引值
③ 为了提高效率，可以使用 & 位运算取代 % 运算【前提：将数组的长度设计为 2 的幂（2^n） 】
static final int hash(Object key) {
return hash_code(key) % table.length;
}
static final int hash(Object key) {
return hash_code(key) & (table.length-1);
}
让hash_code(key)与全1相与，得出的索引下标一定小于数组的长度，并且可以减少Hash碰撞
1 2^1-1
11 2^2-1
111 2^3-1
1111 2^4-1
1100 1011 1100 0010
& 1111 & 1111
--------------------- ----------------
1011 0010
HashMap 容量为2次幂的原因，让哈希值更加均匀分布 → 减少哈希冲突次数 → 提升哈希表的性能 。如果n不是2的幂次方，可能数组的一些位置永远不会插入数据，浪费数组的空间，加大hash冲突。
# 3.2 如果数组容量不是2的n次方？
如果创建HashMap对象时，输入的数组长度是10，不是2的幂，HashMap通过位移运算和或运算得到的肯定是2的幂次数，并且是离那个数最近的数字。
//HashMap的带参构造函数
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
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的n次方，会调用这个方法将集合的容量增至大于等于initialCapacity)的最小的2的幂
this.threshold = tableSizeFor(initialCapacity);
}
/**
当在实例化HashMap实例时，如果给定了initialCapacity( 10)，由于HashMap的capacity必须都是2的幂，
因此这个方法用于找到大于等于initialCapacity(10)的最小的2的幂
（initialCapacity如果就是2的幂，则返回的还是这个数）
*/
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. HashMap的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) {
//transient Node<K,V>[] table; 表示存储Map集合中元素的数组。
Node<K,V>[] tab;
Node<K,V> p;
//n代表数组的长度
int n, i;
// ① 将table赋值给tab,并判断是否为null，第一次赋值时肯定为null
// ② 将tab.length赋值给n，并判断是否为0
if ((tab = table) == null || (n = tab.length) == 0)
//③ 由于数组为tab==null，对数组进行初始化，并将初始化后的数组长度赋值给n
//④ 执行n = (tab = resize()).length，数组tab每个空间都是null
n = (tab = resize()).length;
// ① i = (n - 1) & hash 表示计算数组的索引赋值给i，即确定元素存放在哪个桶中
// ② p = tab[i = (n - 1) & hash] 将计算出的数组索引对应的数据赋值给节点p
// ③ 判断p是否为null，即当前桶没有哈希冲突，则直接把键值对插入空间位置
if ((p = tab[i = (n - 1) & hash]) == null)
// ④ 根据键值对创建新的节点放入该位置的桶中
// p表示tab[i]，即 newNode(hash, key, value, null)方法返回的Node对象。
tab[i] = newNode(hash, key, value, null);
else {
// ① 执行else说明p=tab[i]不等于null，表示这个位置已经有值了，
Node<K,V> e; K k;
// ② p.hash == hash：比较桶中元素的hash值和新添加元素key的hash值是否相等
// ③ (k = p.key) == key：比较两个key的地址值是否相等
// ④ (key != null && key.equals(k))：能够执行到这里说明两个key的地址值不相等，那么先判断后 添加的key是否等于null，如果不等于null再调用equals方法判断两个key的内容是否相等
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
// 两个元素哈希值相等，并且key的值也相等，将旧的元素整体对象赋值给e，用e来记录
e = p;
// hash值不相等或者key不相等；判断p是否为红黑树结点
else if (p instanceof TreeNode)
// 放入树中
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// hash值不相等或者key不相等，说明是链表节点
else {
// 如果hash(key)不相同，说明是计算的桶下标相同，key也不相同，说明直接插在链表最后
for (int binCount = 0; ; ++binCount) {
// ① e = p.next 获取p的下一个元素赋值给e
// ② 判断p.next是否等于null，等于null，说明p没有下一个元素
// ③ 到达了链表的尾部，还没有找到重复的key,说明HashMap没有包含该键，将该键值对插入链表中
if ((e = p.next) == null) {
//④ 创建一个新的节点插入到尾部
p.next = newNode(hash, key, value, null);
//① 节点添加完成之后判断此时节点个数是否大于临界值8，如果大于则将链表转换为红黑树
//② binCount从0开始计数，TREEIFY_THRESHOLD - 1=7
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//转换为红黑树
treeifyBin(tab, hash);
break;
}
// ① e = p.next 不是null，不是最后一个元素。
// ②继续判断链表中结点的key值与插入的元素的key值是否相等
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
// 相等，跳出循环
//要添加的元素和链表中的存在的元素的key相等了，则跳出for循环。
//不用再继续比较了，直接执行下面的if语句去替换去 if (e != null)
break;
//说明新添加的元素和当前节点不相等，继续查找下一个节点。
// 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表
p = e;
}
}
/*
表示在桶中找到key值、hash值与插入元素相等的结点
也就是说通过上面的操作找到了重复的键，所以这里就是把该键的值变为新的值，并返回旧值
这里完成了put方法的修改功能
*/
if (e != null) {
// 记录e的value
V oldValue = e.value;
// onlyIfAbsent为false或者旧值为null
if (!onlyIfAbsent || oldValue == null)
//用新值替换旧值:e.value 表示旧值 value表示新值
e.value = value;
// 访问后回调
afterNodeAccess(e);
// 返回旧值
return oldValue;
}
}
//修改记录次数
++modCount;
// 判断实际大小是否大于threshold阈值，如果超过则扩容
if (++size > threshold)
resize();
// 插入后回调
afterNodeInsertion(evict);
return null;
}
根据源码分析详解下面的添加过程：
public class Test01 {
public static void main(String[] args) {
HashMap<String, Integer> map = new HashMap<>(10);
map.put("柳岩", 18);
map.put("杨幂", 28);
map.put("郑爽", 20);
map.put("柳岩", 20);
map.put("童谣", 19);
map.put("童谣", 25);
}
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// ① 由于数组为tab==null，对数组进行扩容并初始化，并将初始化后的数组长度赋值给n
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// ② 通过 hash(key)& (tabel.length-1)得出key映射的桶下标索引
if ((p = tab[i = (n - 1) & hash]) == null){
tab[i] = newNode(hash, key, value, null);
}
//修改记录次数
++modCount;
//判断size是否大于threshold，如果大于则扩容
if (++size > threshold){
resize();
}
afterNodeInsertion(evict);
return null;
}
① 判断数组是否为null，如果数组为null，对数组进行扩容并初始化
② 计算hash(key)并将其与数组长度-1进行与运算得出key对应的桶下标索引
③ 如果该索引处元素位null，说明没有出现hash冲突，直接将key和value创建成一个新的节点插入到当前位置即可
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// ① 判断数组是否为Null，如果为null对数组进行扩容，并初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// ② 计算要插入数据key映射的桶下标索引，如果索引位置处数据为null，没有hash碰撞，直接插入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// ③ 如果索引位置处有数据，说明要插入的数据和桶下标索引处的数据的key对应的桶下标相同，存在hash冲突
else {
Node<K,V> e; K k;
//① 如果数组桶下标处数据的hash值和要添加元素处的hash值相同，并且key的地址相同或者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 = e;
}
}
// ④ 满足第一个 if 条件，hash值形同，key的地址值相同，说明key相同，值覆盖
if (e != null) {
// existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// ① 判断数组是否为Null，如果为null对数组进行扩容，并初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// ② 计算要插入数据key映射的桶下标索引，如果索引位置处数据为null，没有hash碰撞，直接插入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// ③ 如果索引位置处有数据，说明要插入的数据和桶下标索引处的数据的key对应的桶下标相同，存在hash冲突
else {
Node<K,V> e; K k;
// ① 如果索引处数据的hash值和要添加元素处的hash值相同，并且key的地址相同或者key本身相同
// 柳岩和童谣尽管计算出的桶下标索引相同，但是key的地址值不相同，因此不走这个if逻辑
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);
// ③走到这儿：桶中元素(首节点)的hash值和新添加元素key的hash值不相同或者key的地址值不相同
else {
//遍历这个链表，bitCount用来记录添加的节点数，不加已有的数组中的那个元素
for (int binCount = 0; ; ++binCount) {
//如果到大链表末尾后，链表中也没有重复的key，将key和value构建成节点直接添加到链表末尾
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//添加节点后判断添加的节点数是否大于等于7，如果满足，转换为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
//跳出这个循环不再走下面的逻辑
break;
}
//遍历链表的过程中，判断链表中是否存在相同的key,如果存在，break
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// ④ hash值相同，key的地址值相同，说明key相同，值覆盖
if (e != null) {
// existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
总结：
① 判断数组是否为null，如果为null，对数组进行扩容并初始化
② 计算要添加数据的key映射的桶下标，如果桶下标处元素为null，说明不存在hash碰撞，直接将key和value封装为Node节点添加到数组中。
③ 如果桶下标处元素不为null，说明存在hash碰撞，即存在两个key计算出的桶下标相同：
- 如果要添加的元素的hash值和数组中元素的hash值相同，并且key的地址值也相同，那么键相同值覆盖
- 如果要添加的元素的hash值和数组中元素的hash值不同，或者key的地址值不相同：
-
- 如果是红黑树节点，调用红黑树添加节点的方法
- 如果是链表节点，遍历链表，并判断链表中的节点的key值和要添加的数据的key值是相同，如果key相同值覆盖，如果遍历到链表的结尾也不存在重复的key，直接添加到链表的尾部，添加完后判断添加的节点个数是否大于等于7，如果大于等于7则将链表转为红黑树。
④ 如果size大于阈值threshold，则进行扩容；
# 4.1 hash()方法实现
① 计算hash(key)
对于key的hashCode做hash操作，无符号右移16位后做异或运算。 还有伪随机数法和取余数法。这2种效率都比较低。而无符号右移16位和异或运算效率是最高的。
static final int hash(Object key) {
int h;
//第一步：计算key的hashCode，返回散列值 ，假设随便生成的一个值。
//第二步：将h ^ (h >>> 16)
//通过高16bit 和 低16bit 混合计算出 16bit 的哈希值，充分利用所有信息计算出哈希值,减少hash冲突
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
② 计算数组桶下标： hash(key) & (table.length-1)
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
// n表示数组初始化的长度是16
// 数组的长度必须为2的n次方，这样能够让hash(key)更加均匀的分布在桶下标中，减少hash冲突
// 使用 & 运算是为了提高效率
if ((p = tab[i = (n - 1) & hash]) == null)
}
# 4.2 resize()方法实现
当HashMap中的元素个数超过数组大小 *loadFactor时，就会进行数组扩容，loadFactor的默认值是0.75,这是一个折中的取值。也就是说，默认情况下，数组大小为16，那么当HashMap中的元素个数超过16×0.75=12(这个值就是阈值或者边界值threshold值)的时候，就把数组的大小扩展为2×16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预知元素的个数能够有效的提高HashMap的性能。
当HashMap中的其中一个链表的对象个数如果达到了8个，此时如果数组长度没有达到64，那么HashMap会先扩容解决，如果已经达到了64，那么这个链表会变成红黑树，节点类型由Node变成TreeNode类型。当然，如果映射关系被移除后，下次执行resize方法时判断树的节点个数低于6，也会再把树转换为链表。
进行扩容，会伴随着一次重新hash分配，并且会遍历hash表中所有的元素，是非常耗时的。在编写程序中，要尽量避免resize。
HashMap在进行扩容时，使用的rehash方式非常巧妙，因为每次扩容都是翻倍，与原来计算的 (n-1)&hash的结果相比，只是多了一个bit位，所以节点要么就在原来的位置，要么就被分配到"原位置+旧容量"这个位置。
怎么理解呢？例如我们从16扩展为32时，具体的变化如下所示：
元素在重新计算hash之后，因为n变为2倍，那么n-1的标记范围在高位多1bit(红色)，因此新的index就会发生这样的变化：
说明：5是假设计算出来的原来的索引。这样就验证了上述所描述的：扩容之后所以节点要么就在原来的位置，要么就被分配到"原位置+旧容量"这个位置。如果新的索引高位为0那么存储在原来索引位置，如果高位是1那么存在原来索引+旧的数组长度位置。
因此，我们在扩充HashMap的时候，不需要重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就可以了，是0的话索引没变，是1的话索引变成“原索引+oldCap(原位置+旧容量)”。可以看看下图为16扩充为32的resize示意图：
正是因为这样巧妙的rehash方式，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，在resize的过程中保证了rehash之后每个桶上的节点数一定小于等于原来桶上的节点数，保证了rehash之后不会出现更严重的hash冲突，均匀的把之前的冲突的节点分散到新的桶中了。
final Node<K,V>[] resize() {
//得到当前数组
Node<K,V>[] oldTab = table;
//如果当前数组等于null长度返回0，否则返回当前数组的长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//旧阈值点 默认是12(16*0.75)
int oldThr = threshold;
int newCap, newThr = 0;
// ① 数组容量>0
if (oldCap > 0) {
// ① 超过最大值就不再扩充了，就只好随你碰撞去吧
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// ② 没超过最大值，数组容量就扩充为原来的2倍，newCap = 16*2=32
else if((newCap = oldCap << 1)< MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
//阈值扩大一倍， 默认原来是12 乘以2之后变为24
newThr = oldThr << 1;
}
//② 旧阈值点大于0 直接赋值
else if (oldThr > 0)
newCap = oldThr;
//③ 直接使用默认值
else {
newCap = DEFAULT_INITIAL_CAPACITY;//16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// ① 如果新的容量为0
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// ② 新的阈值threshold = 24
threshold = newThr;
// ③ 创建新的哈希表，数组大小为newCap=32
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// ④ 判断旧数组不等于空，遍历旧的哈希表 ,重新计算桶里元素的新位置,把每个bucket都移动到新的buckets中
if (oldTab != null) {
// 把每个bucket都移动到新的buckets中
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//取出桶中的元素赋值给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;
//① e这个节点在resize之后不需要移动位置
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
//② 否则e这个节点要插入的位置为：原索引+oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 原索引放到bucket里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引+oldCap放到bucket里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
总结：
① 如果当前数组的容量大于0并且小于数组容量的最大值，那么就会将数组容量扩容为原来的2倍
② 如果数组容量为0，但是阈值大于0，那么table会初始化为阈值大小
③ 如果数组容量为0，且阈值为0，那么table会初始化为默认值16
④ 创建一个新的数组，数组的容量为扩容后的数组大小，然后遍历原来数组中的元素：
- 如果数组桶下标处只有一个键值对，将当前位置的元素直接插入到新数组对应桶下标处
- 如果红黑树节点，拆分红黑树解决哈希冲突
- 如果是链表节点，遍历链表，并计算链表中每个节点应该插入到新数组中的位置
-
3. 如果当前节点的hash值和原来数组的容量进行与运算等于0，那么当前元素插入新数组的该索引处
3. 如果当前节点的hash值和原来数组的容量进行与运算等于1，那么当前元素插入到新数组的位置为：当前元素在旧数组中的索引+旧数组的长度
# 4.3 treeifyBin()方法实现
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();
//② 执行到这里说明哈希表中的数组长度大于阈值64，开始进行树形化
// 将数组中的元素取出赋值给e,e是哈希表中指定位置桶里的链表节点，从第一个开始
else if ((e = tab[index = (n - 1) & hash]) != null) {
///hd：红黑树的头结点 tl :红黑树的尾结点
TreeNode<K,V> hd = null, tl = null;
do {
//新创建一个树的节点，内容和当前链表节点e一致
TreeNode<K,V> p = replacementTreeNode(e, null);
//将新创键的p节点赋值给红黑树的头结点
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);
}
}
# 5. HashMap的get()方法流程
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
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、key的地址、key的内容是否和要查找的key相同，如果相同返回即可
if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
return first;
//如果数组中节点还指向了下一个节点
if ((e = first.next) != null) {
//如果是红黑树，调用红黑树的getTreeNode()方法
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//如果是链表，遍历链表，查找与key相同的键对应的节点，找到只有返回当前节点
do {
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}