linkedhashmap底层数据结构（linkedhashmap如何实现lru）

## LinkedHashMap底层数据结构

简介

LinkedHashMap是Java集合框架中的一种哈希表和链表的组合实现。它继承自HashMap，并额外维护了一个双向链表来记录元素的插入顺序。这意味着LinkedHashMap不仅可以提供HashMap的高效查找、插入和删除操作，还能保证元素的迭代顺序与插入顺序一致。 这使得LinkedHashMap在需要保持插入顺序的场景下非常有用，例如缓存实现。### 1. 数据结构组成LinkedHashMap的核心数据结构由两部分组成：

哈希表 (HashMap):

与HashMap一样，LinkedHashMap使用哈希表来存储键值对。哈希表使用数组+链表（或红黑树，取决于JDK版本和元素数量）的方式来解决哈希冲突。 这意味着键的查找时间复杂度在平均情况下为O(1)，最坏情况下为O(n)，其中n是桶中的元素数量。

双向链表 (Doubly Linked List):

LinkedHashMap 使用一个双向链表来维护元素的插入顺序。每个Entry（键值对）对象除了存储键值对本身外，还包含指向链表中前一个和后一个Entry的指针。链表的头结点指向最近插入的元素，尾结点指向最早插入的元素。### 2. Entry节点结构LinkedHashMap的内部类`Entry`继承自HashMap的`Node` (JDK 8及以后)，包含以下关键字段：

`key`: 键

`value`: 值

`next`: 指向哈希表中下一个Entry的指针（用于处理哈希冲突）

`before`: 指向双向链表中前一个Entry的指针

`after`: 指向双向链表中后一个Entry的指针

`hash`: 键的哈希值### 3. 哈希冲突处理与HashMap类似，LinkedHashMap也需要处理哈希冲突。当多个键映射到同一个桶时，这些Entry会形成一个链表（或红黑树，在JDK 8及以后，当桶中元素数量超过TREEIFY_THRESHOLD时会转换为红黑树）。 链表的顺序取决于元素的插入顺序。### 4. 操作效率

查找 (get):

O(1) 平均时间复杂度，最坏情况O(n)

插入 (put):

O(1) 平均时间复杂度，最坏情况O(n)

删除 (remove):

O(1) 平均时间复杂度，最坏情况O(n)

迭代:

O(n)，因为需要遍历链表### 5. 与HashMap和TreeMap的比较| 特性 | LinkedHashMap | HashMap | TreeMap | |-----------------|-----------------|---------------|---------------| | 元素顺序 | 保持插入顺序 | 无序 | 按键排序 | | 查找效率 | O(1) 平均 | O(1) 平均 | O(log n) | | 插入效率 | O(1) 平均 | O(1) 平均 | O(log n) | | 删除效率 | O(1) 平均 | O(1) 平均 | O(log n) | | 适用场景 | 需要保持插入顺序的缓存、LRU缓存等 | 需要快速查找的场景 | 需要按键排序的场景 |### 6. 访问顺序控制 (accessOrder)LinkedHashMap 的构造函数允许指定一个布尔参数 `accessOrder`。

`accessOrder = false` (默认值): 迭代顺序保持插入顺序。

`accessOrder = true` : 迭代顺序保持访问顺序 (最近访问的元素排在前面)。 每次访问元素 (get操作)，都会将该元素移动到链表的头部。 这使得LinkedHashMap可以很方便地实现LRU (Least Recently Used)缓存。

总结

LinkedHashMap 通过结合哈希表和双向链表，兼顾了HashMap的高效查找和链表保持元素顺序的能力。 理解其底层数据结构有助于更好地利用其特性，并在需要保持元素插入顺序或访问顺序的场景中做出最佳选择。

LinkedHashMap底层数据结构**简介**LinkedHashMap是Java集合框架中的一种哈希表和链表的组合实现。它继承自HashMap，并额外维护了一个双向链表来记录元素的插入顺序。这意味着LinkedHashMap不仅可以提供HashMap的高效查找、插入和删除操作，还能保证元素的迭代顺序与插入顺序一致。 这使得LinkedHashMap在需要保持插入顺序的场景下非常有用，例如缓存实现。

1. 数据结构组成LinkedHashMap的核心数据结构由两部分组成：* **哈希表 (HashMap):** 与HashMap一样，LinkedHashMap使用哈希表来存储键值对。哈希表使用数组+链表（或红黑树，取决于JDK版本和元素数量）的方式来解决哈希冲突。 这意味着键的查找时间复杂度在平均情况下为O(1)，最坏情况下为O(n)，其中n是桶中的元素数量。* **双向链表 (Doubly Linked List):** LinkedHashMap 使用一个双向链表来维护元素的插入顺序。每个Entry（键值对）对象除了存储键值对本身外，还包含指向链表中前一个和后一个Entry的指针。链表的头结点指向最近插入的元素，尾结点指向最早插入的元素。

2. Entry节点结构LinkedHashMap的内部类`Entry`继承自HashMap的`Node` (JDK 8及以后)，包含以下关键字段：* `key`: 键 * `value`: 值 * `next`: 指向哈希表中下一个Entry的指针（用于处理哈希冲突） * `before`: 指向双向链表中前一个Entry的指针 * `after`: 指向双向链表中后一个Entry的指针 * `hash`: 键的哈希值

3. 哈希冲突处理与HashMap类似，LinkedHashMap也需要处理哈希冲突。当多个键映射到同一个桶时，这些Entry会形成一个链表（或红黑树，在JDK 8及以后，当桶中元素数量超过TREEIFY_THRESHOLD时会转换为红黑树）。 链表的顺序取决于元素的插入顺序。

4. 操作效率* **查找 (get):** O(1) 平均时间复杂度，最坏情况O(n) * **插入 (put):** O(1) 平均时间复杂度，最坏情况O(n) * **删除 (remove):** O(1) 平均时间复杂度，最坏情况O(n) * **迭代:** O(n)，因为需要遍历链表

5. 与HashMap和TreeMap的比较| 特性 | LinkedHashMap | HashMap | TreeMap | |-----------------|-----------------|---------------|---------------| | 元素顺序 | 保持插入顺序 | 无序 | 按键排序 | | 查找效率 | O(1) 平均 | O(1) 平均 | O(log n) | | 插入效率 | O(1) 平均 | O(1) 平均 | O(log n) | | 删除效率 | O(1) 平均 | O(1) 平均 | O(log n) | | 适用场景 | 需要保持插入顺序的缓存、LRU缓存等 | 需要快速查找的场景 | 需要按键排序的场景 |

6. 访问顺序控制 (accessOrder)LinkedHashMap 的构造函数允许指定一个布尔参数 `accessOrder`。* `accessOrder = false` (默认值): 迭代顺序保持插入顺序。 * `accessOrder = true` : 迭代顺序保持访问顺序 (最近访问的元素排在前面)。 每次访问元素 (get操作)，都会将该元素移动到链表的头部。 这使得LinkedHashMap可以很方便地实现LRU (Least Recently Used)缓存。**总结**LinkedHashMap 通过结合哈希表和双向链表，兼顾了HashMap的高效查找和链表保持元素顺序的能力。 理解其底层数据结构有助于更好地利用其特性，并在需要保持元素插入顺序或访问顺序的场景中做出最佳选择。