Java 容器源码分析之 LinkedHashMap(4)
 
- UID
- 1066743
|

Java 容器源码分析之 LinkedHashMap(4)
在 afterNodeInsertion 中,如果 removeEldestEntry(first) 节点返回 true,则会将头部节点删除。如果想要实现一个固定容量的 Map,可以在继承 LinkedHashMap 后重写 removeEldestEntry 方法。在 LinkedHashMap 中,该方法始终返回 false。
1
2
3
4
5
| //返回false
//是否移除最老的Entry
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
| 在 HashMap 中,在 putVal 和 removeNode 中都调用了相应的回调函数,而 get 则没有,因而在 LinkedHahsMap 中进行了重写:
1
2
3
4
5
6
7
8
9
10
| 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;
}
| 遍历及迭代器因为 LinkeHashMap 的所有的节点都在一个双向链表中,因而可以通过该双向链表来遍历所有的 Entry。而在 HashMap 中,要遍历所有的 Entry,则要依次遍历所有桶中的单链表。相比较而言,从时间复杂度的角度来看,LinkedHashMap 的复杂度为 O(size()),而 HashMap 则为 O(capacity + size())。
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
| //因为所有的节点都被串联在双向链表中,迭代器在迭代时可以利用双向链表的链接关系进行
//双向链表的顺序是按照插入序或访问序排列的
//相比于HashMap中的迭代,LinkedHashMap更为高效,O(size())
//HashMapde 迭代,O(capacity + size())
abstract class LinkedHashIterator {
LinkedHashMap.Entry<K,V> next;
LinkedHashMap.Entry<K,V> current;
int expectedModCount;
LinkedHashIterator() {
next = head;
expectedModCount = modCount;
current = null;
}
public final boolean hasNext() {
return next != null;
}
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;
return e;
}
public final void remove() {
Node<K,V> p = current;
if (p == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
current = null;
K key = p.key;
removeNode(hash(key), key, null, false, false);
expectedModCount = modCount;
}
}
| 可以看到,在遍历所有节点时是通过节点的 after 引用进行的。这样,可以双链表的头部遍历到到双链表的尾部,就不用像 HahsMap 那样访问空槽了。 |
|
|
|
|
|