LinkedHashMap继承了HashMap,是Map接口的哈希表和链接列表实现。哈希表的功能通过继承HashMap实现了。LinkedHashMap还维护着一个双重链接链表。此链表定义了迭代顺序,该迭代顺序可以是插入顺序或者是访问顺序。
LinkedHashMap的数据结构是数组+链表+红黑树(since JDK1.8)+ 双重链接列表。
数组+链表+红黑树的部分HashMap和LinkedHashMap在这部分的实现是几乎相同的。LinkedHashMap为每个Entry添加了前驱和后继,构成了一个双向循环链表,每次向linkedHashMap插入键值对,除了将其插入到哈希表的对应位置之外,还要将其插入到双向循环链表的尾部。

定义

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>

LinkedHashMap的特性

  • LinkedHashMap<K,V>:HashMap是以key-value形式存储数据的
  • extends HashMap<K,V>:继承了HashMap,哈希表部分的功能和HashMap相似。
  • implements Map<K,V>:实现了Map。HashMap已经继承了Map接口,为什么LinkedHashMap还要实现Map接口呢?仔细看过Java容器其他源码的朋友会发现,不仅仅LinkedHashMap这样做,其他实现类也经常这样做。网上的一些看法是这样做可以直观地表达出LinkedHashMap实现了Map。

构造方法

LinkedHashMap有五种构造方法:

  • LinkedHashMap( int initialCapacity, float loadFactor)。使用指定的初始化容量initial capacity 和负载因子load factor构造一个空LinkedHashMap。
  • LinkedHashMap( int initialCapacity)。使用指定的初始化容量initial capacity和默认负载因子DEFAULT_LOAD_FACTOR(0.75)构造一个空LinkedHashMap。
  • LinkedHashMap()。使用指定的初始化容量(16)和默认负载因子DEFAULT_LOAD_FACTOR(0.75)构造一个空HashMap。
  • LinkedHashMap(Map<? extends K, ? extends V> m)。使用指定Map m构造新的LinkedHashMap。使用指定的初始化容量(16)和默认负载因子DEFAULT_LOAD_FACTOR(0.75)。
  • LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder)。使用指定的初始化容量initial capacity 和负载因子load factor和迭代顺序accessOrder构造一个空LinkedHashMap。

核心方法

containsValue( Object value)
如果linkedHashMap中的键值对有一对或多对的value为参数value,返回true

get( Object key)
返回指定的key对应的entry的value,如果entry为null或者value为null,则返回null

getOrDefault( Object key, V defaultValue)
通过key映射到对应entry,如果没映射到则返回默认值defaultValue

clear()
清空linkedHashMap。

keySet()
返回linkedHashMap中所有key的视图。

values()
返回linkedHashMap中所有value的collection视图

entrySet()
返回hashMap中所有键值对的set视图

源码分析

存储结构
继承自 HashMap,因此具有和 HashMap 一样的快速查找特性。
内部维护了一个双向链表,用来维护插入顺序或者 LRU 顺序。

/**
 * The head (eldest) of the doubly linked list.
 */
transient LinkedHashMap.Entry<K,V> head;
/**
 * The tail (youngest) of the doubly linked list.
 */
transient LinkedHashMap.Entry<K,V> tail;

accessOrder 决定了顺序,默认为 false,此时维护的是插入顺序。

final boolean accessOrder;

LinkedHashMap 最重要的是以下用于维护顺序的函数,它们会在 put、get 等方法中调用。

void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }

**afterNodeAccess()**
当一个节点被访问时,如果 accessOrder 为 true,则会将该节点移到链表尾部。也就是说指定为 LRU 顺序之后,在每次访问一个节点时,会将这个节点移到链表尾部,保证链表尾部是最近访问的节点,那么链表首部就是最近最久未使用的节点。
```java
void afterNodeAccess(Node<K,V> e) { // move node to last
    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;
    }
}

afterNodeInsertion()
在 put 等操作之后执行,当 removeEldestEntry() 方法返回 true 时会移除最晚的节点,也就是链表首部节点 first。
evict 只有在构建 Map 的时候才为 false,在这里为 true。

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

removeEldestEntry() 默认为 false,如果需要让它为 true,需要继承 LinkedHashMap 并且覆盖这个方法的实现,这在实现 LRU 的缓存中特别有用,通过移除最近最久未使用的节点,从而保证缓存空间足够,并且缓存的数据都是热点数据。

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

LRU缓存
以下是使用 LinkedHashMap 实现的一个 LRU 缓存:

  • 设定最大缓存空间 MAX_ENTRIES 为 3;
  • 使用 LinkedHashMap 的构造函数将 accessOrder 设置为 true,开启 LRU 顺序;
  • 覆盖 removeEldestEntry() 方法实现,在节点多于 MAX_ENTRIES 就会将最近最久未使用的数据移除。
class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private static final int MAX_ENTRIES = 3;
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > MAX_ENTRIES;
    }
    LRUCache() {
        super(MAX_ENTRIES, 0.75f, true);
    }
}
···
public static void main(String[] args) {
    LRUCache<Integer, String> cache = new LRUCache<>();
    cache.put(1, "a");
    cache.put(2, "b");
    cache.put(3, "c");
    cache.get(1);
    cache.put(4, "d");
    System.out.println(cache.keySet());
}

运行结果
[3, 1, 4]

HashMap与LinkedHashMap比较

不同点

不同点 HashMap LinkedHashMap
数据结构 数组+链表+红黑树 数组+链表+红黑树+双向循环链表
是否有序 无序 有序

相同点

  • 都是基于哈希表的实现。
  • 存储的是键值对映射。
  • 都继承了AbstractMap,实现了Map、Cloneable、Serializable。
  • 它们的构造函数都一样。
  • 默认的容量大小是16,默认的加载因子是0.75。
  • 都允许key和value为null。
  • 都是线程不安全的。