Java集合-HashMap详解(底层数据结构、实现原理、扩容机制）

 #1024程序员节 | 征文#

一、概述

HashMap是Java中最常用的一种集合类，它实现了Map接口并基于哈希表(hash table)数据结构。HashMap用于存储键值对，能够通过键来访问对应的值。

HashMap是无序的，即不会记录插入的顺序。

HashMap是非线程安全的，如果多个线程同时访问并修改HashMap，可能会导致数据不一致。如果需要线程安全，可以使用 ConcurrentHashMap 或对HashMap进行同步。

HashMap 继承于AbstractMap，实现了 Map、Cloneable、java.io.Serializable 接口。

二、HashMap的底层数据结构是什么？

在JDK1.7中，由“数组+链表”组成，数组时HashMap的主体，链表则时主要为了解决哈希冲突而存在的。

在JDK1.8中，由“数组+链表+红黑树”组成。当链表过长时，则会严重的影响HashMap的性能，又因为红黑树搜索的时间复杂度是O(logn)，而链表是O(n)。因此，JDK1.8对数据结构做了进一步优化，引入了红黑树，链表和红黑树在达到一定条件下会进行转换：

• 当链表超过8且数据总量超过才会转化为红黑树；

• 将链表转换成红黑树之前会进行判断，如果当前数组的长度小于，那么会选择先进行数组扩容，而不是转换为红黑树，以减少搜索时间。

三、HashMap的实现原理是怎么样的？

• 数组：HashMap使用一个数组来存储数据，数组中的每个元素成为“桶”(bucket)，每个桶可以存储一个链表或红黑树；

• 哈希函数：当你向HashMap中插入一个键值对时，HashMap会通过哈希函数计算出键的哈希值，并将其映射到数组中一个索引，这个索引确定了该键值对对应该存储在哪个桶中；

• 链表和红黑树：

  • 链表：在桶中，如果多个键映射到同一个索引(即发生哈希冲突)，HashMap会使用链表来解决这个问题。在这种情况下，所有冲突的键值对会被存储在同一个桶的链表中；

  • 红黑树：当某个桶中的链表长度超过了一定的阈值(默认是8)，HashMap会将链表转换成红黑树，以提高查找效率。红黑树是一种自平衡的二叉搜索树，可以在O(log n)的时间内完成查找、插入和删除操作。

• 动态扩容：当HashMap中的元素超过负载因子(默认是0.75)乘以当前数组长度时，HashMap会自动扩容，通常会将数组的大小扩大为原来的两倍，并重新计算每个元素的哈希值以重新分配到新的桶中。

四、解决哈希冲突的方法有哪些？

• 链表法：使用链表或其他数据结构来存储冲突的键值对，将它们链接在同一个哈希桶中。

• 开放寻址法：在哈希表中找到另一个可用的未知来存储冲突的键值对，而不是存储在链表中。常见的开放寻址方法包括线性探测、二次探测和双重散列。

• 再哈希法：当发生冲突时，使用另一个哈希函数再次计算键的哈希值，直到找到一个空槽来存储键值对。

• 哈希桶扩容：当哈希冲突过多时，可以动态地扩大哈希桶 的数量，重新分配键值对，以减少冲突的概率。

五、HashMap的负载因子

HashMap的负载因子(load factor)是一个衡量哈希表存储密度的指标，通常用于决定何时需要扩展哈希表的大小。具体来说，负载因子定义为当前存储的元素数量与哈希表的总用量(即桶的数量)的比值。

在Java中，HashMap的默认负载因子为0.75，这意味着当哈希表的元素数量达到其容量的75%时，HashMap会触发扩容操作。

扩容机制

• 扩容：当负载因子超过设定值(0.75)时，HashMap会将其容量扩大为原来的两倍，并重新计算每个元素的哈希位置。

• 重新哈希：由于扩容后的数组的大小发生变化，所有现有的键值对都会被重新哈辛并放入新的数组中。

负载因子的选择

默认负载因子为0.75，是因为它提供了空间和时间复杂度之间的良好平衡。

• 高负载因子(即存储的键值对增多了)：提高内存空间的使用率，但会增加哈希冲突的概率，可能导致查找、插入延迟，降低性能；

• 低负载因子：消耗更多的内存空间，但提高了查找、插入性能。

负载因子太低会导致大量的空桶而浪费空间，负载因子太高会导致大量的碰撞，降低性能。