JAVA ｜数据结构 HashMap、LinkedHashMap

一 HashMap HashMap 的基本原理哈希表基础 HashMap 的内部结构哈希冲突的解决策略动态扩容 HashMap 的关键参数二 LinkedHashMap LinkedHashMap 的特点主要特性实现细节 HashMap 与 LinkedHashMap 的对比

一 HashMap

HashMap 的基本原理

HashMap 是基于哈希表（Hash Table）实现的，它通过 键的哈希值 快速定位到存储位置，从而实现高效的插入、删除和查找操作。HashMap 不保证映射的顺序，尤其是它的顺序可能会随着键的插入顺序或键的哈希值的变化而变化。

哈希表基础

哈希表通过一个数组（称为桶数组）来存储数据。每个键通过哈希函数被转换为一个哈希码，然后根据这个哈希码确定在数组中的位置。当多个键的哈希码映射到同一个数组位置时，称为哈希冲突，需要采取一定的策略来处理冲突。

HashMap 的内部结构

在 Java 8 及之后的版本中，HashMap 的内部结构主要包括以下几个关键部分：

数组（table）：底层存储结构，是一个数组，每个元素称为一个桶。

链表/红黑树：每个桶中存储的是一个链表或红黑树，用于处理哈希冲突。

节点（Node）：每个链表或树中的元素包含键值对、哈希值以及指向下一个节点的引用（对于链表）。

其中代码如下：


transient Node<K,V>[] table;
transient int size;
final float loadFactor;
transient int threshold;

// 其中 Node 结构
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        ...
    }

table：存储键值对的数组。

size：当前存储的键值对数量。

loadFactor：负载因子，决定何时扩容。

threshold：扩容的阈值，当 size 超过 threshold 时，进行扩容。

哈希冲突的解决策略

在 HashMap 中，采用 链表法 解决哈希冲突。当多个键映射到同一个桶时，它们以链表的形式存储在该桶中。自 Java 8 起，当某个桶中的元素数量超过一定阈值（默认为 8）时，链表将被转换为 红黑树，以提高查找效率。

动态扩容

HashMap 具有动态扩容的能力，当元素数量超过当前数组容量与负载因子的乘积时，HashMap 会进行扩容操作，通常是将数组容量扩大为原来的两倍，并重新计算所有键的哈希值，以重新分配它们的位置。

HashMap 的关键参数

HashMap 的性能和行为受以下几个关键参数影响：

初始容量（initial capacity）：哈希表初始化时的桶数量。默认值为 16。

负载因子（load factor）：衡量哈希表填满程度的指标，默认为 0.75。当实际负载超过这个值时，哈希表会进行扩容。

容量阈值（threshold）：触发扩容的具体元素数量，计算公式为 capacity * load factor。

合理设置这些参数可以有效地减少哈希冲突和扩容次数，从而提升 HashMap 的性能。

二 LinkedHashMap

LinkedHashMap 的特点

LinkedHashMap 是 HashMap 的子类，它在 HashMap 的基础上维护了一个 双向链表，以记录键值对的插入顺序或访问顺序。这使得 LinkedHashMap 在迭代时能够按照特定顺序返回元素。

主要特性

有序性：LinkedHashMap 保持了元素的插入顺序或按访问顺序排序。

轻微的性能开销：由于维护了额外的双向链表，LinkedHashMap 比 HashMap 稍微耗费更多的内存和时间。

应用场景：适用于需要有序迭代的场景，如实现 LRU 缓存等。

实现细节

LinkedHashMap 通过在每个节点中增加 before 和 after 指针，实现了链表的双向链接。这样不仅能保持迭代顺序，还能在插入和访问时高效地调整顺序。

HashMap 与 LinkedHashMap 的对比

特性	HashMap	LinkedHashMap
顺序性	无序	保持插入顺序或访问顺序
性能	通常略快于 LinkedHashMap	由于维护链表，稍微慢一些
内存消耗	较低	由于额外的链表指针，内存消耗更高
迭代顺序控制	无法控制	可按照插入顺序或访问顺序进行迭代
应用场景	通用的键值对存储	需要有序迭代或实现特定缓存策略（如 LRU 缓存）

JAVA ｜ 数据结构 HashMap、LinkedHashMap