WLQ's Blog
0%

HashMap总结

发表于 更新于 分类于

默认初始长度为16，每次扩容一倍

HashMap在并发插入元素的扩容时，会出现线程安全问题，可能会出现环形链表，让下一次读操作出现死循环

扩容源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            //jdk1.7的头插法，这会导致resize的时候链表顺序颠倒
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

.image-20220220142747615

该部分参考文章 https://mp.weixin.qq.com/s/dzNq50zBQ4iDrOAhM4a70A

为什么负载因子是0.75？

.image-20220307204753962

  • 当负载因子为1.0时，会产生较多的Hash冲突，红黑树变得比较复杂，查询效率降低
  • 当负载因子为0.5时，会增加额外的空间消耗

所以0.75是时间和空间的权衡结果，源码注释中也提到了这一点

为什么链表和红黑树转换的阈值是8？

按照源码解释，**TreeNode的大小是ListNode的两倍，所以应该尽量减少使用**

当负载因子为0.75时，链表长度$k$和概率$p$服从$λ=\frac{1}{2}$的泊松分布，即
$$
p(k)=\frac{λ^ke^{-λ}}{k!}=\frac{1}{2^kk!\sqrt{e}}
$$

1
2
3
4
5
6
7
8
9
10
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

JDK1.7和1.8的区别

JDK1.7 JDK1.8
数据结构 数组+链表 数组+链表+红黑树(链表长度>8)
插入方式 头插法(LRU思想)(会出现环形链表) 尾插法
扩容 链表逆序(头插法导致) 链表原序
rehash hashCode()->扰动处理->hash&(capacity-1) 原位置 or 原位置+capacity

HashMap与HashTable的区别

HashMap HashTable
并发性 主要方法无synchonized关键字 主要方法均有synchonized关键字
key值是否允许为null 允许 NullPointerException
默认初始容量 16 11
扩容 *2 *2+1