深入了解 Java 各种容器(三)
2024-10-28 08:52:07 # Technical # JavaBase

此篇了解 LinkedHashSet 与 LinkedHashMap

继承了 HashMap 的 LinkedHashMap 拥有 HashMap 所有的特点,除此之外,LinkedHashMap 还通过双向链表保证了元素的有序

LinkedHashMap 源码只有 700 来行,主要通过重写 HashMap 的方法来增加功能

LinkedHashMap 结构

基础属性与方法

首先从构造方法开始,LinkedHashMap 对外提供 5 中构造方法

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
// 无参构造
public LinkedHashMap() {
super();
accessOrder = false;
}

// 指定初始容量
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false
}

// 指定初始容量与负载因子boolean accessOrder
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}

// 指定初始容量、负载因子和排序模式
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}

// 先使用无参构造实例化,然后将指定map映射到初始化的实例中
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super();
accessOrder = false;
putMapEntries(m, false);
}

LinkedHashMap 中多了一个属性 accessOrder 排序模式,如果为 true 表示按访问顺序,false 表示按插入顺序

另外还有两个关键的属性

1
2
3
4
5
// 链表头元素
transient LinkedHashMap.Entry<K,V> head;

// 链表尾元素
transient LinkedHashMap.Entry<K,V> tail;

双向链表的静态内部类节点

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

重写方法

LinkedHashMap 对 HashMap 重写的方法是其核心

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
void reinitialize() {
super.reinitialize();
this.head = this.tail = null;
}

HashMap.Node<K, V> newNode(int hash, K key, V value, HashMap.Node<K, V> e) {
Entry<K, V> p = new Entry(hash, key, value, e);
this.linkNodeAtEnd(p);
return p;
}

HashMap.Node<K, V> replacementNode(HashMap.Node<K, V> p, HashMap.Node<K, V> next) {
Entry<K, V> q = (Entry)p;
Entry<K, V> t = new Entry(q.hash, q.key, q.value, next);
this.transferLinks(q, t);
return t;
}

HashMap.TreeNode<K, V> newTreeNode(int hash, K key, V value, HashMap.Node<K, V> next) {
HashMap.TreeNode<K, V> p = new HashMap.TreeNode(hash, key, value, next);
this.linkNodeAtEnd(p);
return p;
}

HashMap.TreeNode<K, V> replacementTreeNode(HashMap.Node<K, V> p, HashMap.Node<K, V> next) {
Entry<K, V> q = (Entry)p;
HashMap.TreeNode<K, V> t = new HashMap.TreeNode(q.hash, q.key, q.value, next);
this.transferLinks(q, t);
return t;
}

// remove 后断开链接
void afterNodeRemoval(HashMap.Node<K, V> e) {
Entry<K, V> p = (Entry)e;
Entry<K, V> b = p.before;
Entry<K, V> a = p.after;
p.before = p.after = null;
if (b == null) {
this.head = a;
} else {
b.after = a;
}

if (a == null) {
this.tail = b;
} else {
a.before = b;
}

}

void afterNodeInsertion(boolean evict) {
Entry first;
// removeEldestEntry 可用于实现 LRU,删除最「老」节点
if (evict && (first = this.head) != null && this.removeEldestEntry(first)) {
K key = first.key;
this.removeNode(hash(key), key, (Object)null, false, true);
}

}

// 将节点移动到最后
void afterNodeAccess(HashMap.Node<K, V> e) {
Entry<K, V> last;
if (accessOrder && (last = tail) != e) {// 按插入排序并且e不是最后一个节点
Entry<K, V> p = (Entry<K, V>) e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;// 如果e是头节点,将头换为e的下节点
else
b.after = a;// 如果e不是头节点,将上个节点连接下个节点
if (a != null)
a.before = b;// 如果存在下个节点,连接下个节点与上个节点
else
last = b;// 如果不存在下个节点,先将上个节点放到最后
if (last == null)
head = p;// 如果最后个节点为空,就直接把p(e)放到最后
else {
// 如果最后个节点不为空,就将p加到最后个节点的后面
p.before = last;
last.before = p;
}
tail = p;
++modCount;
}
}

void internalWriteEntries(ObjectOutputStream s) throws IOException {
for(Entry<K, V> e = this.head; e != null; e = e.after) {
s.writeObject(e.key);
s.writeObject(e.value);
}
}

有序性

可以通过 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
24
25
26
27
28
public class LinkedHashMapExample {
public static void main(String[] args) {
LinkedHashMap<Integer, String> map = new LinkedHashMap<>();

map.put(1, "one");
map.put(2, "two");
map.put(3, "three");

System.out.println("Insertion Order:");
for (Map.Entry<Integer, String> entry : map.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}

// Access order demonstration
map = new LinkedHashMap<>(16, 0.75f, true);
map.put(1, "one");
map.put(2, "two");
map.put(3, "three");

map.get(2);
map.get(1);

System.out.println("Access Order:");
for (Map.Entry<Integer, String> entry : map.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
}
}

LRU 缓存

利用 LinkedHashMap 的访问顺序特性,可以轻松实现一个 LRU(Least Recently Used,最近最少使用)缓存。只需要在构造 LinkedHashMap 时设置 accessOrdertrue,并覆盖 removeEldestEntry 方法,使其在缓存大小超过指定容量时自动删除最久未访问的条目

1
2
3
4
5
6
7
8
9
10
11
12
13
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
private final int capacity;

public LRUCache(int capacity) {
super(capacity, 0.75f, true);
this.capacity = capacity;
}

@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > capacity;
}
}

LinkedHashSet

和 HashSet 一样,LinkedHashSet 也是对 LinkedHashMap 的封装,本质依然是 LinkedHashMap