[Java]面试官你能不能别问我 HashMap 了?

分手后的思念是犯贱 2022-12-24 15:50 245阅读 0赞

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

# HashMap 的底层数据结构 #

先来聊聊 HashMap 的底层数据结构  
HashMap 的底层数据结构, 1.7 版本和 1.8 版本是有些不同的,但大体上都是 数组 + 链表 的形式来实现的  
1.7 版本是这个样子:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3psbF8wNDA1_size_16_color_FFFFFF_t_70_pic_center]  
1.8 版本是这样:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3psbF8wNDA1_size_16_color_FFFFFF_t_70_pic_center 1]  
很明显就能看出来, 1.8 版本怎么多了一个树?还是红黑的?  
这就要来分析 1.7 版本 HashMap 的实现有什么不足了.  
1.7 版本主要就是 数组 + 链表,那么如果有一个 hash 值总是会发生碰撞,那么由此对应的链表结构也会越来越长,这个时候如果再想要进行查询操作,就会非常耗时,所以该如何优化这一点就是 1.8 版本想要实现的  
1.8 版本采用了 数组 + 链表 + 红黑树 的方式去实现,当链表的长度大于 8 时,就会将链表转为红黑树.

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

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

在理想情况下 & 随机哈希码,哈希表中节点的频率遵循泊松分布,而根据统计,忽略方差,列表长度为 K 的期望出现的次数是以上的结果,可以看到其实在为8的时候概率就已经很小了,再往后调整并没有很大意义,故而选取 8  
为什么是小于 6 的时候转为链表,而不是 7 的时候就转为链表呢?频繁的从链表转到红黑树,再从红黑树转到链表,开销会很大,特别是频繁的从链表转到红黑树时,需要旋转

为什么将链表转为红黑树,而不是平衡二叉树( 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` 那么此时就会发生扩容,具体如下图:  
![在这里插入图片描述][20201129192459721.jpg_pic_center]  
扩容完毕之后,因为采用的是头插法,所以后面的元素会放在头部位置,那么就可能会这样:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3psbF8wNDA1_size_16_color_FFFFFF_t_70_pic_center 2]  
刚开始记录的是 `A.next = B` ,经过扩容之后是 `B.next = A` ,那么最后可能就是这样了:  
![在这里插入图片描述][20201129193349908.jpg_pic_center]  
明显看到造成了死循环,比较好的是, 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 版本具体的实现,等等等等  
但是这篇文章已经比较长了,就写到这里吧~  
感谢您的阅读哇

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3psbF8wNDA1_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/f15282a03cdf48dd91a38aefe86b77f9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3psbF8wNDA1_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/4849d5da06c840a1b2b49526aafaa9c8.png
[20201129192459721.jpg_pic_center]: https://img-blog.csdnimg.cn/20201129192459721.jpg#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3psbF8wNDA1_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20201129193144151.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3psbF8wNDA1,size_16,color_FFFFFF,t_70#pic_center
[20201129193349908.jpg_pic_center]: https://img-blog.csdnimg.cn/20201129193349908.jpg#pic_center