LinkedHashMap底层结构

LinkedHashMap 是 Java 集合框架中 Map 接口的一个实现，它基于哈希表和双向链表来实现。LinkedHashMap 的特别之处在于，它不仅像普通的 HashMap 一样使用哈希表存储键值对，还维护了插入顺序或访问顺序的链表。这使得它可以保持元素的有序性，这与无序的 HashMap 形成对比。

1. `LinkedHashMap` 的基本特点

有序性：LinkedHashMap 保持键值对的顺序，这个顺序可以是插入顺序（默认）或访问顺序（可选）。这与 HashMap 不同，HashMap 无法保证任何顺序。
底层实现：LinkedHashMap 的实现基于 HashMap，但增加了双向链表来维护顺序。具体而言，每个节点在哈希表中存储数据时，不仅存储了键值对，还存储了指向前一个节点和后一个节点的引用。
性能：与 HashMap 一样，LinkedHashMap 的基本操作（如插入、删除、查找等）都是 O(1) 的时间复杂度。然而，维护链表意味着在一定程度上增加了内存开销。

2. `LinkedHashMap` 的底层数据结构

LinkedHashMap 的底层结构是基于 HashMap 实现的，但它在 HashMap 的基础上添加了双向链表来维护顺序。这使得每个键值对不仅包含哈希表中的 Entry，还具有链表结构。

具体来说，它使用了 LinkedHashMap.Entry<K, V> 作为存储单元，这个类继承自 HashMap.Node<K, V>，并额外添加了两个指针 before 和 after，分别指向双向链表中的前一个和后一个节点。

static class Entry<K,V> extends HashMap.Node<K,V> {Entry<K,V> before, after;Entry(int hash, K key, V value, Node<K,V> next) {super(hash, key, value, next);}
}

`LinkedHashMap` 的双向链表

每次插入元素时，不仅在哈希表中添加新节点，还要将其添加到链表的末尾。链表通过每个 Entry 的 before 和 after 指针进行链接：

before 指向前一个元素。
after 指向下一个元素。

这使得 LinkedHashMap 能够维护键值对的插入顺序。

3. `LinkedHashMap` 的工作原理

LinkedHashMap 的工作原理可以分为几个核心操作：插入元素、删除元素、访问元素和迭代元素。

插入元素

当向 LinkedHashMap 插入一个新的键值对时，底层的哈希表会先计算键的哈希值，并确定键值对存储在哈希表中的位置。与 HashMap 相同，LinkedHashMap 也会通过哈希冲突解决链（链地址法或红黑树）来管理冲突的键。

不同的是，每当插入新节点时，LinkedHashMap 会将新节点添加到链表的尾部。链表通过每个节点的 before 和 after 指针来维护插入顺序。

具体步骤如下：

计算哈希值，找到在哈希表中的位置。
如果该位置已有元素，采用链地址法解决冲突。
将新节点插入哈希表，同时更新链表，将新节点作为链表的最后一个节点。

删除元素

LinkedHashMap 删除元素的过程与 HashMap 基本相同。当删除一个键值对时，哈希表会通过哈希值定位到对应的桶，找到相应的节点并将其移除。

此外，LinkedHashMap 还需要更新双向链表的结构。具体来说，要将被删除节点的前后节点重新链接在一起，确保链表的完整性。假设要删除的节点是 e，它的前后节点分别是 beforeE 和 afterE，删除后链表需要将 beforeE 的 after 指针指向 afterE，afterE 的 before 指针指向 beforeE。

访问元素

LinkedHashMap 提供了一个可选的模式，即“访问顺序模式”。这种模式下，每当访问一个元素（即调用 get 或 put 时获取已存在的元素），都会将该元素移动到链表的末尾。这意味着最近访问的元素会排在最后，从而形成一个按访问顺序排列的 LinkedHashMap。

要启用访问顺序模式，只需在构造 LinkedHashMap 时将 accessOrder 设置为 true：

LinkedHashMap<K, V> map = new LinkedHashMap<>(16, 0.75f, true);

默认情况下，accessOrder 为 false，表示 LinkedHashMap 按插入顺序排列。

在访问顺序模式下，每次访问元素时，LinkedHashMap 都会将该元素移动到链表的末尾。这是通过重新链接链表实现的，即将访问的节点从链表中移除并重新插入到末尾。

迭代元素

由于 LinkedHashMap 维护了一个双向链表，它的迭代顺序与链表中的顺序一致。如果 LinkedHashMap 按插入顺序排列，那么迭代时将按插入顺序访问键值对。如果使用访问顺序排列，迭代顺序将按最近访问的顺序来访问。

4. `LinkedHashMap` 的其他特性

自定义删除策略

LinkedHashMap 提供了一个钩子方法 removeEldestEntry，允许用户自定义何时自动删除最老的元素。这在实现 LRU（最近最少使用）缓存时非常有用。removeEldestEntry 方法每次插入新元素时都会被调用，如果返回 true，则移除最老的元素。

示例：

LinkedHashMap<Integer, String> lruCache = new LinkedHashMap<Integer, String>(16, 0.75f, true) {@Overrideprotected boolean removeEldestEntry(Map.Entry<Integer, String> eldest) {return size() > 5; // 限制缓存大小为 5}
};

在这个例子中，removeEldestEntry 方法控制了缓存的大小，当缓存超过 5 个元素时，最老的元素将被自动删除。

LRU 缓存实现

通过结合访问顺序和 removeEldestEntry，LinkedHashMap 可以很容易地实现 LRU 缓存。每当访问一个元素时，该元素会被移动到链表的末尾，表示最近访问过的元素。而当元素过多时，通过 removeEldestEntry 来移除最不常使用的元素。

5. `LinkedHashMap` 与 `HashMap` 的比较

顺序性：LinkedHashMap 保持元素的顺序（插入顺序或访问顺序），而 HashMap 不保证任何顺序。
性能：由于 LinkedHashMap 维护了一个额外的双向链表，它的性能稍微比 HashMap 慢，但大多数情况下，其时间复杂度仍为 O(1)。
内存开销：LinkedHashMap 的每个节点不仅存储键值对，还存储两个额外的指针（before 和 after），因此它的内存开销比 HashMap 更大。

6. 适用场景

缓存实现：由于 LinkedHashMap 支持按访问顺序排列，并且可以通过 removeEldestEntry 实现自动删除机制，因此它常用于实现 LRU 缓存。
需要保持元素顺序的场景：在某些情况下，保持插入顺序是必须的，例如按顺序输出键值对、生成有序的报表等，这时 LinkedHashMap 是一个理想的选择。