大厂真实面试：HashMap八连问，逐渐深入

文章内容来自B站UP主【Tom弹架构】 已经过作者本人授权同意将问题记录至博客 原文链接： 大厂一面Java高级开发月薪38K，也不算太难，HashMap八连问，大家看我回答的怎么样 转载请注明出处，侵权必究 Tom出品，必属精品

HashMap的工作原理是什么？

回答：   HashMap的底层呢是通过数组加单向链表实现的，数组中的每一个元素都是一个链表结构，而链表中的每一个节点又是一个Entry对象，这个Entry对象呢，它是用来存储真正的K-V，也就是键值对的这个值。   在hashmap中有两个比较重要的方法，一个是get()方法，一个是put()方法。   我先说一下put方法吧，在存储K-V键值对的时候，我们首先会调用一个hash方法，然后通过这个方法，可以计算出Key的 Hash的值，从而得到一个10进制的数字，用这个数字和数组的长度减一去取模，就可以得到一个结果，也就是数组的下标，然后我们根据这个下标去找到数组中存储的这个单向链表，然后把链表中的每一个Key和要插入的Key进行一个equals()的比较，如果是相等的话，我们就直接更新这个value的值，也就是覆盖，如果不相等的话就把新的K-V值put()到这个链表中去，在put的过程中的话，我们当哈希表中存储键值对超过了数组长度乘以负载因子的时候，就会将这个数组扩容为两倍，还有就是在插入链表的时候，如果链表长度超过了我们默认设置的阈值为8的时候，结点的数据结构就会自动转化为一个红黑树的结构。   接下来就是再说一下get()方法吧，调用的时候和put方法也比较类似，同样也会先去调用hash方法，然后对key进行计算，用这个数字和数组的长度减一去取模，也就是数组的下标，然后我们再遍历这个下标对应的链表元素，再进行equals的比较，如果key相同的话，就把这个元素取回并返回给用户。   hashmap最核心的原理就是利用hash值来计算出这个下标的位置，然后再用equals比较，这一步主要是解决哈希冲突的问题

追问：你刚才提到了哈希表中，链表超长以后转化成红黑树，那这里为什么会使用红黑树呢？

  是这样的，红黑树是二叉查找树的一种，他的查找算法相当于是二分的查找，红黑树的时间复杂度O(log n)在数据比较多的时候会比列表的查询的时间复杂度O(n)要好很多

追问：那你认为hashmap可不可以不是用链表而直接使用红黑树呢？或者使用二叉搜索树，或者是AVL树之类的数组结构

  我认为hashmap之所以没有一开始就使用红黑树，应该是因为时间和空间的折中考虑吧，在哈希冲突比较小的时候，即使转化为红黑树之后，在时间复杂中上所产生的效果，其实也并不是特别大，而且呢，在put的时候效率可能会降低，毕竟每次put都会进行非常复杂的红黑树的这种旋转操作，另外在空间上的话，每个节点都需要去维护更多的一个指针，这就显得有点得不偿失了，最后就是HashMap之所以选择红黑树，而不是二叉搜索树，我认为最主要的原因就是二叉树在一些极端情况下，他会变成一个倾斜的结构，然后查找效率会退化成和链表差不多的效率，而红黑树它是一种平衡树，它可以防止这种退化，所以呢，可以保持这种平衡，因为红黑树又不像其它的完全的平衡二叉树那样有严格的平衡条件，所以呢，红黑树的插入效率要比完全的平衡二叉树要高，所以的话，hashmap在选择红黑树时，既可以避免级端情况下的退化，也可以兼顾查询和插入的这种效率

追问： 那请问hashmap是线程安全的吗？

  hashmap在设计的时候就是针对单线程环境去设计的，在多线程环境下它不是线程安全的。

追问：那既然不安全，多线程并发环境下,如果需要一个Hash结构,你如何实现呢？

  多线程并发环境下，我们可以使用ConcurrentHashMap来实现这样一个需求。

追问：那你对ConcurrentHashMap的底层实现原理的理解能说一下吗？

  ConcurrentHashMap的话，要分为两种分情况去进行分析，一个是在jdk1.7，然后就是1.8之后，他们的这个差别还是蛮大的。   1.7的话，底层是数组加链表实现的，然后呢，使用了分段锁来保证线程安全，它是将数组分成了16段，也就是，给每个Segment来配一把锁，然后在读每个Segment的时候就要先获取对应的锁，所以呢，它是最多能有16个线程并发去操作。   到了jdk1.8之后，它跟hashmap一样，使用了链表加红黑树，同时在并发处理方面不再使用分段锁的方式，而是采用 CAS 加synchronized关键字的方式实现一种更加细粒度的锁，相当于是把这个锁的控制控制在了这种更加细粒度的哈希桶的这个级别，然后在写入键值对的时候，这个可以锁住哈希桶的这种链表的这种这个头节点，这样的话，就不会影响到其它的哈希桶的写入，从而去提高对并发的这种处理能力。

追问：你刚才提到ConcurrentHashMap中，使用了synchronized关键字，那如果使用ReentrantLock来作为锁，你觉得可以吗？

  理论上来讲的话应该是可以的，但是我认为，这个synchronized关键字会更好一点吧，因为在JDK1.6之后对synchronized关键字也进行了一些优化它里面引入了偏向锁，然后轻量级锁以及重量级锁，这些在ReentrantLock中是没有的，并且随着JDK版本的这个升级，这个synchronized也在进一步的进行优化，因为这个ReentrantLock是用Java代码来实现的，所以在之后的话我认为很难有优化或者提升的空间了，所以让我选的话，我会优先选择synchronized。

追问：你刚才提到了synchronized关键字对于锁的优化，能介绍一下优化了什么吗？

  主要还是对锁的升级做了一些优化，它默认采用的是偏向锁，然后在程序运行中始终是(只有)有一个线程去获取这个synchronized的这个这么一个锁，那么Java对象中的话会记录了一个线程的ID，所以呢，我们在下次再获取这个synchronized的锁定的时候，只需要去比较这个线程ID就行了，在运行过程中如果出现第二个线程去请求synchronized锁的时候，这里就分两种情况   在没有发生并发竞争锁的情况下，这个synchronized就会自动升级成为轻量级锁，这个时候，第二个线程就会尝试自旋锁的方式来获取锁因为很快就能拿到锁所以第二个线程也不会阻塞。   但是如果出现这种两个线程竞争锁的情况的话，这个synchronized它会升级为重量级锁，那么这个时候就是只会有一个线程能够获取到锁，那么另外一个线程它会阻塞然后要等待第一个线程释放锁之后才能去拿到锁