简介

image-20240322103238022

可以看到它继承自HashMap，并实现了Map接口。LinkedHashMap与HashMap的主要区别在于，LinkedHashMap维护了一个运行于所有条目的双向链表。这个链表定义了迭代顺序，通常就是插入顺序，或者是访问顺序。 LinkedHashMap的构造函数接受一个名为accessOrder的布尔值参数，用于指定迭代顺序。如果accessOrder为false，则使用插入顺序；如果为true，则使用访问顺序。在访问顺序模式下，调用get和put方法会将相应的条目移动到双向链表的末尾。这种特性使得LinkedHashMap非常适合用来构建LRU（最近最少使用）缓存。 LinkedHashMap还提供了一个名为removeEldestEntry()的方法，它可以被覆盖以移除最老的条目。这个方法默认返回false，即不移除最老的条目。如果需要根据某种策略移除最老的条目，可以创建LinkedHashMap的子类，并覆盖这个方法。 LinkedHashMap的性能通常略低于HashMap，因为维护链表需要额外的资源。然而，LinkedHashMap的迭代性能更高，因为迭代时间仅与实际条目数有关，而与容量无关。在HashMap中，迭代时间与容量有关。

重点属性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 队列的头部指针
transient LinkedHashMap.Entry<K,V> head;

// 队列的尾部指针
transient LinkedHashMap.Entry<K,V> tail;

// 用于指定迭代顺序。如果accessOrder为false，则使用插入顺序；如果为true，则使用访问顺序。
final boolean accessOrder;

// 默认的设置模式，新的数据会被添加到队列的尾部
static final int PUT_NORM = 0;
// 新的数据会被添加到队列的头部
static final int PUT_FIRST = 1;
// 同默认的插入模式
static final int PUT_LAST = 2;
// 确认新数据插入头部还是尾部，默认放入尾部
transient int putMode = PUT_NORM;

构造器

由于继承自HashMap，LinkedHashMap的构造器都是用父类的构造器去构造对象，只是多了些自己的属性：accessOrder，用来确认插入顺序还是访问顺序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 指定容量与负载因子的构造器
public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}
// 只指定容量的构造器
public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}
// 使用默认容量和默认负载因子的构造器
public LinkedHashMap() {
    super();
    accessOrder = false;
}
// 指定容量与负载因子以及迭代顺序的构造器
public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

关键方法

put方法

LinkedHashMap的put方法和父类HashMap是一致的，只是重写了其中的几个方法。HashMap的基本类型是Node，而LinkedHashMap的基本数据类型是继承自Node的Entry，同时多了before和after指针。

1
2
3
4
5
6
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);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 重写了newNode方法
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            // 虽然有执行这个方法，但是由于不满足这个方法的条件，所以不会执行任何逻辑
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    // 重写了插入后的方法
    afterNodeInsertion(evict);
    return null;
}

我们看下newNode方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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);
    linkNodeAtEnd(p);
    return p;
}
// 将Node插入到队列头部或尾部，同时维护好LinkedHashMap的head和tail指针
private void linkNodeAtEnd(LinkedHashMap.Entry<K,V> p) {
    if (putMode == PUT_FIRST) { // 这里是将Node插入到头部
        LinkedHashMap.Entry<K,V> first = head;
        head = p;
        if (first == null)
            tail = p;
        else {
            p.after = first;
            first.before = p;
        }
    } else { // 这是是将Node插入到尾部
        LinkedHashMap.Entry<K,V> last = tail;
        tail = p;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
    }
}

现在看下插入后的逻辑，这个方法主要是执行是否删除头部Node的逻辑。removeEldestEntry方法默认返回false，默认是不删除的，如果需要这样的动作就需要我们重写removeEldestEntry()方法

1
2
3
4
5
6
7
8
9
void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    // 如果需要删除头部元素，可以重写removeEldestEntry(first)方法
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        // 移除节点，后面会详细阐述删除的逻辑
        removeNode(hash(key), key, null, false, true);
    }
}

get方法

get方法和HashMap的get方法是一样的，只是多了一段是否要访问后排序的逻辑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
public V get(Object key) {
    Node<K,V> e;
    // 根据key获取这个Node
    if ((e = getNode(key)) == null)
        return null;
    // 如果迭代顺序是访问顺序，则要执行排序逻辑
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}
// 将Node移动到头部或尾部，注意这种移动动作也影响了modCount的累计
void afterNodeAccess(Node<K,V> e) {
    LinkedHashMap.Entry<K,V> last;
    LinkedHashMap.Entry<K,V> first;
    if ((putMode == PUT_LAST || (putMode == PUT_NORM && accessOrder)) && (last = tail) != e) {
        // 将Node移动到尾部
        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;
    } else if (putMode == PUT_FIRST && (first = head) != e) {
        // 将Node移动到头部
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.before = null;
        if (a == null)
            tail = b;
        else
            a.before = b;
        if (b != null)
            b.after = a;
        else
            first = a;
        if (first == null)
            tail = p;
        else {
            p.after = first;
            first.before = p;
        }
        head = p;
        ++modCount;
    }
}

remove方法

删除指定key的内容，和HashMap的remove操作是同一个方法，只是重写了afterNodeRemove方法,将删除节点的前后节点关联起来

1
2
3
4
5
6
7
8
9
10
11
12
13
void afterNodeRemoval(Node<K,V> e) { // unlink
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, 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;
}

基于LinkedHashMap实现的简单的LRU算法

这里我们实现一个简答的LRU算法，当LinkedHashMap中元素大于5时旧将头部的元素删除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class LinkedHashMapTest<K, V> extends LinkedHashMap<K, V>{
    private static final int THRESHOLD = 5;
    @Override
    public boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return size() > THRESHOLD;
    }

    public static void main(String[] args) {
        LinkedHashMapTest<String, String> linkedHashMap = new LinkedHashMapTest<>();
        for (int i = 0; i < 10; i++) {
            linkedHashMap.put("key:" + i, "value:" + i);
        }
        System.out.println(linkedHashMap);
    }
}
执行结果：{key:5=value:5, key:6=value:6, key:7=value:7, key:8=value:8, key:9=value:9}