【Java】Java经典面试题：HashMap和HashTable以及ConcurrentHashMap分析

Z时代
2024-01-10
分类：技术分享

前言：

开场

面试官: 你先自我介绍一下吧！

我: 我是，毕业于**，目前在--公司做--系统开发。开发的项目有--布拉布拉......

面试官: 看你简历上写熟悉 Java 集合，HashMap 用过的吧？

我: 用过的。(还是熟悉的味道)

面试官: 那你跟我讲讲 HashMap 的内部数据结构？

我: 目前我用的是 JDK1.8 版本的，内部使用数组 + 链表红黑树；

我: 方便我给您画个数据结构图吧：

【Java】Java经典面试题：HashMap和HashTable以及ConcurrentHashMap分析

面试官: 那你清楚 HashMap 的数据插入原理吗？

我: 呃......我觉得还是应该画个图比较清楚，如下：

【Java】Java经典面试题：HashMap和HashTable以及ConcurrentHashMap分析

判断数组是否为空，为空进行初始化;

不为空，计算 k 的 hash 值，通过(n - 1) & hash计算应当存放在数组中的下标 index;

查看 table[index] 是否存在数据，没有数据就构造一个 Node 节点存放在 table[index] 中；

存在数据，说明发生了 hash 冲突(存在二个节点 key 的 hash 值一样), 继续判断 key 是否相等，相等，用新的 value 替换原数据(onlyIfAbsent 为 false)；

如果不相等，判断当前节点类型是不是树型节点，如果是树型节点，创造树型节点插入红黑树中；

如果不是树型节点，创建普通 Node 加入链表中；判断链表长度是否大于 8，大于的话链表转换为红黑树；

插入完成之后判断当前节点数是否大于阈值，如果大于开始扩容为原数组的二倍。

面试官: 刚才你提到 HashMap 的初始化，那 HashMap 怎么设定初始容量大小的吗？

我: （就猜你会问这个）一般如果new HashMap() 不传值，默认大小是 16，负载因子是 0.75，如果自己传入初始大小 k，初始化大小为大于 k 的 2 的整数次方，例如如果传 10，大小为 16。（补充说明:实现代码如下）

static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}复制代码

【Java】Java经典面试题：HashMap和HashTable以及ConcurrentHashMap分析

面试官: 你提到 hash 函数，你知道 HashMap 的哈希函数怎么设计的吗？

我: （不是吧，非要问到我不会为止吗） hash 函数是先拿到通过 key 的 hashcode，是 32 位的 int 值，然后让 hashcode 的高 16 位和低 16 位进行异或操作。

【Java】Java经典面试题：HashMap和HashTable以及ConcurrentHashMap分析

重点来了！

面试官：HashMap和HashTable的区别是什么？

我： HashMap不是线程安全的

HashMap是map接口的子类，是将键映射到值的对象，其中键和值都是对象，并且不能包含重复键，但可以包含重复值。HashMap允许null key和null value，而hashtable不允许。

HashTable是线程安全。

HashMap是Hashtable的轻量级实现（非线程安全的实现），他们都完成了Map接口，主要区别在于HashMap允许空（null）键值（key）,由于非线程安全，效率上可能高于Hashtable。

HashMap允许将null作为一个entry的key或者value，而Hashtable不允许。 HashMap把Hashtable的contains方法去掉了，改成containsvalue和containsKey。因为contains方法容易让人引起误解。 Hashtable继承自Dictionary类，而HashMap是Java1.2引进的Map interface的一个实现。最大的不同是，Hashtable的方法是Synchronize的，而HashMap不是，在多个线程访问Hashtable时，不需要自己为它的方法实现同步，而HashMap 就必须为之提供外同步。 Hashtable和HashMap采用的hash/rehash算法都大概一样，所以性能不会有很大的差。