HashMap数据结构最全详解(图文全面总结)

如下图所示:

图片

HashMap底层数据结构主要包括三部分：数组、链表，以及红黑树三部分组成实现。

1.数组

HashMap内部维护了一个Entry数组，用于存储键值对，Entry是HashMap内部定义的一个私有类，包含了key和value两个属性。

如下所示：

static class Node implements Map.Entry {
    final int hash;
    final K key;
    V value;
    Node next;


}

数组的每个元素称为“桶”，每个桶可能存储一个或多个Entry对象。

2.链表

如果多个Entry对象的hash值相同，它们会被存储在同一个桶中，形成一个链表。

如下图所示：

图片

HashMap 底层结构 (数组 + 链表)
--------------------------------
Bucket 0    ->   null
Bucket 1    ->   Entry1(key1, value1) -> Entry2(key2, value2) -> null
Bucket 2    ->   null
Bucket 3    ->   Entry3(key3, value3) -> null
Bucket 4    ->   null
...

• 每个 Bucket 代表数组中的一个位置。
• Entry 是链表节点，存储键值对以及下一个节点的引用。
• 当多个键值对的哈希值相同时，它们被链接在同一个链表中。

3.红黑树

当同一个桶中的Entry数量达到一定阈值（默认为8），HashMap会将这个桶中的Entry转化为一棵红黑树。

如下图所示：

图片

JDK 8 及之后，引入了红黑树，链表转化为红黑树，提高了性能。

HashMap 底层结构 (数组 + 链表 + 红黑树)
---------------------------------------
Bucket 0    ->   null
Bucket 1    ->   Entry1(key1, value1) -> Entry2(key2, value2) -> null
Bucket 2    ->   null
Bucket 3    ->   TreeNode(key3, value3)
                 /          \
         TreeNode(key4, value4) TreeNode(key5, value5)
Bucket 4    ->   null
...

TreeNode 表示红黑树的节点，取代了长链表中的 Entry。

当链表长度超过阈值时，链表会转换为红黑树，优化查找性能。

但是，这也会出现另外一种情况，当链表中的Entry数量较少时，HashMap会将红黑树，会重新转换为链表。

这样设计的目的：这是为了提高查找效率，因为在红黑树中查找的时间复杂度为O(log n)，而在链表中查找的时间复杂度为O(n)。

简要总结，如下：

• 数组 ：提供了快速的定位，根据键计算哈希值，并确定将该键值对存储到数组中的哪个桶；
• 链表：如果多个键映射到相同的桶，形成链表，解决了哈希冲突，但在大量冲突情况下，查找性能较低；
• 红黑树： 则在大量冲突时，转换为红黑树，提高了查找性能，时间复杂度降到 O(log n)。