首页 | 新闻 | 新品 | 文库 | 方案 | 视频 | 下载 | 商城 | 开发板 | 数据中心 | 座谈新版 | 培训 | 工具 | 博客 | 论坛 | 百科 | GEC | 活动 | 主题月 | 电子展
返回列表 回复 发帖

Java 容器源码分析之 LinkedHashMap(4)

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 那样访问空槽了。
返回列表