HashMap 原理及源码分析
站长
· 阅读数 37
HashMap 原理及源码分析
HashMap-设计简介
针对上图做一个术语规定便于理解
- table 数组，叫做桶（bucket）
- table 数组中的某一个元素比如 table[1] 叫做槽位
- 如果槽位有对应的单链表链表数据，叫做槽位链表（包含槽位数据）
上图有一个不准确的地方就是，实际上就算 table 对应的槽位链表结点数大于等于 8 后，也要判断 table 的数据量是否超过了 64，超过了才会转化为红黑树，如果没有超过则会对 table 进行扩容而不转化为红黑树
如上图所示，HashMap 的组成是由以下几个部分组成
- table 数组
- 单链表
- 红黑树（在特定的情况下才会存在后续会讲解）
思考问题
在看源代码前，不过在此之前我们先思考几个问题，带着问题去看源码理解更深
- HashMap 扩容是不是要依次取出每个数据在调用 putVal 方法再做一次 hash 存储？
- 为什么 HashMap 要使用数组 + 链表 + 红黑树来实现？
- 为什么单链表数大于等于 8 并且 table 数组大于等于 64 的时候要进行转换为红黑树？
- 为什么要存在 size > threshold 这个扩容限定值的时候要进行扩容？
- 为什么红黑树结点数目小于 6 的时候要退化为链表？
- 如果说 HashMap 在扩容的时候不需要再次 hash 来提高扩容时候的效率它又是如何实现的？
- HashMap 是有序的吗？
- HashMap 是线程安全的吗？
问题 2：为什么 HashMap 要使用数组 + 链表 + 红黑树来实现？
为什么使用数组？利用 table 数组保存索引位置，索引位置是根据 hash(key) & (table.length - 1) 算出来的，那么下次访问某个 key 的时候直接计算出 table 数组索引就可以直接访问效率 O(1)
为什么要加链表呢？这个是因为 hash 算法的问题，对于 hash 算法而言，如果能够将数据均匀 hash 到不同的槽位，hash 算法本身执行效率也高，hash 冲突小那么就是很好的 hash 算法，事实上也无法完全保证，比如 hash 冲突就是一定会存在的，那么如果存在 hash 冲突的话，将冲突的数据以槽位数据为 head 依次添加到尾部形成一个单链表，检索的时候去挨个判断 hash、key 是否相等来验证是否找到了对应的数据
由上图可以看出采用了链表检索检索效率可能会降低单链表的检索时间复杂度为 O(n)，所以我们可以将单链表转化为二叉搜索树来提高效率时间复杂度就可以提升为 O(log2n)。
那什么需要红黑树，思考一种情况是，如果由于某种情况下（比如别人的恶意攻击，hash 算法问题，以及数据的特征分布问题）导致绝大部分数据都在同一个槽位比如 table[i] 上，那么当检索一个数据的时候实际上就变成了单链表的检索，时间复杂度 O(n) 这显然违背了 HashMap 设计的初衷无法满足高效的检索缩率 O(1)
这种情况下怎么办呢？就是将树转化为红黑树，红黑树由于其本身的特性就算数据分布不均匀也能保持高效的检索等效率所以 HashMap 的真正实现是，需要将单链表转化为红黑树。
红黑树通过增加结点，修改结点的红、黑颜色旋转子树等操作让树始终保持平衡状态，红黑树的原理不复杂，但是代码实现相对复杂感兴趣的同学就可以去搜索一下，本文就暂时不讲其对应的原理。
问题 3：为什么单链表数大于等于 8 并且 table 数组大于等于 64 的时候要进行转换为红黑树？
通过问题 2 我们已经知道了为什么要使用红黑树，那么这个实际数值的选取其实是实现方通过测试选取的一个较为合适的转化值，因为要平衡收益和效率问题，如果 table 本身很小的，其实扩容代价很低，使用效率也还是蛮高的
问题 4：为什么要存在 size > threshold 这个扩容限定值的时候要进行扩容？
因为容量一定的情况，存储数据量越大，那么新添加的数据存在 hash 冲突的可能性就越高，所以需要给一个扩容阈值 threshold 表示存储容量达到该值的时候需要对 HashMap 进行扩容
问题 5：为什么红黑树结点数目小于 6 的时候要退化为链表？
当单链表结点数据足够小的时候，遍历的时间是可以忽略的，检索速度足够快。链表的复杂性也比红黑树低更好维护，在 HashMap 扩容的时候也可以更好的对链表进行拆分
而对于其它问题我们就需要从源码上找到答案，同时也能看到代码是如何实现上述操作的。首先先看下它的部分成员变量定义代表的含义（有的不明白也没有关系，具体到代码的时候还会讲解，这里先有一个大致的印象）
变量定义
// 默认的初始容量为 16
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;
// 当一个桶中链表元素个数大于等于 8 的时候转化为红黑树
static final int TREEIFY_THRESHOLD = 8;
// 当一个桶中链表元素个数小于等于 6 的时候将红黑树转化为链表
static final int UNTREEIFY_THRESHOLD = 6;
// 当桶的个数达到 64 的时候并且单个槽位链表结点数量大于等 8 的时候进行树化
static final int MIN_TREEIFY_CAPACITY = 64;
// 数组，也就是桶
transient Node<K,V>[] table;
// 作为 entrySet() 的缓存
transient Set<Map.Entry<K,V>> entrySet;
// 元素的数量
transient int size;
// 修改次数，用于在迭代的时候执行 fail-fast
transient int modCount;
// 当桶的使用数量达到多少时候进行扩容
int threshold;
// 装载因子
final float loadFactor;
/**
* 单链表结点
* @param <K>
* @param <V>
*/
static class Node<K,V> implements Map.Entry<K,V> {
// 存储 key 的 hash 值
final int hash;
final K key;
V value;
// 下一个结点
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;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
构造方法
// 指定容量和装载因子构建 HashMap
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);
}
// 指定容量构造 map
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// 无参构造全部使用默认值
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
// 根据 map 来创建一个 HashMap 使用默认的参数
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
// 将传入 map 数据复制到新的 map 中
putMapEntries(m, false);
}
上面的方法无非就是说明创建 map 的时候可以指定的变量只有，initialCapacity 容量和 loadFactor 装载因子，其它的通通使用默认值，最后一个构造方法可以根据传入额 map 构建一个新的 HashMap，下面我们看一下 putMapEntries(m, false); 是如何实现的。
// 方法是 final 不可被覆写
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
// 如果桶数组还没有创建，则先进行创建
if (table == null) { // pre-size
// 使用传入 map 的长度 / 装载因子 + 1 作为当前的 map 容量
float ft = ((float)s / loadFactor) + 1.0F;
// 如果该值超出 map 承受的最大值，则取 map 最大值作为容量
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
// 如果 map 当前的容量超出了扩容限定值，则进行扩容
if (t > threshold)
// 扩容并且返回新的 map 扩容限定值
threshold = tableSizeFor(t);
}
// 如果 map 的数据大小超出了扩容阀值
else if (s > threshold)
// 将数据迁移到一个新的 map 中搬移所有数据
resize();
// 遍历传入 map
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
// 将数据一个一个的重新放入 map 中
putVal(hash(key), key, value, false, evict);
}
}
}
这里调用了 tableSizeFor(t) 来增加 threshold，使用 puVal() 将数据依次放入新的 HashMap 中 putVal() 放到 put 那节，这里先看 tableSizeFor()
/**
* 返回一个大于等于且最接近 cap 的 2 的幂次方整数
* cap 无符号右移 1 位然后位或, 然后右移 2 位然后位或 3 .. 得到最终的结果
* @param cap
* @return
*/
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;
}
插入数据
我们首先来看一张 put 数据的流程图，假设以此插入 a、b、c、d、e、f、g、i 这 8 个变量的数据（注意这几个字母代表的是对应的变量数据比如 a = 10 之类的）
public V put(K key, V value) {
// onlyIfAbsent：false 表示如果存在则更新，不存在则插入
return putVal(hash(key), key, value, false, true);
}
/**
* 根据传入 key 的 hashCode 的无符号右移 16 位次方作为其 map 中的 hash 值
* @param key
* @return
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
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 为 null 先进行初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 如果 hash 后制定的槽位为 null 则直接放入数据即可
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
// 槽位存在数据就需要检查槽位链表是否存在对应的数据
// 如果有根据策略选择是更新还是放弃
// 如果没有这执行插入
Node<K,V> e; K k;
// 已经存在对应的 key 直接进行赋值后续根据 putIfAbsent 决定是否更新
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 {
// binCount 临时统计链表数量
for (int binCount = 0; ; ++binCount) {
// 如果不存在对应的 key 则直接执行插入
if ((e = p.next) == null) {
// 创建一个新结点
p.next = newNode(hash, key, value, null);
// 当链表中的数据数量大于等于 8 的时候
// 需要进行树化
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果已经存在对应的结点则直接返回后续根据 onlyIfAbsent 决定是否更新
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;
}
}
// 修改次数 + 1
// 该字段用于后续迭代器 fail-fast
++modCount;
// 数据量大于 threshold 进行 table 扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
上面这段代码有几个关键点，总结一下
- 如果槽位没有数据则直接进行插入
- 如果槽位有数据则检测插入节点的 key 是不是当前槽位，也就是是否需要更新当前槽位数据
- 检测槽位链表是否存在对应的 key 选择是否更新
- 如果是树节点则直接插入到树中
- 如果槽位链表也每一对应的 key 则进行添加
- 添加的时候检测链表结点数大于 8 可能要进行树化，注意这里是可能，因为 treeifyBin 里面还有一个判断条件下面会进行讲解
- 最后如果 size > threshold 要进行扩容
treeifyBin()
转化为红黑树代码
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 如果数组槽位小于 64 不进行树化，而是对 table 进行扩容
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;
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);
}
}
从这里就可以看到当单链表数据大于等于 8 并且 table 数组容量大于等于 64 的时候才会转化为红黑树，否则就去进行 resize() 扩容，这个长于 8 的单链表通过扩容迁移出去。
resize()
扩容代码，我们先看一张扩容图，首先我们来看对应的 2 种情况。 情况一.
情况二. table 数组大于等于 64 并且槽位链表结点数目大于等于 8，就需要转换为红黑树
思考： 那么 table 进行扩容的时候，原先 table[3] 的槽位链表被拆分成了 2 个一个在原先位置，另外一个在 3 + table.length 位置，这是如何做到的呢，我们来看源码
final Node<K,V>[] resize() {
// 重置之前暂记录之前数组桶的信息及相关配置信息
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// 如果之前 table 中有数据的话
if (oldCap > 0) {
// 如果超出了最大容量值，设置 threshold 最大值
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 将之前的 table 大小扩大一倍作为新的数组桶的容量，当然不能超出最大值
// 前提是之前 table 大小要大于默认值，不然数据量小没有扩容的必要直接使用默认值即可
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // 如果之前 table 中没有数据，将之前 table 的 threshold 作为新 table 的容量大小
newCap = oldThr;
else { // 如果 oldCap 与 oldThr 之前都没有指定那么使用默认值创建，初始化创建 map 其实就是进入的这个分支
newCap = DEFAULT_INITIAL_CAPACITY;
// 装载因子 * 默认容量大小作为新的 threshold
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 如果新的 threshold == 0 使用新的容量大小重新计算
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 替换掉原先的 threshold 为新的值
threshold = newThr;
// 创建一个新的数组桶准备复制迁移数据
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 如果之前的 table 不为 null 开始迁移数据
if (oldTab != null) {
// 遍历之前的 table
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
// 处理不为 null 的数据
if ((e = oldTab[j]) != null) {
// 将原 table 中的数据置为 null 便于断开其可能存在的引用链利于垃圾回收
oldTab[j] = null;
// 如果只有数组桶的一个数据，也就是槽位链表没有数据，这直接放入新的 table 槽位即可
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 如果节点是树节点 红黑树挡在单独章节分析 - TODO
// 如果链表结点数据小于 6 会将红黑树退化为链表
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // 处理 table 中槽位存在链表的情况并且不是树的情况，将原先的单个链表分化为 2 个链表
// 通过这段代码就避免了添加数据需要再次 hash puVal() 的低效率问题
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 低位存储在 loHead 中
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else { // 否则放入 hiHead 链表中也就是 原索引槽位 + oldCap
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;
}
当红黑树中结点数据小于 6 的时候，会退化为链表，这里我们主要来看这段代码，满足这个条件的链表将被放置到原先槽位位置上，否则就要放到 槽位索引 + oldCap 的位置上，为什么呢？
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
这里来举个例子，假如 hash(key-A) = 14，cap = 16 那么老的槽位链表位置为 14&(16 - 1) = 14 这个位置，那么在扩容的时候因为 cap 都是 2 倍扩容，是一样新的 cap = 32，那么之前槽位 14 的槽位链表数据是否需要做迁移呢？一个简单的想法就是
- 如果得到的索引槽位一样则无需做改变可以存放在原位置
- 否则要进行迁移
- java8 之前是调用 putVal() 在做一次 hash & length - 1 存储数据，java 8 做了优化
14 & (32 - 1) = 14 表明这个数据无需做迁移，看看 e.hash & oldCap = 14 & 16 = 0 表明在原先位置，这里需要注意的一个点是 cap 容量始终为 2^n 意味着只有比它大的数据做 & 数据只会是 16，比如 (17, 18, 19 .... n) & 16 = 16，而 16 正好是当前扩容的一个单位，所以 e.hash >= 16 的数据，会被放到原先槽位 + 16 的位置上。
获取数据
public V get(Object key) {
Node<K,V> e;
// 先计算其 hash 值然后调用 getNode
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 的 hash 相等
// 并且他们的 key 相等（== 和 equals）
// 那么槽位中的数据就是目标数据直接返回即可
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 如果槽位中存在链表
if ((e = first.next) != null) {
// 如果是红黑树就去红黑树中找 -- TODO
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;
}
删除数据
搞懂了是如何插入数据和添加数据的，删除数据其实也很简单
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
// 如果 table 中存在 key 对应的 hash 值
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;
// 如果 key 就是对应槽位的 key 则找到数据
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
// 去槽位链表中查找
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);
}
}
// 如果找到了 key 对应的值
// 根据后续的判断确定是否需要删除对应的数据结点
// 默认 remove, matchValue: false 需要进行删除
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);
// 如果是 table 槽位上的值，则将其下一个结点复制到槽位上
else if (node == p)
tab[index] = node.next;
// 如果在槽位链表上删除当前节点
else
p.next = node.next;
// 修改次数 + 1 用于迭代器 fail-fast
++modCount;
// 数据长度 - 1
--size;
// 删除后要做的事情留个子类实现
afterNodeRemoval(node);
return node;
}
}
return null;
}
清空map
public void clear() {
Node<K,V>[] tab;
// 修改次数 + 1
modCount++;
// 如果 table 不为空
if ((tab = table) != null && size > 0) {
// 重置 size 属性
size = 0;
// 遍历将每个槽位数据置位 null
for (int i = 0; i < tab.length; ++i)
tab[i] = null;
}
}
是否包含某个值
public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
// 如果 table 不为空
if ((tab = table) != null && size > 0) {
// 遍历 map 所有槽位
for (int i = 0; i < tab.length; ++i) {
// 遍历每个槽位链表如果找到则返回 true
for (Node<K,V> e = tab[i]; e != null; e = e.next) {
if ((v = e.value) == value ||
(value != null && value.equals(v)))
return true;
}
}
}
return false;
}
转载自:https://juejin.cn/post/6844903940421582861