2020-11-29

|

2020-12-05

| java

| 0

如果你是个 Java 程序员,那一定对 HashMap 不陌生,巧的是只要你去面试,大概率都会被问到 HashMap 的相关内容
基于此,就总结一篇,争取不让面试官问倒~

HashMap 的底层数据结构

先来聊聊 HashMap 的底层数据结构
HashMap 的底层数据结构, 1.7 版本和 1.8 版本是有些不同的,但大体上都是 数组 + 链表 的形式来实现的
1.7 版本是这个样子:

1.8 版本是这样:

很明显就能看出来, 1.8 版本怎么多了一个树?还是红黑的?
这就要来分析 1.7 版本 HashMap 的实现有什么不足了.
1.7 版本主要就是 数组 + 链表,那么如果有一个 hash 值总是会发生碰撞,那么由此对应的链表结构也会越来越长,这个时候如果再想要进行查询操作,就会非常耗时,所以该如何优化这一点就是 1.8 版本想要实现的
1.8 版本采用了 数组 + 链表 + 红黑树 的方式去实现,当链表的长度大于 8 时,就会将链表转为红黑树.

这个时候问题就来了,为什么会将链表转红黑树的值设定为 8 ?
这个问题我们或许可以从源码中窥探一二:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Ideally, under random hashCodes, the frequency of nodes in bins follows a Poisson distribution 
with a parameter of about 0.5 on average for the default resizing threshold of 0.75, although 
with a large variance because of resizing granularity. Ignoring variance, the expected 
occurrences of list size k are (exp(-0.5) * pow(0.5, k) / factorial(k)). 
The first values are:
      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

为什么将链表转为红黑树,而不是平衡二叉树( AVL 树)呢?

• 因为 AVL 树比红黑树保持着更加严格的平衡, AVL 树中从根到最深叶的路径最多为 1.44lg(n + 2) ,红黑树中则最多为 2lg( n + 1) ,所以 AVL 树查找效果会比较快,如果是查找密集型任务使用 AVL 树比较好,相反插入密集型任务,使用红黑树效果就比较 nice
• AVL 树在每个节点上都会存储平衡因子
• AVL 树的旋转比红黑树的旋转更加难以平衡和调试,如果两个都给 O(lgn) 查找, AVL 树可能需要 O(log n) 旋转,而红黑树最多需要两次旋转使其达到平衡

HashMap 为什么是线程不安全的?

HashMap 的线程不安全主要体现在两个方面: 扩容时导致的死循环 & 数据覆盖
扩容时导致的死循环,这个问题只会在 1.7 版本及以前出现,因为在 1.7 版本及以前,扩容时的实现,采用的是头插法,这样就会导致循环链表的问题
什么时候会触发扩容呢?如果存储的数据,大于 当前的 HashMap 长度( Capacity ) * 负载因子( LoadFactor ) 时,就会发生扩容.比如当前容量是 16 , 16 * 0.75 = 12 ,当存储第 13 个元素时,经过判断发现需要进行扩容,那么这个时候 HashMap 就会先进行扩容的操作
扩容也不是简简单单的将原来的容量扩大就完事儿了,扩容时,首先创建一个新的 Entry 空数组,长度是原数组的 2 倍,扩容完毕之后还会再进行 ReHash ,也就是将原 Entry 数组里面的数据,重新 hash 到新数组里面去
假设现在有一个 Entry 数组,大小是 2 ,那么当我们插入第 2 个元素时,大于 2 * 0.75 那么此时就会发生扩容,具体如下图:

扩容完毕之后,因为采用的是头插法,所以后面的元素会放在头部位置,那么就可能会这样:

刚开始记录的是 A.next = B ,经过扩容之后是 B.next = A ,那么最后可能就是这样了:

明显看到造成了死循环,比较好的是, 1.8 版本之后采用了尾插法,解决了这个问题
还有个问题, 1.8 版本是没有解决的,那就是数据覆盖问题
假设现在线程 A 和线程 B 同时进行 put 操作,特别巧的是这两条不同的数据 hash 值一样,并且这个位置数据为 null ,那么是不是应该让线程 A 和 B 都执行 put 操作.假设线程 A 在要进行插入数据时被挂起,然后线程 B 正常执行将数据插入了,然后线程 A 获得了 CPU 时间片,也开始进行数据插入操作,那么就将线程 B 的数据给覆盖掉了
因为 HashMap 对 put 操作没有进行加锁的操作,那么就不能保证下一个线程 get 到的值,就一定是没有被修改过的值,所以 HashMap 是不安全的

那既然 HashMap 线程不安全,你给推荐一个安全的?

如果推荐的话,那肯定推荐 ConcurrentHashMap ,说到 ConcurrentHashMap 也有一个比较有趣的事情,那就是 ConcurrentHashMap 的 1.7 版本和 1.8 版本实现也不是很一样
在 1.7 版本, ConcurrentHashMap 采用的是分段锁( ReentrantLock + Segment + HashEntry )实现,也就是将一个 HashMap 分成多个段,然后每一段都分配一把锁,这样去支持多线程环境下的访问.但是这样锁的粒度太大了,因为你锁的直接就是一段嘛
所以 1.8 版本又做了优化,使用 CAS + synchronized + Node + 红黑树 来实现,这样就将锁的粒度降低了,同时使用 synchronized 来加锁,相比于 ReentrantLock 来说,会节省比较多的内存空间

HashMap 这块,其实还可以扩展,比如 HashMap 和 HashTable 的区别, ConcurrentHashMap 1.7 版本和 1.8 版本具体的实现,等等等等
但是这篇文章已经比较长了,就写到这里吧~
感谢您的阅读哇