如何深入解读LinkedHashMap原理和源码

发布时间：2021-12-03 18:37:57 作者：柒染
来源：亿速云阅读：180

# 如何深入解读LinkedHashMap原理和源码

## 一、LinkedHashMap概述

LinkedHashMap是Java集合框架中一个重要的实现类，它继承自HashMap，在HashMap的基础上通过维护一个双向链表来保证元素的插入顺序或访问顺序。与HashMap的纯哈希表结构不同，LinkedHashMap通过结合哈希表和链表的优势，提供了可预测的迭代顺序。

### 1.1 核心特性
- **有序性**：默认保持插入顺序（accessOrder=false），可配置为访问顺序（LRU模式）
- **性能平衡**：查找效率O(1)，略低于HashMap但远优于TreeMap
- **继承关系**：`java.util.LinkedHashMap` → `java.util.HashMap` → `java.util.AbstractMap`

### 1.2 典型应用场景
- 需要保持插入顺序的缓存系统
- 实现LRU（最近最少使用）缓存策略
- 需要有序键值对且不频繁修改的场景

## 二、数据结构解析

### 2.1 底层存储结构
```java
// 继承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);
    }
}

LinkedHashMap在HashMap的数组+链表/红黑树结构基础上，额外维护了一个双向链表： - 头节点：transient LinkedHashMap.Entry<K,V> head - 尾节点：transient LinkedHashMap.Entry<K,V> tail

2.2 两种排序模式

插入顺序（默认）：

public LinkedHashMap(int initialCapacity, float loadFactor) {
   super(initialCapacity, loadFactor);
   accessOrder = false; // 关键参数
}

访问顺序（LRU）：

public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
   super(initialCapacity, loadFactor);
   this.accessOrder = accessOrder; // 设置为true
}

三、核心源码解析

3.1 节点访问逻辑

访问节点时的顺序维护（get()方法）：

public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder) // 如果为访问顺序模式
        afterNodeAccess(e); // 将被访问节点移到链表尾部
    return e.value;
}

afterNodeAccess()方法实现：

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;
        // 从链表中移除节点p
        LinkedHashMap.Entry<K,V> 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;
        
        // 将p插入到链表尾部
        if (last == null) head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

3.2 插入操作处理

插入节点时的钩子方法（覆盖HashMap的newNode()）：

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;
}

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.3 删除操作处理

删除节点后的处理（afterNodeRemoval()）：

void afterNodeRemoval(Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e;
    LinkedHashMap.Entry<K,V> b = p.before, a = p.after;
    p.before = p.after = null; // 清理指针
    
    if (b == null) head = a;
    else b.after = a;
    
    if (a == null) tail = b;
    else a.before = b;
}

四、LRU缓存实现原理

4.1 移除最老元素机制

通过覆盖removeEldestEntry()方法实现：

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false; // 默认不删除
}

// 典型LRU缓存实现示例
final int MAX_ENTRIES = 100;
LinkedHashMap<Integer, String> cache = new LinkedHashMap<>(16, 0.75f, true) {
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > MAX_ENTRIES;
    }
};

4.2 完整LRU工作流程

新元素插入时自动追加到链表尾部
元素被访问时移动到尾部（当accessOrder=true）
当容量超过阈值时，自动移除链表头部元素

五、迭代器实现

5.1 关键迭代器类

abstract class LinkedHashIterator {
    LinkedHashMap.Entry<K,V> next;
    LinkedHashMap.Entry<K,V> current;
    
    LinkedHashIterator() {
        next = head; // 从头节点开始
        expectedModCount = modCount;
    }
    
    final LinkedHashMap.Entry<K,V> nextNode() {
        LinkedHashMap.Entry<K,V> e = next;
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        if (e == null)
            throw new NoSuchElementException();
        current = e;
        next = e.after; // 通过after指针遍历
        return e;
    }
    // ... 其他方法省略
}

5.2 三种视图迭代器

KeyIterator：继承LinkedHashIterator实现Iterator<K>
ValueIterator：继承LinkedHashIterator实现Iterator<V>
EntryIterator：继承LinkedHashIterator实现Iterator<Map.Entry<K,V>>

六、性能分析与对比

6.1 时间复杂度对比

操作	HashMap	LinkedHashMap	TreeMap
get()	O(1)	O(1)	O(log n)
put()	O(1)	O(1)	O(log n)
remove()	O(1)	O(1)	O(log n)
迭代	无序	O(n)有序	O(n)有序

6.2 内存占用比较

LinkedHashMap比HashMap多维护一个双向链表，每个Entry多存储两个指针
典型内存消耗（64位JVM）：
- HashMap.Entry：24字节
- LinkedHashMap.Entry：40字节（增加16字节）

七、实战注意事项

7.1 线程安全问题

与HashMap相同，LinkedHashMap非线程安全，多线程环境下应该：

Map<String, Object> safeMap = Collections.synchronizedMap(
    new LinkedHashMap<>(16, 0.75f, true));

7.2 初始化参数建议

预估容量避免频繁扩容：

// 预期存储100元素，0.75负载因子
new LinkedHashMap<>( (int)(100/0.75)+1, 0.75f )

访问顺序模式下的并发修改异常：

// 迭代过程中访问元素会触发modCount变化
for(Key key : map.keySet()) {
   map.get(key); // 抛出ConcurrentModificationException
}

八、总结与进阶思考

LinkedHashMap通过精巧的双向链表设计，在几乎不损失HashMap性能优势的前提下实现了有序性。理解其实现原理有助于：

更合理地选择Map实现类
实现高效的LRU缓存策略
深入理解Java集合框架的设计思想

扩展思考：如何基于LinkedHashMap实现一个支持过期时间的缓存系统？（提示：结合定时任务清理机制） “`