目录
写在前面的话
本文是在前辈文章的基础上,结合自身的理解最终创作而成的。刚开始尝试写博客,画图能力实在是太差了,文中部分截图取自 dreamcatcher-cx 的博客,对知识点的解读则来自于自身,希望能帮助到大家,也再次感谢 dreamcatcher-cx 大佬。
核心源码解读
一些关键静态常量
依次对 HashMap 中定义的几个静态常量进行解释
DEFAULT_INITIAL_CAPACITY
默认的元素个数,如果初始化 hashMap 时未指定initialCapacity,则默认为 16。_MAXIMUM_CAPACITY _
最大的元素个数,初始化时超过这个数字则会被强制指定为当前数字,默认为 1 左移 30 位,即 1073741824
DEFAULT_LOAD_FACTOR
扩容因子,当【元素的个数】 > 【table.size * 扩容因子】时,触发 table 数组扩容为 2 倍。TREEIFY_THRESHOLD
产生哈希碰撞时会在数组对应下标处挂一条链表,当链表元素个数 > TREEIFY_THRESHOLD 时会转化为红黑树,默认值是 8。MIN_TREEIFY_CAPACITY
与上述 TREEIFY_THRESHOLD 相互作用,默认值为 64。新增节点的时候,如果单条链表上的元素达到 8 个了,但是 table 总的元素个数还没有超过 64,此时还是会优先选择扩容 table 数组,而不是转化为红黑树。
当 table 数组元素较少时,扩容比维护红黑树更具性价比吧。UNTREEIFY_THRESHOLD
当删除元素时,如果红黑树上的节点数量 < UNTREEIFY_THRESHOLD,则红黑树退化为链表。
可以作为 TREEIFY_THRESHOLD 的逆操作。
hash() 方法(降低碰撞的原理&2的幂次方的问题)
/**
* Computes key.hashCode() and spreads (XORs) higher bits of hash * to lower. Because the table uses power-of-two masking, sets of * hashes that vary only in bits above the current mask will * always collide. (Among known examples are sets of Float keys * holding consecutive whole numbers in small tables.) So we * apply a transform that spreads the impact of higher bits * downward. There is a tradeoff between speed, utility, and * quality of bit-spreading. Because many common sets of hashes * are already reasonably distributed (so don't benefit from * spreading), and because we use trees to handle large sets of * collisions in bins, we just XOR some shifted bits in the * cheapest possible way to reduce systematic lossage, as well as * to incorporate impact of the highest bits that would otherwise * never be used in index calculations because of table bounds. */static final int hash(Object key) {
// 在 obejct.hashCode() 的基础上右移 16 位。
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
右移 16 位这个操作的目的是什么?
一句话概括:右移操作后再进行异或操作,混合了高16位和低16位,增加了哈希复杂度,降低了哈希碰撞概率。
详解如下:
- 上图第一行是得到的 object.hashCode() 原始值的二进制。
- 通过右移 16 位后,原先高位的数值全部变成了 0,原先低位的部分则全部由原先的高位数值进行了覆盖。
- 再将 2 步骤后得到的值与原始的 hashCode 进行一次异或(不同为1,相同则为0)操作,也就得到了第三部分的数据。重点:异或操作结束之后,高位的数值全部保留下来了,低位的数据同时混杂了初始的 h 的低位数据+右移之后的低位数据(其实就是 h 的高位),由此得出【低位的复杂度更高了】,进而得出【哈希碰撞的概率更低了】。
- (n-1) & hash 这一步的结果就是元素在 table 数组中的下标,n 为 table 数组的大小,注意是数组大小,不是实际的元素的个数,在下一次触发扩容之前这个 n 都是固定的。
对取模操作的补充
hash 是一个 int 类型的数值,它的结果的范围是很大的,范围从-2147483648 到 2147483648,前后加起来大概 40 亿的映射空间,但是我们真正初始化的 table 数组的大小是固定的,并且是很小的,默认值只有 16 ,一般业务代码里也就几百几千的数量级。那要将 hash 散列分布到 table 数组中,常见的就是取模。
取模操作对应的操作符为 %,和上图的 & 也不是同一个,是错误吗?
不是的。& 为【与】操作,相比之下性能比%更好,那在什么情况下可以通过 & 来替代 % 完成取模的操作呢?如下图
通过上图也解答了为什么 table 的数量一定是 2 的幂次方。
(2 的幂次方-1)一定是奇数,低位后几位一定是 1 ,1 在进行 & 操作的时候才有可能产生 1 和 0 这两种答案,如果是 0 去执行 & 操作那结果必然是 0,也就是说 1 的结果更加随机,可能性更多,哈希碰撞的概率更低。
此外,如果最终得出来的结果中,某一位一定为 0 的话,那这个 hash 函数就一定取不到某些值,那对应一些 table 的下标就一定不会被放入元素,也就造成了空间的浪费。为什么要对低位的 16 位左这些操作,为什么不对高位做?
hash 这些步骤的最终目的是为了得到 table 数组的下标,而 table 数组一般也就几百几千的数量级,转换成二进制都在后 16 位,所以低位才是关键,高位全是 0,在 & 操作执行完之后也是 0。高位也可以做一些操作,但是性价比很低。
get()方法
概括一下步骤
- 根据 hash 值找到 table 数组的下标,核心是 (n - 1) & hash 这一步操作。
- 找到对应下标后,优先判断第一个元素,判断的方法就是对比 key 和 equals 方法。
- 如果第一个元素不满足,则往下遍历。遍历前先判断是红黑树还是链表。
public V get(Object key) {
Node<K,V> e;
// hash(key) 就是上述介绍的哈希方法
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 &&
// (n-1) & hash 定位到 tab 数组的下标
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((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;
}
put() 方法
概括一下步骤
- 新增之前先判断 table 长度,如果为 0 则进行初始化。第一次一定为 0,懒加载。
- 通过 hash 找到对应的 table 下标位置,为空则直接新建,不为空则处理哈希冲突。
- 处理哈希冲突时,同样按照红黑树和链表这两大类进行分类。
- 链表新增元素的过程中判断是否升级到树。
- 如果是旧元素,则直接替换并返回旧值,方法结束。
- 如果是新增元素,则自增 modCount。
public V put(K key, V value) {
// 入口,逻辑都在 putVal 中。
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
// put 元素之前先判断容量,如果为 0 则先进行初始化操作
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
// 如果 table 数组对应下标位置当前为空,则直接创建新的 node 节点插入
tab[i] = newNode(hash, key, value, null);
else {
// 进到这个 else 中说明 table 数组对应下标不为空,说明有可能产生了哈希冲突
Node<K,V> e; K k;
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;
}
}
// 走到这一步的时候,e 已经被赋值。e 可能是 table 中现有的某个元素,也可能是新增的。如果是现有的,则直接用新的值覆盖,并且返回旧的元素,并且直接 return 了。
if (e != null) {
// existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// 注意:如果是对已经存在的节点的修改,那么上面就已经 returen 了,能走到这里说明插入了新的节点,就会涉及到 table 结构的变更,产生变更的时候就需要更新 modCount。
// 这个 modCount 的更新非常重要,它就是 Fail-fast 的核心。
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
Fail-Fast 快速失败机制
public final void forEach(Consumer<? super K> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e.key);
}
// 在迭代的过程中检查 modCount 和 mc 的数量是否一致,如果过程中有其他线程改变了 modCount 数量,比如删除或者新增了元素,则直接抛出异常。
// 这也说明了 hashMap 本身不是线程安全的。
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
常见问题
table 数组的元素个数为什么要是 2 的幂次方?
上述对 hash() 方法的解释中已经解答了。概括一下就是:
- 当容量为 2 的幂次方时,上述公式才能成立,才能使用 & 操作替代 % 操作,才能提升性能。
- 低位全是 1 ,位运算的时候可以充分散列,增加哈希的随机性,降低了冲突可能性。
- 确保 table 数组的某些下标不会空置,从而降低了空间浪费的可能。
HashMap 中如果只重写 equals 方法,但是没有重写 hashCode 方法,会是什么表现?
如果业务上对【相等】这个概念有自己的定义,比如两个对象的 id 字段相等我们就认为这两个对象是相等的。那么对于两个不同的对象,但是拥有相同的 id,此时 hashCode 的值可能是不一样的(也可能碰巧一样),那么取值的时候可能会出现和业务预期不符的情况。
public class MyTest {
private static class Person{
int idCard;
String name;
public Person(int idCard, String name) {
this.idCard = idCard;
this.name = name;
}
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o == null || getClass() != o.getClass()){
return false;
}
Person person = (Person) o;
//两个对象是否等值,通过idCard来确定
return this.idCard == person.idCard;
}
}
public static void main(String []args){
HashMap<Person,String> map = new HashMap<Person, String>();
Person person = new Person(1234,"乔峰");
//put到hashmap中去
map.put(person,"天龙八部");
//get取出,从逻辑上讲应该能输出“天龙八部”
System.out.println("结果:"+map.get(new Person(1234,"萧峰")));
}
}
HashMap 是线程安全的吗?多线程场景下会有什么表现?
不是。多线程情况下,如果某个线程新增 or 删除了节点,会导致 modCount 自增,而在另一个线程迭代过程中如果感知到了 modCount 的不一致,则会抛出 ConcurrentModificationException 异常,也就是快速失败。
关联知识点
既然 HashMap 不是线程安全的,那么线程安全的 ConcurrentHashMap 又是怎么实现的呢?
优秀博客参考
- https://www.cnblogs.com/chengxiao/p/6059914.html