高级JAVA面试题详解(一)——CurrentHashMap、HashMap、HashTable的区别

川长思鸟来 2023-07-18 09:40 15阅读 0赞

这次疫情让几个关系很好的前同事都跳槽了，基本都面了大厂 阿里系、腾讯系、华为、平安等也都拿到了各自满意的offer，居安思危的我将他们经历的面试题收集整理然后根据自身情况解答复习。每周最少两大题（包含扩展问题）分享出来，大家一起学习。

# CurrentHashMap、HashMap、HashTable的区别 #

大方向区别为：  
HashMap 线程不安全的 ，HashTable 线程安全的任一时间只有一个线程能写Hashtable，CurrentHashMap线程安全的，引入分段锁。

## HashMap 详解 ##

#### HashMap 结构 ####

*  JDK1.8以前 数组+单向链表
 *  JDK1.8以后 数组+单向链表+红黑树

#### 为什么要用红黑树 ####

即使负载因子和Hash算法设计的再合理，也免不了会出现拉链过长的情况，一旦出现拉链过长，则会严重影响HashMap的性能。于是，在JDK1.8版本中，对数据结构做了进一步的优化，引入了红黑树。而当链表长度太长（默认超过8）时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能，长度小于6时红黑树转为链表。

课外习题：红黑树是啥？  
红黑树是一个平衡二叉树  
通过旋转和变色来保持平衡，拥有如下特性

*  每个节点要么是黑色，要么是红色。
 *  根节点是黑色。
 *  每个叶子节点（NIL）是黑色。
 *  每个红色结点的两个子结点一定都是黑色。
 *  任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

#### HashMap put()方法实现流程 ####

![HashMap put方法流程][HashMap put]

#### 哈希值计算方式 ####

hash函数是先拿到通过key 的hashcode，是32位的int值，然后让hashcode的高16位和低16位进行异或操作。这个也叫扰动函数，这么设计有三点原因：

*  一定要尽可能降低hash碰撞，越分散越好；
 *  算法一定要尽可能高效，因为这是高频操作, 因此采用位运算；
 *  混合原始哈希码的高位和低位，以此来加大低位的随机性，减少碰撞

#### 什么样的对象可以成为HashMap 的Key值 ####

重写过hashCode和equals的对象，才能做为key。

#### 如何得到一个线程安全的HashMap？ ####

Collections.synchronizedMap(Map)  
Collections 类提供了一个Map接口的实现的内部类 将所有方法都加了synchronized

## HashTable简介 ##

HashTable是直接在操作方法上加synchronized关键字，锁住整个数组。从而达到线程安全。无论key还是value都不能为null

## ConcurrentHashMap简介 ##

分段的数组+链表实现  
ConcurrentHashMap允许多个修改操作并发进行，其关键在于使用了锁分离技术  
有些方法需要跨段，比如size()和containsValue()，它们可能需要锁定整个表而而不仅仅是某个段，这需要按顺序锁定所有段，操作完毕后，又按顺序释放所有段的锁。

## Map延伸题 ##

#### 有序的map ####

HashMap、HashTable、ConcurrentHashMap都是根据hash值随机插入，是无序的，  
LinkedHashMap 是有序的因为LinkedHashMap内部维护了一个单链表，有头尾节点，可以实现按插入的顺序或访问顺序排序。  
TreeMap是按照Key的自然顺序或者Comprator（实现Comprator接口）的顺序进行排序，内部是通过红黑树来实现。

[HashMap put]: /images/20230528/88e3ba94405241b8ba9eed623f4c73ca.png