java基础-LinkedHashMap

在Java中，LinkedHashMap是HashMap的一个子类，它维护了一个双向链表来记录插入顺序或访问顺序。

LinkedHashMap的底层构成

LinkedHashMap是在HashMap的基础上，增加了双向链表来维护顺序。

1.核心数据结构

// LinkedHashMap内部类Entry继承了HashMap.Node 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); } }

2.实际存储结构

HashMap部分: 数组 + 链表/红黑树（解决哈希冲突） LinkedHashMap额外部分: 头节点(head) ↔ 节点1 ↔ 节点2 ↔ ... ↔ 尾节点(tail)（双向链表）

主要特点

1.有序性

• 插入顺序：默认按元素插入的顺序维护

• 访问顺序：可通过构造函数设置为按访问顺序维护

2.继承关系

Object ↳ AbstractMap<K,V> ↳ HashMap<K,V> ↳ LinkedHashMap<K,V>

基本用法

import java.util.LinkedHashMap; import java.util.Map; public class LinkedHashMapExample { public static void main(String[] args) { // 1. 创建LinkedHashMap（默认按插入顺序） LinkedHashMap<String, Integer> linkedMap = new LinkedHashMap<>(); // 添加元素 linkedMap.put("Apple", 100); linkedMap.put("Banana", 50); linkedMap.put("Orange", 80); linkedMap.put("Grape", 120); // 遍历 - 按插入顺序输出 System.out.println("按插入顺序:"); for (Map.Entry<String, Integer> entry : linkedMap.entrySet()) { System.out.println(entry.getKey() + ": " + entry.getValue()); } // 输出: Apple, Banana, Orange, Grape（按插入顺序） // 2. 按访问顺序（LRU顺序） LinkedHashMap<String, Integer> lruMap = new LinkedHashMap<>( 16, // 初始容量 0.75f, // 加载因子 true // accessOrder为true表示按访问顺序 ); lruMap.put("A", 1); lruMap.put("B", 2); lruMap.put("C", 3); System.out.println("\n访问前:"); lruMap.forEach((k, v) -> System.out.print(k + " ")); // A B C // 访问元素B lruMap.get("B"); System.out.println("\n访问B后:"); lruMap.forEach((k, v) -> System.out.print(k + " ")); // A C B } }

构造方法

// 1. 默认构造函数（插入顺序，初始容量16，加载因子0.75） LinkedHashMap<String, Integer> map1 = new LinkedHashMap<>(); // 2. 指定初始容量 LinkedHashMap<String, Integer> map2 = new LinkedHashMap<>(32); // 3. 指定初始容量和加载因子 LinkedHashMap<String, Integer> map3 = new LinkedHashMap<>(32, 0.8f); // 4. 指定初始容量、加载因子和排序模式 // true: 按访问顺序 false: 按插入顺序（默认） LinkedHashMap<String, Integer> map4 = new LinkedHashMap<>(32, 0.75f, true); // 5. 从其他Map复制 LinkedHashMap<String, Integer> map5 = new LinkedHashMap<>(existingMap);

与HashMap比较

哈希存储过程：

1. 计算哈希：通过key.hashCode()计算

2. 定位桶：(n-1) & hash计算数组下标

3. 处理冲突：链表或红黑树

4. 维护顺序：同时添加到双向链表的尾部

详细工作原理图

HashMap结构（快速查找） LinkedHashMap额外结构（维护顺序） ↓ ↓ ┌───────┐ head → tail │ 数组 │ ↑ ↓ │[0] │ ┌─────┐ ┌─────┐ ┌─────┐ 插入"A" → 哈希 → │[1] → A│───────────────→│ A │←→│ │ │ │ │[2] │ └─────┘ └─────┘ └─────┘ │[3] │ └───────┘ ┌───────┐ head → tail │ 数组 │ ↑ ↓ │[0] │ ┌─────┐ ┌─────┐ ┌─────┐ 插入"B" → 哈希 → │[1] → A│───────────────→│ A │←→│ B │ │ │ │[2] → B│───────────────→│ │←→│ │ │ │ │[3] │ └─────┘ └─────┘ └─────┘ └───────┘ ┌───────┐ head → tail │ 数组 │ ↑ ↓ │[0] │ ┌─────┐ ┌─────┐ ┌─────┐ 插入"C" → 哈希 → │[1] → A│───────────────→│ A │←→│ B │←→│ C │ │[2] → B│───────────────→│ │←→│ │←→│ │ │[3] → C│───────────────→│ │←→│ │←→│ │ └───────┘ └─────┘ └─────┘ └─────┘

源码关键方法解析

// 1. 创建节点时，同时链接到链表尾部 Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) { LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<>(hash, key, value, e); linkNodeLast(p); // ← 关键！将新节点链接到链表尾部 return p; } // 2. 链接节点到链表尾部 private void linkNodeLast(LinkedHashMap.Entry<K,V> p) { LinkedHashMap.Entry<K,V> last = tail; tail = p; if (last == null) head = p; else { p.before = last; last.after = p; } } // 3. 访问节点后调整顺序（LRU模式） void afterNodeAccess(Node<K,V> e) { // 移动节点到链表尾部 LinkedHashMap.Entry<K,V> last; if (accessOrder && (last = tail) != e) { LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; p.after = null; if (b == null) head = a; else b.after = a; if (a != null) a.before = b; else last = b; if (last == null) head = p; else { p.before = last; last.after = p; } tail = p; ++modCount; } }

查找过程示例

public class LookupExample { public static void main(String[] args) { LinkedHashMap<String, Integer> map = new LinkedHashMap<>(); map.put("Apple", 100); map.put("Banana", 50); map.put("Orange", 80); // 查找"Banana"的过程： // 1. 计算hash: "Banana".hashCode() // 2. 定位桶: (n-1) & hash → 找到数组下标 // 3. 遍历链表/树: 在对应桶中查找 // 4. 如果accessOrder=true，调用afterNodeAccess()将节点移到链表尾部 Integer value = map.get("Banana"); // 通过哈希快速定位 System.out.println("Found: " + value); } }

性能特点对比

总结

1. 底层构成：HashMap的数组+链表/红黑树 + 额外的双向链表

2. key哈希：完全使用HashMap的哈希机制，确保O(1)查找

3. 顺序维护：通过双向链表维护插入顺序或访问顺序

4. 设计巧妙：结合了HashMap的快速查找和链表的顺序特性

LinkedHashMap通过这种"哈希表+双向链表"的复合结构，既保证了HashMap的快速查找特性，又提供了可预测的迭代顺序，是一个非常精妙的设计！

进阶问题

LinkedHashMap作为一个Map与HashMap基本相同，为什么还需要添加一个排序功能，创造出LinkedHashMap？

确实，作为Map，核心功能是通过key找value。但维护顺序在很多实际场景中非常有用，让我通过具体例子来解释：

1.需要保持插入顺序的场景

示例：配置文件解析

public class ConfigFileParser { public static void main(String[] args) { // 读取配置文件，需要保持原有顺序 LinkedHashMap<String, String> config = new LinkedHashMap<>(); config.put("server.host", "localhost"); config.put("server.port", "8080"); config.put("database.url", "jdbc:mysql://localhost:3306/mydb"); config.put("database.username", "admin"); config.put("database.password", "secret"); // 保存配置时，保持原来的顺序 System.out.println("配置项（保持原顺序）:"); config.forEach((key, value) -> System.out.println(key + " = " + value)); // 输出顺序与插入顺序一致，便于阅读和维护 } }

示例：操作日志记录

public class OperationLogger { public static void main(String[] args) { // 记录用户操作序列 LinkedHashMap<Long, String> operationLog = new LinkedHashMap<>(); operationLog.put(System.currentTimeMillis(), "用户登录"); Thread.sleep(100); operationLog.put(System.currentTimeMillis(), "查询商品"); Thread.sleep(100); operationLog.put(System.currentTimeMillis(), "添加购物车"); Thread.sleep(100); operationLog.put(System.currentTimeMillis(), "提交订单"); // 可以按操作发生的顺序回放 System.out.println("用户操作序列:"); operationLog.forEach((time, op) -> System.out.println(new Date(time) + " - " + op)); } }

2.需要可预测迭代顺序的场景

示例：生成有序的JSON/XML

public class OrderedJSONGenerator { public static void main(String[] args) { // 使用LinkedHashMap保证JSON字段顺序 LinkedHashMap<String, Object> json = new LinkedHashMap<>(); json.put("id", 1001); json.put("name", "张三"); json.put("age", 25); json.put("email", "zhangsan@example.com"); json.put("createdAt", "2024-01-15"); // 转换为JSON时，字段顺序是确定的 String jsonString = convertToJSON(json); System.out.println(jsonString); // 输出：{"id":1001,"name":"张三","age":25,"email":"zhangsan@example.com","createdAt":"2024-01-15"} // 如果不保证顺序，每次输出可能不同，不利于调试和测试 } static String convertToJSON(LinkedHashMap<String, Object> map) { StringBuilder sb = new StringBuilder("{"); for (Map.Entry<String, Object> entry : map.entrySet()) { sb.append("\"").append(entry.getKey()).append("\":"); sb.append("\"").append(entry.getValue()).append("\","); } sb.deleteCharAt(sb.length() - 1); sb.append("}"); return sb.toString(); } }

3.构建有序映射表

示例：字母频率统计（按字母顺序）

public class LetterFrequency { public static void main(String[] args) { String text = "hello world"; // 使用LinkedHashMap按字母顺序统计 LinkedHashMap<Character, Integer> frequency = new LinkedHashMap<>(); // 先初始化所有字母（保证顺序） for (char c = 'a'; c <= 'z'; c++) { frequency.put(c, 0); } // 统计频率 for (char c : text.toLowerCase().toCharArray()) { if (frequency.containsKey(c)) { frequency.put(c, frequency.get(c) + 1); } } // 按字母顺序输出 System.out.println("字母频率统计:"); frequency.forEach((letter, count) -> { if (count > 0) { System.out.println(letter + ": " + count); } }); // 输出：d:1, e:1, h:1, l:3, o:2, r:1, w:1 } }

核心价值：LinkedHashMap在不牺牲查找性能（O(1)）的前提下，提供了可预测的迭代顺序，这在很多业务场景中非常有用。它结合了HashMap的快速查找和List的顺序特性，是一个"两全其美"的数据结构。

所以，虽然Map的核心是通过key找value，但顺序在很多实际应用中提供了额外的价值，而LinkedHashMap正好满足了这个需求！