HashMap

kimmking大约 11 分钟

没有人比中国人更懂 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 重构,提高系统扩展性和复用性。你继续加深对各种设计模式的理解和运用,技术还会更上一层楼。

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

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

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

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

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

最近我在更新《面试1v1》系列文章，主要以场景化的方式，讲解我们在面试中遇到的问题，致力于让每一位工程师拿到自己心仪的offer，感兴趣可以关注公众号JavaPub追更！

🎁目录合集：

Gitee：https://gitee.com/rodert/JavaPub

GitHub：https://github.com/Rodert/JavaPub

http://javapub.net.cn