HashMap面试题

灰太狼 2022-11-22 12:39 139阅读 0赞

# HashMap指南 #

## 面试题： ##

1.  JDK8中的HashMap有哪些改动？
2.  HashMap的工作原理吗？
3.  HashMap中的“死锁”是怎么回事？
4.  HashMap的扩容机制是怎么样的？JDK7与JDK8有什么不同吗？
5.  HashMap是线程安全的吗？为什么？
6.  HashMap添加的对象为什么要重写equals和hashcode？
7.  JDK8中为什么要使用红黑树？

## JDK8中的HashMap有哪些改动 ##

JDK7-HashMap是用位桶+链表的形式  
JDK8-HashMap是用位桶+链表/红黑树的形式 （冲突节点数不小于8-1时，转换成红黑树。）  
*深处的还需要去了解下面这些？*  
1：什么是桶排序？  
2：红黑树  
3：get是如何获取数据  
4：扩容机制resize()

## HashMap的工作原理吗？ ##

HashMap的工作原理 ：HashMap是基于散列法（又称哈希法）的原理，使用put(key, value)存储对象到HashMap中，使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时，我们先对键调用hashCode()方法，返回的hashCode用于找到bucket（桶）位置来储存Entry对象。HashMap是在bucket中储存键对象和值对象，作为Map.Entry。并不是仅仅只在bucket中存储值

## HashMap中的“死锁”是怎么回事？ ##

HashMap会造成死锁，因为HashMap是线程非安全的，多并发的情况容易造成死锁，若要高并发推荐使用ConcurrentHashMap；  
二个进程T1、T2，HashMap容量为2,T1线程放入key A、B、C、D、E。在T1线程中A、B、C Hash值相同，于是形成一个链接，假设为A->C->B，而D、E Hash值不同，于是容量不足，需要新建一个更大尺寸的hash表，然后把数据从老的Hash表中  
迁移到新的Hash表中(refresh)。这时T2进程闯进来了，T1暂时挂起，T2进程也准备放入新的key，这时也  
发现容量不足，也refresh一把。refresh之后原来的链表结构假设为C->A，之后T1进程继续执行，链接结构  
为A->C,这时就形成A.next=B,B.next=A的环形链表。一旦取值进入这个环形链表就会陷入死循环。  
产生死锁的根本原因就是在高并发条件下，hashmap扩容的时候产生头尾相连出现死循环而导致的。  
**解决办法**：  
使用ConcurrentHashMap进行替代hash,利用ConcurrentHashMap的线程安全，加锁（sgement）的方式，内部的结构可以让其在进行写操作的时候能够将锁的粒度

## HashMap的扩容机制是怎么样的？JDK7与JDK8有什么不同吗？ ##

HashMap扩容：  
JDK7的时候，Hashmap扩容的时候，当有新的元素进来的时候，他不仅仅会判断是否大于阈值，还会看当前的数组位置是否为空，就算这时候已经大于阈值了，但是当前数组位置为空的时候，他也不会扩容，数组扩容只有一个办法：只能把元素存入一个新的数组。  
JDK1.8中在计算新位置的时候并没有跟1.7中一样重新进行hash运算，而是用了原位置+原数组长度这样一种很巧妙的方式，而这个结果与hash运算得到的结果是一致的，只是会更块。rehash之后，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。

JDK1.7 HashMap的结构： Entry数组+链表  
JDK1.8 HashMap的结构: Node数组+链表+红黑树  
***存储原理***  
根据上面图片, 我们可以看出, 如果 HashMap 的每个 bucket 里只有一个 Entry 时，HashMap 可以根据索引、快速地取出该 bucket 里的 Entry；在发生“Hash 冲突”的情况下，单个 bucket 里存储的不是一个 Entry，而是一个 Entry 链，系统只能必须按顺序遍历每个 Entry，直到找到想搜索的 Entry 为止——如果恰好要搜索的 Entry 位于该 Entry 链的最末端（该 Entry 是最早放入该 bucket 中），那系统必须循环到最后才能找到该元素。  
***负载因子和扩容***  
initailCapacity \* loadFactor = HashMap容量  
当创建 HashMap 时，有一个默认的负载因子（load factor），其默认值为 0.75，这是时间和空间成本上一种折衷：增大负载因子可以减少 Hash 表（就是那个 Entry 数组）所占用的内存空间，但会增加查询数据的时间开销，而查询是最频繁的的操作（HashMap 的 get() 与 put() 方法都要用到查询）；减小负载因子会提高数据查询的性能，但会增加 Hash 表所占用的内存空间。

如果开始就知道 HashMap 会保存多个 key-value 对，可以在创建时就使用较大的初始化容量，如果 HashMap 中 Entry 的数量一直不会超过极限容量（capacity \* load factor），HashMap 就无需调用 resize() 方法重新分配 table 数组，从而保证较好的性能。

HashMap的大小很简单，不是实时计算的，而是每次新增加Entry/Node的时候，size就递增。删除的时候就递减。当到达阈值(负载因子\*总size)时, 容量翻倍, 并且永远是2^n, 因为hash取模运算太慢, 2^n的容量可以进行位运算

jdk 1.7 头插  
jdk 1.8+ 尾插

因为hashmap在并发resize时会出现的死循环问题, 并且1.7时候用头插是考虑到了一个所谓的热点数据的点(新插入的数据可能会更早用到)，但这其实是个伪命题, 因为JDK1.7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置(就是因为头插) 所以最后的结果 还是打乱了插入的顺序 所以总的来看支撑1.7使用头插的这点原因也不足以支撑下去了 所以就干脆换成尾插 一举多得

## HashMap是线程安全的吗？为什么？ ##

答：不安全  
原因：hashmap在高并发的情况下执行扩容会出现死锁的问题。  
面试官还会问：产生死锁的原因是什么？如何解决？采用这种方式将会带来哪些问题？  
死锁：多线程下扩容的时候产生死循环，采用ConcurrentHashMap来代替hashmap,带来的问题是ConcurrentHashMap的效率低，

## HashMap添加的对象为什么要重写equals和hashcode ##

在我们的业务系统中判断对象时有时候需要的不是一种严格意义上的相等，而是一种业务上的对象相等。在这种情况下，原生的equals方法就不能满足我们的需求了  
所以这个时候我们需要重写equals方法，来满足我们的业务系统上的需求。那么为什么在重写equals方法的时候需要重写hashCode方法呢？  
Object.hashCode的通用约定：  
1：在一个应用程序执行期间，如果一个对象的equals方法做比较所用到的信息没有被修改的话，那么，对该对象调用hashCode方法多次，它必须始终如一地返回 同一个整数。在同一个应用程序的多次执行过程中，这个整数可以不同，即这个应用程序这次执行返回的整数与下一次执行返回的整数可以不一致。  
2：如果两个对象根据equals(Object)方法是相等的，那么调用这两个对象中任一个对象的hashCode方法必须产生同样的整数结果。  
3：如果两个对象根据equals(Object)方法是不相等的，那么调用这两个对象中任一个对象的hashCode方法，不要求必须产生不同的整数结果。然而，程序员应该意识到这样的事实，对于不相等的对象产生截然不同的整数结果，有可能提高散列表（hash table）的性能。

HashSet和HashMap这些基于散列值（hash）实现的类。HashMap的底层处理机制是以数组的方法保存放入的数据的(Node<K,V>\[\] table)，其中的关键是数组下标的处理。数组的下标是根据传入的元素hashCode方法的返回值再和特定的值异或决定的。如果该数组位置上已经有放入的值了，且传入的键值相等则不处理，若不相等则覆盖原来的值，如果数组位置没有条目，则插入，并加入到相应的链表中。检查键是否存在也是根据hashCode值来确定的。所以如果不重写hashCode的话，可能导致HashSet、HashMap不能正常的运作、

如果我们将某个自定义对象存到HashMap或者HashSet及其类似实现类中的时候，如果该对象的属性参与了hashCode的计算，那么就不能修改该对象参数hashCode计算的属性了。有可能会移除不了元素，导致内存泄漏。  
总结：  
1.new Object(),JVM根据这个对象的Hashcode值,放入到对应的Hash表对应的Key上,如果不同的对象确产生了相同的hash值,也就是发生了Hash key相同导致冲突的情况,那么就在这个Hash key的地方产生一个链表,将所有产生相同hashcode的对象放到这个单链表上去,串在一起。

2.比较两个对象的时候,首先根据他们的hashcode去hash表中找他的对象,当两个对象的hashcode相同,那么就是说他们这两个对象放在Hash表中的同一个key上,那么他们一定在这个key上的链表上。那么此时就只能根据Object的equal方法来比较这个对象是否equal。当两个对象的hashcode不同的话，肯定他们不能equals.

## JDK8中为什么要使用红黑树 ##

原因：jdk1.8版本后，Java对HashMap做了改进，在链表长度大于8的时候，将后面的数据存在红黑树中，以加快检索速度  
***红黑树的特征：***  
1：每个节点或者是黑色，或者是红色。  
2：根节点是黑色。  
3：每个叶子节点（NIL）是黑色。 \[注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！\]  
4：如果一个节点是红色的，则它的子节点必须是黑色的。  
5：从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。  
***红黑树的优势***  
红黑树相比avl树，在检索的时候效率其实差不多，都是通过平衡来二分查找。但对于插入删除等操作效率提高很多。红黑树不像avl树一样追求绝对的平衡，他允许局部很少的不完全平衡，这样对于效率影响不大，但省去了很多没有必要的调平衡操作，avl树调平衡有时候代价较大，所以效率不如红黑树，在现在很多地方都是底层都是红黑树的天下啦。

红黑树的高度只比高度平衡的AVL树的高度（log2n）仅仅大了一倍，在性能上却好很多。  
***总结：***  
java8不是用红黑树来管理hashmap，而是在hash值相同的情况下（且重复数量大于8），用红黑树来管理数据。 红黑树相当于排序数据，可以自动的使用二分法进行定位，性能较高。一般情况下，hash值做的比较好的话基本上用不到红黑树。

红黑树牺牲了一些查找性能 但其本身并不是完全平衡的二叉树。因此插入删除操作效率略高于AVL树。  
AVL树用于自平衡的计算牺牲了插入删除性能，但是因为最多只有一层的高度差，查询效率会高一些。