《面试 1v1》HashMap

作者：JavaPub

2023-07-11
北京
本文字数：3985 字
阅读完需：约 13 分钟

没有人比中国人更懂 HashMap

我是 javapub，一名 Markdown 程序员从👨‍💻，八股文种子选手。

面试官：HashMap 是 Java 程序员用得最频繁的集合之一,可以给我简单介绍一下它的内部实现机制吗?

候选人： HashMap 是一个散列映射表,它存储的内容是键值对(key-value)映射。

面试官：那它内部具体是如何实现的呢?

候选人： HashMap 在内部实现上主要包含以下几个结构:

数组:HashMap 的核心数据结构就是一个 Entry[] 数组。
链表:每个数组元素是一个单链表结构的头节点,当冲突产生时,会在链表中追加元素。
节点:每个链表节点包含四个字段,key, value, hash 和 next。其中 key 和 value 是映射中的键值,hash 是 key 的 hashCode,next 是指向下一个节点的指针。

面试官：为什么要选择数组和链表这两种数据结构呢?

候选人： 这是因为 HashMap 要保证高效的增删改查操作,数组和链表各自的优点可以满足这个要求:

数组实现通过散列算法,可以快速定位到相应的位置,保证查询的时间复杂度为 O(1)。
链表在冲突发生时,通过在尾部添加节点,可以高效地进行插入操作。同时也方便进行删除操作。所以,HashMap 通过数组实现快速查找,通过链表解决冲突,既可以保证查询效率,也可以应对散列算法产生碰撞的情况。这是它的核心优雅与高效之处。

面试官：HashMap 是非线程安全的,它有哪些线程安全的替代方案呢?

候选人： 对于线程安全的需求,可以选择以下替代方案:

HashTable:HashMap 的线程安全版,内部的方法基本相同,只是进行了线程安全的同步处理。
ConcurrentHashMap:Java 7 的实现使用分段锁,既保证线程安全,也不会影响性能。Java 8 使用 CAS 操作来保证并发度高的操作。
Hashtable:Java 老版本中提供的 hash 表实现,线程安全,但相比于前两者性能较低。现在不建议使用。所以,如果不需要高并发,HashTable 是一个简单直接的替代方案;如果对性能有较高要求,推荐使用 ConcurrentHashMap。两者相比,ConcurrentHashMap 的并发度更高,性能也更佳,是当前推荐的线程安全 hash 表方案。

面试官：简单说一下 HashMap 的 put 操作过程。

候选人： HashMap 的 put(key, value) 方法大致分为以下几步:

计算 key 的 hash 值,这一步通过 key 的 hashCode()方法计算,然后进一步处理高 16 位和低 16 位产生最终的 hash 值。

// 计算key的hash值 final int hash = hash(key);

复制代码

根据 hash 值定位数组索引,如果没有冲突就直接插入。如果产生冲突,就插入冲突链表中。

int i = indexFor(hash, table.length);// 若i位置为空,直接新建节点添加,size增加    if (table[i] == null) {      table[i] = newNode(hash, key, value, null);} // 若产生冲突,将节点添加到链表尾部  else {      ...}

复制代码

如果链表长度超过 TREEIFY_THRESHOLD(默认 8),就把链表转换为红黑树。这一步可以提高查询效率。

// 若链表长度大于8,链表转换为红黑树    if (binCount > TREEIFY_THRESHOLD)     treeifyBin(tab, hash);

复制代码

如果节点已经存在,就替换 oldValue 为新值。

// 若节点已存在,用新值替换旧值for (Node<K,V> e = p;; e = e.next) {    if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {        e.value = value;        break;    }

复制代码

如果容量达到阈值,就进行 resize 两倍扩容,这一步可以减少 hash 冲突,提高查询性能。

if (++size > threshold)     resize(newCapacity);

复制代码

面试官：说说 HashMap 的扩容机制。

候选人： HashMap 的扩容机制就是在 put 时,如果 size 已经超过阈值 threshold,就会进行扩容 resize 操作。在扩容时,capacity 的容量会扩大两倍,并会重新计算每个节点的 hash 值和索引位置。

面试官：为什么要进行两倍扩容?

候选人： 这是因为 HashMap 采用开放定址法来解决冲突,每次扩容时,原有的 hash 值都需要重新计算,如果扩容过小,重新计算后的索引位置有很大概率仍然会发生冲突,效果不明显。如果采用两倍扩容,然后重新计算 hash 值,那么冲突的概率会大大减少,查询性能就能得到较大提高。

面试官：说说 resize 的实现过程。

候选人： resize 的实现过程主要分为以下几步:

将 oldTable 的值赋给 newTable,newTable 的长度是 oldTable 的两倍。

Node<K,V>[] newTable = (Node<K,V>[])new Node[newCapacity];table = newTable;

复制代码

遍历 oldTable 的每个桶,如果桶位非空,就重新计算每个节点的 hash 值和索引,并放入 newTable 对应的桶中。

for (int j = 0; j < oldCap; ++j) {    Node<K,V> e;    if ((e = oldTab[j]) != null) {        oldTab[j] = null;        if (e.next == null)            newTab[e.hash & (newCap - 1)] = e;        else ...     }}

复制代码

resize 的过程中,如果节点的新的索引位置相同,就会在链表中追加新节点。如果不同,就在新位置形成新的链表。

else if (e instanceof TreeNode)     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else { // 链表情况     Node<K,V> loHead = null, loTail = null;    Node<K,V> hiHead = null, hiTail = null;    Node<K,V> next;    do {        next = e.next;        ...    } while ((e = next) != null);}

复制代码

如果链表长度过长,就会先将链表转成红黑树,再进行 resize。这一步可以有效提高性能。

面试官：最后,总结一下 HashMap 的优势。

候选人： HashMap 的主要优势有:

查询和修改的时间复杂度都是 O(1),这是通过哈希算法实现的。
HashMap 是非线程安全的,可以选择并发版的 ConcurrentHashMap。
HashMap 通过扩容和链表转红黑树,可以动态调整容量和提高查询性能。
HashMap 支持 null 键和 null 值。
HashMap 的实现是非常巧妙的,通过数组和链表组合,既可以支持快速查找,也可以解决冲突。
HashMap 有很高的空间利用率,可以存储大量元素。所以,总之,HashMap 的优势在于:性能高效,支持 null,动态扩容,空间利用率高,这也是它成为 Java 最常用的 Map 实现的原因。

面试官：说说 HashMap 的缺点。

候选人： HashMap 也存在一定的缺点:

HashMap 是非线程安全的。多线程环境下,需要对 HashMap 进行同步处理,可以选择 HashTable 或者 ConcurrentHashMap。
HashMap 的迭代顺序是未定义的。每次迭代的顺序可能不同,如果需要顺序,可以采用 LinkedHashMap。
HashMap 的遍历也是 O(n)的时间复杂度,如果集合很大,遍历会很慢。可以通过提高初始容量和负载因子来减少冲突及拉链长度,提高性能。
如果 Hash 算法设计不当,HashMap 的性能会很差。比如大量 Hash 冲突会导致拉链过长,严重影响查询性能。对于自定义类型作为键,需要重写 hashCode()方法来保证分布均匀。
HashMap 采用拉链法解决冲突,極端情况下(数据全部使用相同 hashCode)会退化为链表,变成 O(n)的时间复杂度,查询性能变差。这种情况可以通过使用 TreeMap 来改进。
HashMap 的初始容量和扩容机制的设计不当,会造成非必要的数学开销,影响性能。
HashMap 不支持排序,如果需要排序可以使用 TreeMap 或者对 HashMap 进行排序。所以,总结来说,HashMap 的主要缺点在于:非线程安全,遍历慢,迭代顺序不定,自定义键的 hashCode()设计不好会导致性能下降,不支持排序等。但这些缺点都可以通过选择其他 Map 实现或辅助结构来补充。如果能清楚 HashMap 的这些缺点,就可以更好地选择和使用它。

面试官：你说的很全面和深入。HashMap 作为一个高频使用的数据结构,你对它的理解已经相当深刻了。

候选人： 谢谢面试官的夸奖!HashMap 确实是我常用的数据结构之一,我通过阅读源码、实践使用与论坛上的讨论,对它的设计和实现有了比较深入的理解。但 HashMap 的内容还是非常之广博,我还需要继续学习和总结,以进一步加深理解,利用好它提供的功能,并在实际工作中发挥其优势。我会持续努力,不断提高自己对这方面的认知。

面试官：很好,你对自己的提高有清醒的认识。最后,我想问你作为 HashMap 的替代,现在有什么其他的 Map 实现可以选择?

候选人： 除了 HashMap,Java 中常用的 Map 还有:

Hashtable:HashMap 的线程安全版本,性能差一些,现在不太建议使用。
ConcurrentHashMap:支持高并发的线程安全 Map,在 Java8 之前使用分段锁,之后使用 CAS 保证并发度高的操作。是 HashMap 的线程安全替代方案。
TreeMap:基于红黑树实现,支持排序,复杂度 O(logN), Keys 自动排序。
LinkedHashMap:内部维护着一个双向链表,结合 HashMap 提供按插入顺序或访问顺序遍历 Map 中的条目。
EnumMap:键是枚举类型,内部实现更加紧凑高效。
WeakHashMap:键是弱引用,容易被垃圾回收,防止内存泄露。所以,根据需要的功能,有多个可替代的 Map 实现供选择。但作为最基本和高效的实现,HashMap 还是最为常用和推荐的。

面试官：很好,你的理解和应用已经相当不错了。熟练运用设计模式,在项目开发中可以 large-scale 重构,提高系统扩展性和复用性。你继续加深对各种设计模式的理解和运用,技术还会更上一层楼。

最后,你有什么问题想要提问吗?今天的面试到此结束。

候选人： 非常感谢面试官今天的时间!通过我们的交流,我对很多技术内容有了进一步的认识和提高,也清楚自己的不足和需要努力的方向。这对我来说很宝贵。我现阶段没有其他问题了。我会继续努力学习,不断总结和实践,特别是对数据结构、算法与设计模式等基础内容的运用,提高自己的工程化水平与解决问题的能力。

再次感谢面试官!这是一次非常有价值的交流,很高兴有机会进行这样的技术探讨。谢谢!

面试官： 你的态度很好,技术也不错,继续努力深造,我相信你一定会越来越精进。这也是我作为面试官最喜欢看到的,不论最终结果如何,重要的是候选人的心态和潜力。你也提出了很好的问题,我们进行了广泛而深入的探讨,这说明你在学习和工作中确实遇到过一定的困惑,而又积极主动寻求解决之道。这种积极主动的学习态度很难得,技术人员走的最远的,永远都是在学习和总结中不断超越自己。

很高兴今天的交流,这也使我有机会重温。