HashMap常见面试题

待我称王封你为后i 2023-01-03 04:49 102阅读 0赞

## HashMap，HashTable，ConcurrentHashMap之间的区别 ##

<table> 
 <thead> 
  <tr> 
   <th>对象</th> 
   <th>key和value是否允许为空</th> 
   <th>是否线程安全</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>HashMap</td> 
   <td>key和value都允许为null</td> 
   <td>否</td> 
  </tr> 
  <tr> 
   <td>HashTable</td> 
   <td>key和value都不允许为null</td> 
   <td>是</td> 
  </tr> 
  <tr> 
   <td>ConcurrentHashMap</td> 
   <td>key和value都不允许为null</td> 
   <td>是</td> 
  </tr> 
 </tbody> 
</table>

## HashMap在什么条件下扩容 ##

**jdk1.7**

1.  超过扩容的阈值
2.  发生碰撞

**jdk1.8**

1.  超过扩容的阈值

## HashMap的大小为什么是2 n ##

为了通过hash值确定元素在数组中存的位置，我们需要进行如下操作`hash%length`，当时%操作比较耗时间，所以优化为 `hash & (length - 1)`

**当length为2的n次方时**，`hash & (length - 1) =hash % length`

我们假设数组的长度为15和16，hash码为8和9

<table> 
 <thead> 
  <tr> 
   <th>h &amp; (length - 1)</th> 
   <th>h</th> 
   <th>length</th> 
   <th>index</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>8 &amp; (15 - 1)</td> 
   <td>0100</td> 
   <td>1110</td> 
   <td>0100</td> 
  </tr> 
  <tr> 
   <td>9 &amp; (15 - 1)</td> 
   <td>0101</td> 
   <td>1110</td> 
   <td>0100</td> 
  </tr> 
  <tr> 
   <td>8 &amp; (16 - 1)</td> 
   <td>0100</td> 
   <td>1111</td> 
   <td>0100</td> 
  </tr> 
  <tr> 
   <td>9 &amp; (16 - 1)</td> 
   <td>0101</td> 
   <td>1111</td> 
   <td>0101</td> 
  </tr> 
 </tbody> 
</table>

可以看出数组长度为15的时候，hash码为8和9的元素被放到数组中的同一个位置形成链表，键低了查询效率，当hahs码和15-1(1110)进行&时，最后一位永远是0，这样0001，0011，0101，1001，1011，0111，1101这些位置永远不会被放置元素，这样会导致

1.  空间浪费大
2.  增加了碰撞的几率，减慢查询的效率

当数组长度为2 n时，2 n −1的所有位都是1，如8-1=7即111，那么进行低位&运算时，值总与原来的hash值相同，降低了碰撞的概率

## JDK1.8发生了哪些变化？ ##

1.  由数组+链表改为数组+链表+红黑树，当链表的长度超过8时，链表变为红黑树。  
    **为什么要这么改？**  
    我们知道链表的查找效率为O(n)，而红黑树的查找效率为O（logn），查找效率变高了。  
    **为什么不直接用红黑树？**  
    因为红黑树的查找效率虽然变高了，但是插入效率变低了，如果从一开始就用红黑树并不合适。从概率学的角度选了一个合适的临界值为8
2.  优化了hash算法
3.  计算元素在新数组中位置的算法发生了变化，新算法通过新增位判断oldTable\[i\]应该放在newTable\[i\]还是newTable\[i+oldTable.length\]
4.  头插法改为尾插法，扩容时链表没有发生倒置（避免形成`死循环`）

## HashMap在高并发下会发生什么问题？ ##

1.  多线程扩容，会让链表形成环，从而造成死循环
2.  多线程put可能导致元素丢失  
    **jdk1.8中死循环问题已经解决，元素丢失问题还存在**

## 如何避免HashMap在高并发下的问题？ ##

1.  使用ConcurrentHashMap
2.  用Collections.synchronizedMap(hashMap)包装成同步集合