面试题总结——HashMap与ConcurrentHashMap

逃离我推掉我的手 2023-06-08 04:39 17阅读 0赞

## 面试题总结——HashMap与ConcurrentHashMap ##

###   HashMap ###

>   **1、`HashXXX(HashSet,HashMap)和TreeXXX(TreeSet,TreeMap)的区别？`**

①**底层实现**：HashXXX底层基于哈希表+红黑树；TreeXXX底层基于红黑树  
   ②**元素要求**：HashXXX是无序存储，允许存放null(Set是key，Map是key+value)；TreeXXX是有序存储（与比较器有关），不允许存放null(Set是key，Map是key+value)  
   ③**使用要求**：使用HashXXX存储的类需要覆写hashCode()+equals()；使用TreeXX需要实现Comparable接口或传入Comparator比较器

>   **2、HashMap底层究竟是如何实现？**

HashMap的底层：JDK1.8，HashMap采用位桶数组+链表+红黑树实现，HashMap采用`懒加载`，当第一次put时才会初始化哈希表(resize()方法)。默认数组初始化长度为16(1<<4)。

**HashMap的`插入或更新`流程（put方法）**：当添加一个元素时，首先计算元素key的hash值，以此确定插入Entry数组中的位置（见下面对哈希函数的处理），若当前位置没有元素，就将key-value封装为Node(Map.Entry)放在该位置，若有元素(相同hash值)，则遍历这个链表，看该链表中有没有哪个节点的key与当前key相同，若相同，则将该节点的key所对应的value修改为当前key所对应的value；若没有相同的，则将当前key-value所对应的结点插入到链表尾部。如果链表长度超过阈值(8)，链表转换为红黑树。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA_size_16_color_FFFFFF_t_70]

**HashMap的`查找或删除`流程（get方法，remove方法）**：根据HashMap的哈希函数+(n-1)&hash，求得当前key所在数组中的位置，遍历该数组中的节点（无论是链表还是红黑树），寻找与key相同的结点，若存在，返回该结点中的value值或将该节点删除，若不存在，返回null。

>   **3、HashMap到底是怎样确定当前元素在数组中的位置的？**

首先根据HashMap中的hash()函数(h=key.hashCode())^ (h >>> 16)：将key的hashCode的低16位和高16位做了个异或运算，确定当前key在HashMap中的hash值比较均匀。

再根据这个hash值确定对应数组位置：(n - 1) & hash，n代表HashMap数组的长度，由于HashMap数组的长度都是2的x次方，因此(n-1)&hash==hash%n，&运算的效率高于%，这刚好体现了HashMap的hash函数最终策略：`除留余数法`，最终得到数组的下标。

`总结的来讲`，元素在数组中的位置：`1`、将该元素hashCode的高16位与低16位进行异或(^)操作；`2`、将1得到的值与数组的长度-1(n-1)做按位与(&)操作得到该元素在数组中的位置。

>   **4、HashMap的初始化容量(数组长度)为什么都是2的次幂？**

当初始化大小为2的次方时，HashMap的效率最高。由于上面确定元素在数组中的位置说到底用的还是除留余数法，用的还是(n-1)&hash，如果n为2的次方，则n-1在二进制中就是一串全为1的格式，这样做&操作时，分布比较均匀，碰撞的几率较小，提高了查询效率，更符合哈希表的设计，最重要的是，此时的`hash&(n-1)==hash%n)`。  
  即便使用HashMap时传入的容量size不是2的次幂，在HashMap中也会使用tableSizeFor()方法将该size转换为`向上最近`的2的次幂。

>   **5、HashMap是如何解决Hash冲突的？**

HashMap通过`链地址法`解决Hash冲突，数组中的每一个单元都会指向一个链表，如果发生冲突，就将 put 进来的 K- V 插入到链表的`尾部`。当链表长度大于阈值`8`时，链表转换为红黑树。如果红黑树的节点数小于阈值`6`，红黑树又转换为链表。

>   **6、为什么当长度大于8才转换为红黑树，而节点数小于6转换为链表？**

红黑树结点TreeNode所占用的空间是链表结点Node的两倍，从时间和空间两个方面进行权衡，由于HashMap符合`泊松分布`，超过8的概率达到`十万分之一`，已经非常小了。才有这两个阈值的设定。

>   **7、HashMap的阈值与扩容策略是什么？**

HashMap在初始化或数组中元素个数超过阈值时，HashMap采用resize()进行扩容。

**阈值**：数组长度\*负载因子(默认为0.75，可通过构造方法传入)

**扩容策略**：扩容为原数组长度的`2倍`（原数组重新进行哈希定值），即便HashMap删除了很多个结点，也`不会缩容`，因此需要将该HashMap转移到新的HashMap中，将该HashMap丢弃掉。（避免浪费大量空间）

**`产生扩容的条件`**：①链表转红黑树时判断此时数组的长度是否小于阈值(64)，若小于，则不进行表到树的转换，而是将该数组扩容。②在添加元素时，所占数组的数量超过了阈值（n\*0.75）

**扩容方式**：一个数组在扩容后，新索引要么在原位置，要么在原位置+oldCapacity的位置上，扩容后，n的有效位相比之前会多增加一位，所以只需要判断hash在新增的有效位的位置上是0还是1，若是0，则索引没有变化还在原位，若是1，则索引变为原索引+oldCapacity。这样，`每次扩容不需要重新计算hash值`，直接在这两个位置上加即可。

>   **8、HashMap与HashTable的区别？**

**安全性**：HashMap是线程不安全的，效率高；HashTable是线程安全的，效率低。

**接收null值**：HashMap的key-value都可以是null，HashTable的key-value都不能是null。

**初始值即扩容策略**：HashMap初始值为16，扩容策略为n=2*n；HashTable初始值为11，扩容策略为n=2*n+1.

>   **9、HashMap为什么是线程不安全的？**

在put时会出现数据不一致，在扩容时可能导致死循环。请参考：[HashMap线程不安全][HashMap]

eg:本来长度为2,扩容为4
    		假设原本存在key==3与key==7，则都在数组[1]的链表中存放，且3.next=7
    		若此时thread-1已经读到了3.next=7时，thread-2进来完成了整个扩容操作
    		此时新的数组，key==3和key==7都在新数组[3]的链表中，
    		由于扩容使用的是头插法，此时7.next=3，
    		而此时若thread-1再进入，就会出现3.next=7,7.next=3的死循环

###   ConcurrentHashMap ###

>   **10、线程安全的HashTable和ConcurrentHashMap**

由于HashTable比较低效，因为它的实现是将大多数方法都设置为synchronized同步方法，这就导致所有并发操作都要竞争同一把锁，当一个线程在进行同步操作时，其他线程只能等待，大大降低了并发操作的效率。

ConcurrentHashMap采用分段锁的思想，将数据分成一段一段存储，给每一段数据配上一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问。有些需要跨段的操作，必须按顺序锁定所有段并按顺序释放所有段，否则会出现死锁。

>   **11、Java1.8中ConcurrentHashMap与HashMap，HashTable的对比？**

**HashMap**不是线程安全的，处理并发的时候会出现问题（扩容时）

**HashTable**虽然是线程安全的，但是对整个结构进行加锁，效率太低

**CurrentHashMap**采用分段锁的思想（synchronized与CAS操作实现），支持并发的读写，效率较高。

>   **`12、HashMap，HashTable、ConcurrentHashMap的区别？`**

**HashMap**：key和value都可以为null，线程不安全，size一定为2的n次方(初始size为16)，扩容策略为\*2，继承自AbstractMap类，实现Map接口，每次扩容原来数组中的元素都得重新计算存放位置并重新插入。

**HashTable**：key和value都不能为null，线程安全，初始值size为11，扩容策略为\*2+1，继承自Dictionary类，实现Map接口。

**ConcurrentHashMap**：key和value都不能为null，线程安全，size一定为2的n次方(初始size为16)，扩容策略为\*2，采用synchronized+CAS操作保证线程的安全性。

>   **13、ConcurrentHashMap的底层实现**

ConcurrentHashMap在Java7版本时，采用分段锁Segment机制(默认分为16个锁)，而Java8版本中，ConcurrentHashMap采用与HashMap相似的设计，使用`buckets数组+分离链接法`，将锁的粒度细分到每个数组元素。（主体逻辑与HashMap基本相同，只不过需要采用`synchronized锁+CAS操作`保证线程安全）

**寻址**：与HashMap完全相同。

**get()查找**：主要过程与HashMap相同，此处并没有采取锁机制，而是使用`volatile关键字保证数据的可见性`，将table数组，结点的值等`变量都使用volatile修饰`，保证了多线程环境下变量的可见性和有序性。（基于内存保障）

**`sizeCtl`**：ConcurrentHashMap的一个核心属性，用于控制table数组的初始化与扩容，默认值为0，当sizeCtl<0，代表table正处于初始化或扩容的状态；当`sizeCtl==-1`，代表table正处于`初始化`，当`sizeCtl==-N`，代表当前有`N-1个线程正在进行扩容`。当`sizeCtl>0`，说明该数组已初始化过了，此时的`sizeCtl代表下次触发扩容操作的阈值(n*0.75)`。

**初始化**：同样采用懒加载机制，主要在初始化阶段通过`判断sizeCtl的大小+CAS操作`实现线程安全，若初始化时，sizeCtl<0，说明已经有其他线程正在进行初始化，则当前线程让出CPU时间片(yield()），否则（sizeCtl>=0），通过CAS操作尝试修改sizeCtl完成初始化并先将sizeCtl设置为-1。而sizeCtl是volatile变量，一旦被设置为-1，其他线程立马可见，其他线程就会执行线程让步，而最终当前线程将sizeCtl设置为下次扩容的阈值，用于触发扩容操作。

**transfer()扩容**：与HashMap相似，要么链表->红黑树时数组长度小于阈值(64)，要么添加元素时数组容量大于阈值(sizeCtl)，进行扩容。当前线程使用CAS操作对数组进行扩容，此时若当前线程在执行数组的扩容(sizeCtl被设置为负数)，其他线程看到sizeCtl<0就知道正在有其他线程进行扩容就会进行辅助扩容。扩容的核心是`数据的转移`。

**`数据转移`**：ConcurrentHashMap最为巧妙的方法，这是`基于CAS实现的无锁并发同步策略`。

将table数组当做多个线程之间共享的任务队列，维护一个指针，当有一个线程开始进行数据转移，就会先移动指针（`逆向遍历`），表示指针划过的这部分bucket桶区域由该线程负责。这样，即便出现`后面的线程需要插入操作而遇到前面的线程已经在扩容时`，后面线程非但不会被阻塞，还能共同协作，通过`当前机器的CPU数量`决定每个线程负责的bucket数量（避免因为线程过多反而影响到性能），每个线程负责一小块bucket区域，而一个已经完成迁移的bucket会被替换为ForwardingNode结点，目的就是为了标记此块bucket区域已经被其他线程迁移完毕。

使用CAS操作不断尝试为当前线程分配任务，直到分配完成或任务队列已经被完全分配完毕，若当前线程已经被分配过bucket区域，通过指针指向下一块待处理的bucket区域，当任务队列（table数组）已完全处理完数据转移，设置新的阈值sizeCtl。而具体每个线程的迁移过程就和HashMap相同了，要么在原位置，要么在原位置+oldCapacity上插入即可。  
  **addCount()计数**：Java7ConcurrentHashMap对每个Segment单独计数，想要得到总数就需要获得所有Segment的锁，然后进行汇总统计，这样性能太差，Java8通过声明一个volatile变量baseCount用于记录元素的个数，对这个变量的`修改操作是基于CAS`的，每当插入或删除元素都需要调用addCount()进行计数。  
  通过CAS操作更新一个volatile变量baseCount，完美的利用了volatile变量的可见性(先写后读)，CAS操作的判断，以此来更新baseCount的值以及获取最新的baseCount的值。  
  **put()添加元素**：主要逻辑与HashMap相同，唯一需要注意的就是多线程对节点进行操作时需要通过互斥锁保证线程的安全，互斥锁的粒度就是每个数组下标锁对应的bucket桶（数组中一个下标对应的位置）。无限循环进行CAS操作，直到将该元素成功插入到表中。

>   **14、ConcurrentHashMap在JDK1.7和JDK1.8的区别？**

JDK1.7采用分段锁Segment，比较复杂，JDK1.8采用synchronized+CAS操作，并引入红黑树，结构类似于HashMap，引入红黑树使得查询效率提高。

>   **15、简单说一下[红黑树][Link 1]/为什么要使用红黑树？**

红黑树是弱平衡的二叉树，其保证对任意结点而言，没有一条路径会比其他路径长出两倍。相比于二叉搜索树来讲，红黑树保证了树的平衡性，降低了树的高度，提高了树的查找性能，防止由于插入顺序(升/降序插入)导致二叉搜索树成为一条链表的情况。相比于AVL树来讲，红黑树的旋转操作相对较少，操作相对简单。  
  由于平衡二叉树是二叉排序树的进阶，因此红黑树也保证任意结点大于其左子树中的结点，小于其右子树中的任意结点。这样使得红黑树的查找效率比较高。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA_size_16_color_FFFFFF_t_70]: /images/20230531/1225b2e1d76440c5a0b1ab5aee6dfc62.png
[HashMap]: https://www.cnblogs.com/panbingqi/p/11045283.html
[Link 1]: https://blog.csdn.net/weixin_43490440/article/details/103529497