Java 集合框架之 LinkedHashMap 工作原理

发表于 | 分类于 | 阅读次数
字数统计 1,771 | 阅读时长 7

一、不同类型 Map 的适用场景

  • 如果不关心 Map 中的 key 顺序，只是希望能够以 O(1) 的时间复杂度执行插入和查找操作。那么可以选择HashMap；

  • 如果要求 key 有序，则选择TreeMap。

    • 但是选择 TreeMap 就会有性能问题，因为 TreeMap 的 get 操作的时间复杂度是O(log(n))的，相比于 HashMap 的O(1)还是差不少的，
  • LinkedHashMap的出现就是为了平衡这些因素，使得 能够以O(1)时间复杂度增加查找元素，又能够保证 key 的有序性 此外，LinkedHashMap 提供了两种 key 的顺序：
    1. 按照访问顺序排序（access order）。可以使用这种顺序实现LRU（Least Recently Used）缓存
    • 因为每次访问后的元素会被移到链表尾部，实现 LRU 只需要移除 链首元素 即可
      • 「一次访问」的定义是什么？
        • put，putIfAbsent，get，getOrDefault，compute，computeIfAbsent，computeIfPresent 或 merge 方法会导致访问相应的条目（假设它在调用完成后存在）。如果值被替换，替换方法只会导致条目的访问
    1. 按照插入顺序排序（insertion orde）。注：同一 key 的多次插入，并不会影响其顺序。
      注：WeakHashMap 也可以用于实现缓存，二者的使用场景不同。WeakHashMap 无法像 LinkedHashMap 那样自定义淘汰规则，它的元素会在 gc 的发生的时候被清除。

特别地，对 collection-view 的操作不会影响后台映射的迭代顺序。

  • collection-view 是否类似于数据库的视图？

二、性能

LinkedHashMap 提供了所有可选的 Map 操作，并允许使用 null 元素。与 HashMap 一样，假设散列函数能够正确地在桶之间分散元素，它为基本操作（添加，包含和删除）提供了恒定的性能。性能可能略低于 HashMap 的性能，这是因为维护链接列表的成本增加了，但有一个例外：对 LinkedHashMap 的 collection-view 的迭代需要时间与 map 的 size 成比，而不关其 capacity。迭代 HashMap 可能会更加昂贵，需要的时间与其 capacity 成正比。

LinkedHashMap 有两个影响其性能的参数：初始容量和负载因子。它们的定义与 HashMap 完全相同。但请注意，对于此类，初始容量选择过高值对性能的影响不会像 HashMap 那么严重，因为此类的迭代时间不受容量影响，迭代只受到 size 的影响。

三、并发问题（fail-fast）

并发方式：推荐使用 Map m = Collections.synchronizedMap(new LinkedHashMap(...));进行包装。内部是使用一个内置锁，各个方法的实现只是加锁然后 调用原来的类。这最好在创建时就完成「包装操作」，以防止意外的不同步访问 Map。

结构性修改（A structural modification ） 是指

  • 添加或删除一个或多个映射的操作，
  • 在访问有序的 LinkedHashMap 的情况下会影响迭代顺序。
  • 在插入有序的 LinkedHashMap 中，仅更改与已包含在映射中的键相关的值不是结构修改。
  • 在 access-ordered 模式下的 LinkedHashMap 中，仅通过 get 查询 map 就是一种结构修改。

迭代遍历过程中如果发现结构性修改问题（使用 iterater#remove 方法产生的结构性修改问题除外 ），马上抛出 ConcurrentModificationException，以免造成更大的损失。

「快速失败」具体实现是怎么样的呢？每趟遍历完成之后都会调用 checkForComodification 方法进行检查

java.util.ArrayList.Itr#checkForComodification

1
2
3
4
final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

四、实现

节点数据结构

主要基于 HashMap 的节点数据结构实现。

1
2
3
4
5
6
7
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);
    }
}

双向链表实现的 LinkedHshMap，所以每个节点须在 HashMap 的基础上添加指向前继节点与后继节点指针：before，after。

核心方法

HashMap 中定义了三个回调方法供 LinkedHashMap 重写。

1
2
3
4
// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }

LinkedHashMap 继承于 HashMap，重新实现了这 3 个函数，顾名思义这三个函数的作用分别是：节点访问后、节点插入后、节点移除后做一些事情。

1.afterNodeRemoval

双向链表删除节点可以参考这样思路。

假设 before —> p —> after

要删除 p

1.先处理 after 方向

if p 为第一个节点 before == null head = after

else before.after = after

2.再处理 before 方向

if p 为最后一个节点 after == null tail = before
else after.before = before;

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

2.afterNodeInsertion

evict 参数有什么用？

  • if false, the table is in creation mode.
    • Creation mode 是什么？刚刚创建时的模式？

HashMap#的 put 方法，调用 putVal 方法时，传入的 evit 为 true。 

1
2
3
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

调用处传递 evict 全部为 true。

1
2
3
4
5
6
7
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);
    }
}

3.afterNodeAccess

与模式相关 final boolean accessOrder

只能在构造函数中指定，默认为 false，

  • true 表示按访问顺序排序
  • false 表示按插入顺序排序

把节点移到链表末尾。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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;
    }
}

4.put

put put函数在LinkedHashMap中未重新实现，只是实现了afterNodeAccess和afterNodeInsertion两个回调函数。

5.get

1
2
3
4
5
6
7
8
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;
}

get函数重新实现并加入了afterNodeAccess来保证访问顺序

五、小结

  1. 怎样保证插入顺序？ 使用前驱和后继指针，使得原来的 HashMap 有序，在LinkedHashMap中覆盖HashMap中newNode 方法，使得每次 put 数据时，新建的节点都是LinkedHashMap.Entry<K,v> 类型的，比普通的HsahMap.Entry 多一个前驱结点和一个后继节点，使用前驱和后继保证插入有序。
  2. 怎么样保证访问顺序？ 覆盖父类HashMap的afterNodeAccess 方法，使得每次访问后，都改变链表顺序。使得原链表按访问排序。将最新一次访问的节点放到链表的最后。

六、参考资料与学习资源推荐

由于本人水平有限，可能出于误解或者笔误难免出错，如果发现有问题或者对文中内容存在疑问请在下面评论区告诉我，谢谢！

Show Comments
0%