HashMap 是 Map 接口中基于哈希表的非同步实现, 自身也可以自动扩容。使用时可以通过 key 快速定位到对应的 value。key 和 value 同时可以都为 null。
1 HashMap 的结构定义
JDK1.8 对 HashMap 进行了比较大的优化, 底层实现由之前的 “数组 + 链表” 改为 “数组 + 链表 + 红黑树”。
在链表的长度大于等于 8 并且数组的长度大于等于 64 时, 将对应的链表转为红黑树 (本文不涉及红黑树部分的分析, 涉及到时, 只会提一下, 然后跳过)。
首先数组是整个数据的存储真正实体, 数组中的存储的数据是链表或者红黑树, 当链表的长度达到了条件, 就变成了红黑树, 大体的情况如下:
1.1 数组的定义
public class HashMap<K,V> {
transient Node<K,V>[] table;
}
从上面的代码就是 HashMap 中数据存储的地方: 数组。 数组存储的数据类型为 Node, 这个 Node 是链表的定义。
而 红黑树的定义是继承了 Node, 所以通过向上转型的方式, 就能通过一个 Node 的类型表示链表和红黑树。
1.2 链表的定义
public class HashMap<K,V> {
/**
* 链表定义
* Map.Entry 行为接口, 定义了一堆操作方法, 比如 getValue, setValue 等
*/
static class Node<K,V> implements Map.Entry<K,V> {
// 当前节点的 hash 值
final int hash;
// 当前节点的 key
final K key;
// 当前节点的 value
V value;
// 下一个节点, 这个属性决定了 Node 为链表
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
/**
* 计算当前节点 hashCode
*/
public final int hashCode() {
// Objects.hashCode 本质就是调用对象的 o.hashCode()
// 当前节点的 hashCode 值 等于 key 的 hashCode 异或 value 的 hashCode 值
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
/**
* 节点比较
*/
public final boolean equals(Object o) {
if (o == this)
return true;
// 都是 Map.Entry 节点
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
// Objects.equals 会先比较一下 2 者的内存地址, 一样直接返回 true
// 不一样, 调用 key.equals(e.getKey) 进行比较
if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
}
1.3 红黑树的定义
public class HashMap<K, V> {
// 继承了 LinkedHashMap.Entry, Entry 继承了 HashMap.Node 所以 TreeNode 具有 链表的特点
/**
* 红黑树的定义
* LinkedHashMap.Entry 继承了 HashMap.Node 节点, 所以 TreeNode 是 Node 的子类, 也具备链表的特点
*/
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
/**
* 红黑树的根节点
*/
TreeNode<K,V> parent;
/**
* 当前节点的左节点
*/
TreeNode<K,V> left;
/**
* 当前节点的右节点
*/
TreeNode<K,V> right;
/**
* 删除后需要解决连接的节点
*/
TreeNode<K,V> prev;
/**
* 是否为红色节点
*/
boolean red;
// ... 后面 省略 红黑树的操作
}
}
2 HashMap 中的几个重要属性
public class HashMap<K,V> {
transient Node<K,V>[] table;
transient int size;
transient int modCount;
final float loadFactor;
private int threshold;
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
static final int MAXIMUM_CAPACITY = 1 << 30;
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
}
2.1 table
transient Node<K,V>[] table;
HashMap 中存储数据的数组
2.2 size
transient int size;
HashMap 中已经存储的数据个数
2.3 modCount
transient int modCount;
HashMap 已经被修改了多少次, 用于支撑 fail-fast 机制
2.4 loadFactor
final float loadFactor;
负载因子: 默认等于 DEFAULT_LOAD_FACTOR = 0.75f;
作用: 一般情况都是在容器满了才会进行扩容, 但是在 HashMap 中, 数据量达到了数组的长度 * 负载因子的值, 就会进行扩容了。
原因: HashMap 在数组中插入一个数据, 是先通过一个 hash 方法转换为一个 hash 值, 通过这个 hash 值计算得到存储在数组的位置, 通过 hash 计算, 就可能存在 hash 冲突。
数据越密集, 冲突的可能性越大, 所以 HashMap 中的数组是不会完成存满的, 通过空留一部分, 减少冲突等。
负载因子默认值为 0.75 的原因: 太大冲突可能性变大, 太小浪费了空间, 同时会导致数组扩容等耗时操作。
所以 0.75 应该是一个经验值的估算, 或者是因为 HashMap的数组长度为 2^n, 乘以 0.75, 能获得一个整数。
2.5 threshold
private int threshold;
当前数组的阈值, 即数组实际应该放多少数据
2.6 几个常量
// 1 左移多少位, 就是相当于 2 的 多少次方, 这里就是 2^4 = 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
声明 HashMap, 不指定容量时, 默认为 16。
// 2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
HashMap 最大容量, 容量必须是 2 的 n 次方, 涉及到通过 key 的 hash 值定位到数组的位置中的一个配合。
HashMap 中数组的容量设定为 2 的 n 次方具体有 2 个作用:
第一, 得到了 key 对应的 hash 后, 如何通过 hash 定位到数组中的哪一个位置呢?
最简单的方式就是取模了吧, 通过 hash 值模于当前数组的长度, 得到的就是当前 hash 对应的数组位置。
但是取模的效率不太好, 那么有什么好的优化方式吗?
在数学上, a, b 都是正整数的情况下, a % b, 在 b 是 2 的 n 次方下, a % b = a & (b - 1)。
位运算比正常的算术运算快, 那么将 HashMap 的容量设置为 2 的 n 次方, 就可以通过与运算达到取模的效果。
所以 HashMap 中的数组容量必须为 2 的 n 次方。
第二个作用在后面会分析。
static final int TREEIFY_THRESHOLD = 8;
HashMap 中链表变为红黑树的长度配置, 链表长度达到了 8 满足了链表变为红黑树的条件之一。
static final int UNTREEIFY_THRESHOLD = 6;
HashMap 中红黑树重新变为链表的长度配置, 红黑树的节点个数达到了 6, 满足了红黑树变为链表的条件之一。
static final int MIN_TREEIFY_CAPACITY = 64;
HashMap 中链表变为红黑树的的另外一个条件, 当前数组的长度达到了 64。
3 HashMap 的构造方法
3.1 无参的构造函数
public HashMap() {
// 设置负载因子为 0.75
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
3.2 指定初始容量 (和负载因子) 的构造函数
public HashMap(int initialCapacity) {
// 调用到自身的指定容量 和负载因子的构造函数, 传入的负载因子为默认值 0.75
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* 指定 初始容量 和 负载因子
*/
public HashMap(int initialCapacity, float loadFactor) {
// 指定的容量小于 0, 格式不正确
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
// 指定的容量超过了最大容量, 设置为支持的最大容量值
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// 格式不正确 NaN: Not-a-Number, isNaN(arg) => arg 不是数字, 返回true
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
// 负载因子直接等于输入的值
this.loadFactor = loadFactor;
// tableSizeFor 这个方法会对输入的值, 转换为第一个大于或等于输入值的 2 的 n 次方的数, 比如: 输入 3 得到 4, 输入 4 得到 4, 输入 5 得到 8
// 因为 HashMap 的容量需要是 2 的 n 次方, 通过 tableSizeFor 将用户输入的不是 2 的 n 次方的数, 进行修正
// threshold 这个属性上面说过是用来存储 HashMap 的实际容量 (声明的数组容量 * 负载因子), 但是这里直接赋值的是 2 的 n 次方, 错了吗?
// 实际上没错的, threshold 就是用来存储实际的容量的, 这里只是把计算出来的容量临时存在这个变量, 在第一次进行存放数据时, 进行修正为实际容量的
this.threshold = tableSizeFor(initialCapacity);
}
/**
* 计算数组容量
*/
static final int tableSizeFor(int cap) {
// 此次减 1 的原因: 让后面的处理结果变为 n 是第一个大于等于 cap 的 2 的 n 次方的数
// 如果这里不减 1 的话, 刚好传进来的数是 2 的 n 次方, 经过下面几步的处理会变成 2 的 n+1 次方的数
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
// 做一个容错 如果 cap 是一个小于等于 0 的数, 经过上面的处理, n 将会变成一个负数
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
3.3 给定一个 Map 的构造函数
public HashMap(Map<? extends K, ? extends V> m) {
// 负载因子 = 0.75
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
/**
* 放入数据
* @param m 数据
* @param evict 这个参数主用是在插入节点后, 做调整用的, 在 HashMap 中不具备任何作用, 构造参数中直接使用 false, 其他的情况使用 true 即可, 基于 HashMap 实现的 LinkedHashMap 才需要使用到这个参数
*/
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
// 获取需要传入的 Map 的数据个数
int s = m.size();
// 大于 0 的话, 才出来
if (s > 0) {
// 当前存放数据的 table 为空, 表示为初始化
if (table == null) {
// 计算出来需要的容量 = 长度 / 赋值因子 + 1
float ft = ((float)s / loadFactor) + 1.0F;
// 限制最大的容量 为 2^ 30
int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);
// 计算出来的当前需要的容量 > 实际的容量, 进行新容量的计算
if (t > threshold)
// 计算存储数据的数组的容量
threshold = tableSizeFor(t);
} else if (s > threshold)
// 当前存入的数据量直接大于当前阈值, 进行重新扩容
// 扩容方法在下面的添加数据讲解
resize();
// 遍历 Map, 将里面的数据逐个迁移到当前的 Map 中
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);
}
}
}
4 HashMap 的操作方法
4.1 添加数据
public class HashMap<K, V> {
public V put(K key, V value) {
// 1. 计算 key 的 hash 值
// 2. 调用 putVal 进行数据的新增
return putVal(hash(key), key, value, false, true);
}
/**
* key 计算出 hash 值
*/
static final int hash(Object key) {
int h;
// 对象的 hashCode ^ 对象的 hashCode >>> 16
// 将 hashCode 的高 16 位与 hashCode 进行异或运算, 主要是为了在 table 的 length 较小的时候, 让高位也参与运算, 减少 hash 冲突, 并且不会有太大的开销
// 这里做了一个容错, 如果 key 为 0, 那么计算出来的 hash 值为 0, 也就是 HashMap 直接 key 为 0 的情况, 但是只能存一个 key 为 null 的数据,
// 后面的 key 为 null, 计算出来的 hash 都是 0, 会把旧值覆盖(默认情况)
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
/**
* 存值
* @ hash 存的 key 的hash值
* @ key 对象的 key
* @ value 存的值
* @ onlyIfAbsent 存入的数据已在 HashMap 中存在, 是否有新的 value 替代旧的 value, false 进行修改, true 不修改
* @ evict 这个值用于 LinkedHashMap, 在HashMap 中没有作用
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 数组为空 或者 数组的长度为 0, 进行扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// HashMap 对象的位置是通过 (数组的长度 - 1) & hash, 也就是 hash % (2 ^ n - 1) 的形式
// 存储的位置为空, 直接将 hash, key, value 封装为新的 Node 节点, 放到指定的位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
// 存储的位置已经有数据了
Node<K,V> e; K k;
// 需要放入的位置的第一个节点 的 hash 和 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);
// 当前的容量已经达到了 8个, 转为红黑树, binCount 从 0 开始遍历的
if (binCount >= TREEIFY_THRESHOLD - 1)
// 这个方法后面
treeifyBin(tab, hash);
break;
}
// 链表中有一个节点的 hash 和 key 和要插入的一样, 取到这个节点, 停止遍历链表
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
// p = p 的下一个节点, 判断下一个节点
p = e
}
}
// e 不为空, 表示在数组当前的位置的链表或红黑树中存在一个 key 值和 hash 值和当前要存入的数据一样。
if (e != null) {
// 获取旧值
V oldValue = e.value;
// 旧值为 null 或者入参的 onlyIfAbsent 为 false, 新值替换旧值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// 在 HashMap 中这个是空方法
afterNodeAccess(e);
return oldValue;
}
// 修改次数 + 1, 用于支持 fast-fail 机制
++modCount;
// 当前存储的数据个数达到了阈值, 进行扩容
if (++size > threshold)
resize();
}
// HashMap 的这个方法没有实现
afterNodeInsertion(evict);
return null;
}
/**
* 重新扩容
*/
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, 也就是有数据存在了
if (oldCap > 0) {
// 当前的容量已经达到最大了, 直接不进行操作
if (oldCap >= MAXIMUM_CAPACITY) {
// 直接将阈值设为 int 的最大值
// 实际的数组长度依旧为 2^30, 一般情况阈值 threshold = 实际数组的长度 * 负载因子, 负载因子一般都是小于 1 大于 0 的数, 所以 threshold < 数组的实际长度
// 决定数组是否扩容的则是由 threshold 是否小于当前的数据个数 size, 所以数组的容量还未完全用完了, 就扩容了,
// 现在的情况是, 旧的数组的容量已经达到了设定的最大容量了, 无法继续扩了, 所以将 threshold 直接设置为 int 的最大值 > 数组的长度, 这样可以继续利用原本因负载因子而无法使用到的空间
threshold = Integer.MAX_VALUE;
return oldTab;
// 新容量的值 = 旧数组的容量 * 2
// 新的容量 < 最大容量 && 旧的容量 >= 初始默认的容量(16), 这种情况下设置新的负载 = 旧的 * 2
// 那么就存在旧的容量为 2, 4, 8 三种情况, 没有走到下面的 newThr = old << 1, 那么新的阈值为 0
// oldCap >= DEFAULT_INITIAL_CAPACITY, 新的阈值什么不是无条件的等于旧的阈值的 2 倍
// 而是只有在 oldCap >= DEFAULT_INITIAL_CAPACITY, 新的阈值才会是旧阈值的 2 倍
// 而如果 oldCap 为 2, 4, 8, 则新的阈值为 0, 需要到下面的新的阈值 = 0 的判断进行处理, 具体的分析看下面的备注 1
} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1;
} else if (oldThr > 0)
// 当旧的阈值大于 0, 设置新的容量 = 阈值
// 能够走到这一步的情况有:
// 1. 我们初始时, 只指定了容量, 然后第一次往里面加数据
// 2. 初始时, 只传递了一个 Map, 然后第一次把 Map 里面的数据放到当前 HashMap 时
// 新的容量 = 当前的阈值 = threshold, 因为在声明 HashMap 时, 会临时将容量存储到 threshold, 直接赋值过来就是需要的容量了
newCap = oldThr;
else {
// 当我们创建时, 没有指定容量时, 在第一次放数据, 会走这一步
// 这里将需要的容量的设置为默认值 16, 新的阈值为 16 * 0.75
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 新的阈值为 0
if (newThr == 0) {
// 一般情况下阈值 = 新容量 * 0.75, 如果数组的容量达到了最大容量, 则直接设置为 int 的最大值
// 这里新的阈值为 0, 能够走到这一步的情况有:
// 1. 我们初始时, 只指定了容量, 然后第一次往里面加数据
// 2. 初始时, 只传递了一个 Map, 然后第一次把 Map 里面的数据放到当前 HashMap 时
// 3. 扩容时, 旧的容量为 2/4/8 中的一个, 那么 newThr 也是 0, 需要结合上面的扩容的 oldCap >= DEFAULT_INITIAL_CAPACITY 进行分析
// 计算理论的阈值 = 新的容量 * 负载因子
float ft = (float)newCap * loadFactor;
// 新的容量 < 最大值 && 理论的阈值 < 最大值 ? 新的阈值 = 计算出来的阈值 : 新的阈值 = int 的最大值
// 这里个人感觉有点问题, 具体看下面的 备注 2
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
}
// 设置新的阈值
threshold = newThr;
// 声明新的数组, 用于存储数据
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
// HashMap 中的数组引用修改为新声明的数组
table = newTab;
// 数组 重新赋值
if (oldTab != null) {
// 遍历旧数组的每一项
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
// 获取到当前数组的第 j 个元素
if ((e = oldTab[j]) != null) {
第 j 个元素不为 null, 表示有数据, 需要进行迁移
// 旧数组的 j 位置的值设置为空, 方便垃圾回收
oldTab[j] = null;
if (e.next == null)
// 如果 e.next 为空, 则代表旧数组的该位置只有 1 个节点, 那么把这个节点直接放到新数组里面, 就行了
// 通过 (节点 的 hash 值 & 新容量 -1 ) 取到新的位置
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// 原本的这个节点为树节点, 调用 TreeNode 的 split 进行处理
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
// 到了这一步, 说明当前位置存储的是一个 链表, 同时链表的数据存在 2 个以上
// 声明了2 个链表, lo 链表, hi 链表, 这 4 个指针, 分别指向了 2 个链表的头和尾
// 其中的 lo 可以理解为 low, 地位链表, hi 为 hight, 高维链表,
// 新的数组的容量是是原来的2倍, 那么 原来的一倍 可以理解为 low, 扩充出来的为 hight
// 原本在同一个链表上的节点, 转移到扩容后的数组式, 只可能会被分配到 2 个位置, 和原来一样的位置 或者原来的位置 + oldCap 的位置, 看下面的备注 3
// lo 链表存放的是节点位置不需要修改的节点, hi 就是存储位置变为 原来位置 + oldCap 的节点
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
// 遍历 j 位置上的链表
// 临时保存下一个节点
next = e.next;
// 当前节点的 hash 值 与上旧的容量值等于 0, 那么可以确定这个节点在新数组的位置和原来的一样
// 先将其放到低维的链表, 后面在把低维的链表放到新数组的对应位置
if ((e.hash & oldCap) == 0) {
if (loTail == null)
// 如果loTail为空, 代表该节点为第一个节点
loHead = e;
else
// 否则将节点添加在链表的尾部
loTail.next = e;
// 重新设置尾结点
loTail = e;
} else {
// 不等于 0, 表示这个节点需要存放到新的位置, 先放到高维链表
if (hiTail == null)
// 作用同上面
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
// 设置数组的 j 位置为 lo 链表
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
// 设置数组的 j + oldCap 为 hi链表
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
// 返回新数组
return newTab;
}
/**
* 将指定的位置转为树
* 在 putVal 时, 如果发现链表的长度大于 8 了, 就会调用这个方法, 将链表变为链表
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 注意这里: 数组为空, 或者长度还不够 64, 进行扩容, 不进行转换操作
// 所以链表转为红黑树的还有一个大前提: 当前 HashMap 中存储数据的数组的长度要大于 64, 而不是链表的长度大于 8 就树化
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
// 需要处理的位置的链表不为 null
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
// 因为 TreeNode 继承了 Node, 所以 TreeNode 也可以当做链表使用
// 将 Node 转为 TreeNode
// 然后将下面拼接成一个以 TreeNode 为类型的链表
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);
}
}
}
4.1.1 备注 1
在 resize 方法中, 旧数组已有数据了, 但是在进行扩容时, 容量默认是 2 倍扩展, 但是阈值只有在 oldCap >= DEFAULT_INITIAL_CAPACITY 时才会进行 2 倍扩展, 否则是为新的容量 * 负载因子。
原因: 为了在容量少的情况下, 尽可能的利用数组的空间, 不造成浪费。
假设我们在初始时, 指定了容量为 2, 那么在初始后容量值为 2, 阈值为 2 * 0.75 = 1。
第一次扩容:
| 旧的容量 | 新的容量 | 旧的阈值 | 经过运算新的阈值 | |
|---|---|---|---|---|
| 旧阈值 << 1 | 2 | 4 | 1 | 2 |
| 新容量 × 0.75 | 2 | 4 | 1 | 3 |
第一次扩容:
| 旧的容量 | 新的容量 | 旧的阈值 | 经过运算新的阈值 | |
|---|---|---|---|---|
| 旧阈值 << 1 | 4 | 8 | 2 | 4 |
| 新容量 × 0.75 | 4 | 8 | 3 | 6 |
第三次扩容
| 旧的容量 | 新的容量 | 旧的阈值 | 经过运算新的阈值 | |
|---|---|---|---|---|
| 旧阈值 << 1 | 8 | 16 | 4 | 8 |
| 新容量 × 0.75 | 8 | 16 | 6 | 12 |
第四次扩容
| 旧的容量 | 新的容量 | 旧的阈值 | 经过运算新的阈值 | |
|---|---|---|---|---|
| 旧阈值 << 1 | 16 | 32 | 8 | 16 |
| 新容量 × 0.75 | 16 | 32 | 12 | 24 |
通过上面可以发现: 在旧容量 < 16 之间变化时, 通过新容量 × 负载因子, 阈值会大一些, 可以更充分的利用数组的空间, 在第四次扩容时, 新容量为 32 时, 旧的阈值为 12, 这时 12 << 1 等于 32 * 0.75, 所以 2 者后续的计算是一样的, 通过位运算比较快。
可以简单理解为: 阈值一直都是等于当前的容量 * 负载因子,
在旧容量为 2, 4, 8 按照上面的方式计算。
到了就容量 >= 16 时, 可以通过位运算达到同样的计算效果, 使用位运算更快
4.1.2 备注 2
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
// 步骤 1
} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1;
} else if (oldThr > 0)
// 省略
else {
// 省略
}
if (newThr == 0) {
// 步骤 2
float ft = (float)newCap * loadFactor;
// 步骤 3
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
}
// 设置新的阈值
threshold = newThr;
}
上面的阈值的计算一般情况下是没问题的, 但是在容量从 2^29 到最大值 2^30 扩容时, 按照上面的步骤
- 走到步骤 1 时, 容量变为原来的 2 倍, newCap = MAXIMUM_CAPACITY, 这时 newCap < MAXIMUM_CAPACITY, 不满足条件, 所以 newThr 还是 0
- 到了步骤 2 时, 计算出来的 ft = newCap * loadFactor, loadFactory 一般都是大于 0, 小于 1 的数, 所以 ft < newCap = MAXIMUM_CAPACITY, 既 ft < MAXIMUM_CAPACITY
- 到了步骤 3 时, new = MAXIMUM_CAPACITY < MAXIMUM_CAPACITY 为 false, false && true = false
- 经过步骤 3 后, newThr 直接变为 int.max_value, 正常应该是 newCap * loadFactor, 下次扩容时, 到达上面的旧容量 >= MAXIMUM_CAPACITY, 再把阈值修改为 int.max_value
上面的分析都是基于负载因子大于 0, 小于 1 的情况的分析, 如果用户将负载因子设置为大于 1 的情况, 可能导致步骤 2 计算出来的 ft 为 负数。
所以可以将上面的步骤 1 修改为 <= MAXIMUM_CAPACITY 或者步骤 3 修改为 <= MAXIMUM_CAPACITY
4.1.3 备注 3
(e.hash & oldCap) == 0 可以判断节点在新数组的位置和旧数组的是否一样, 很巧妙的利用了数组的长度为 2 的 n 次方这个特性。 也就是 HashMap 中数组的容量是 2 的 n 次方的第二个作用。
能达到这样的效果的必须知道:
- oldCap 是 2 ^ n, newCap 是 在 oldCap 的基础 * 2, 也就是 newCap 是 2 ^ (n + 1)
- 2 ^ n 在二进制的表示为 1 + n 个 0 , 2 ^ (n + 1) 二进制表示 1 + ( n + 1 ) 个 0
- 2 ^ n - 1 在二进制的表示为 n 个 1, 那么 2 ^ (n + 1) 就是 n + 1 个 1
- (2 ^ n - 1) & hash, 我们只需要取 hash 的从右到左的 1 到 n 位就行了, 因为 2 ^ n - 1 前面都是 0, & 上都是 0
我们假设有个节点 A, 其 现在在数组中的 index 位置, 现在 oldCap 是 16, 既 2^4, 16 - 1 = 15, 二进制表示为 00000000 00000000 00000000 00001111
这时候 index = hash & (16 - 1), index 的值自然就是只和 hash 值的低 4 位有关, 我们假设它为 abcd
oldCap 扩大了一倍, 当前节点的的位置 index 的计算公式 = (32-1) & hash, 和 hash 值的低 5 位有关, hash 的低 5 位的值无外乎下面两种情况: 0abcd 或者 1abcd
0abcd = index, 而 1abcd = 0abcd + 10000 = 0abcd + oldCap = index + oldCap, 从这里可以知道容量扩大了一倍, 那么新的 index 是有规律的, 要么不变, 要么就是 index + oldCap
新旧 index 是否一致就体现在 hash 值的第 5 位, 那么第 5 位怎么知道呢？ 32 的 2^n 的二进制形式 1 + 5 个 0, 那么 hash & oldCap 就能知道 hash 的第 5 位是 0 或者 1 了, 既 hash & oldCap = 0, hash 的第 5 位为 0,
hash & oldCap 不等于 0, hash 的第 5 位为 1。
最终可以通过 hash & oldCap 得到
- hash & oldCap = 0 => 当前节点在数组的位置不用变
- hash & oldCap != 0 => 当前节点在新数组的 index + oldCap 的位置
4.2 其他添加数据的方式
- 直接添加一个 Map 的 putAll(Map<K, V> map);
- 添加一个元素, 如果对应的位置已经有数据了, 则不添加 putIfAbsent(K key, V value)
4.3 获取数据
public class HashMap<K, V> {
/**
* 通过 key 获取 value, 如果节点为 null, 返回 nulL
*/
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* 通过 key 的 hash 值和 key 值获取 value 值
*/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 数组不为空, 长度大于 0, 链表的第一个节点 不为 null
if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
// 第一个节点的 hash 值和传入的 hash 值一样, key 值也一样, 第一个节点符合条件了, 直接返回
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 {
// 遍历 链表的其他节点,
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
}
4.4 删除数据
public class HashMap<K, V> {
/**
* 直接通过 key删除
*/
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;
}
/**
* 删除节点
* matchValue : 为 true, 找到了节点, 还会比较他们的值, 值相同才会删除
* movable : 针对红黑树起作用, 为 false, 节点删除了, 不改变其他节点的位置
*/
final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
// 数组不为 null, 长度大于 0, 同时定位到的位置不为 null
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 = p;
// 链表的下一个节点不为null
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 = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
// 找到了需要删除的节点, 如果设置了需要检查值, 后面会对其值的内存地址和 equals 进行比较
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 在上面的链表的遍历中, 变成需要删除的节点的前一个节点了
// p 的下一个节点指向需要删除节点的下一个节点
p.next = node.next;
++modCount;
--size;
// 空方法
afterNodeRemoval(node);
return node;
}
}
}
}
上面只是通过 key 进行删除数据的, 同样还有一个通过 key 和 value 值都相同的情况进行删除的方法。
4.5 修改数据
public class HashMap<K, V> {
public boolean replace(K key, V oldValue, V newValue) {
Node<K,V> e; V v;
// 通过 getNode 获取到对应的节点, 节点的值等于入参的 oldValue
if ((e = getNode(hash(key), key)) != null && ((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
// 替换节点的 value 值等于入参的新 value
e.value = newValue;
afterNodeAccess(e);
return true;
}
return false;
}
}
5 HashMap 的补充
- HashMap 同样是线程不安全的, 如果需要线程安全, 同样可以通过 Collections.synchronizedMap() 获取到一个线程安全的实现类。
- HashMap 支持 fail-fast 机制
- HashMap 的序列化也是自定义的
- HashMap 内部提供了许多迭代器: KeyIterator, ValueIterator, EntryIterator, 方便各种遍历需求
- HashMap 的线程不安全, 猜测时, 同时有 2 个线程判断到需要扩容了, 然后同时进行扩容, 期间就可能造成闭合的链路。
6 红黑树相关的内容
- 清晰理解红黑树的演变—红黑的含义 红黑树的前身
- 教你初步了解红黑树 红黑树的节点插入
- 红黑树之删除节点 红黑树的节点删除
- 红黑树原理以及插入、删除算法 附图例说明 里面的增删图片不错
7 参考
Java集合: HashMap详解 (JDK 1.8)
深入理解HashMap(四): 关键源码逐行分析之resize扩容
