薯拾

LinkedHashMap-and-LinkedHashSet

2019-06-23

Introduction

LinkedHashMap 继承了 HashMap 与HashMap不同的是,它维护一个贯穿所有entries的双向链表,这个双向链表定义了迭代顺序(通常是key插入到map的顺序)。
linkedHashMap.png

  • 有序:此实现使客户免于HashMap和Hashtable提供的未指定的,通常混乱的排序,而不会增加与treeMap相关的成本。他可以被用来制造一个map的副本,这个副本和原来的map顺序相同,不管这个map是如何实现的。这种技术在客户端传入map进行处理,并且希望返回结果有同样的顺序的时候非常有用。

    1
    2
    3
    4
    void fool(Map m){
    Map copy = new LinkedHashMap(m);
    ...
    }

    此实现有一个特殊的构造函数LinkedHashMap(int,float,boolean),通过指定accessOrder的值可以获得两种维护链表顺序的方式.

    1. accessOrder=true按照最近访问来维护顺序,非常适合用于构建LRU caches。
    2. accessOrder=false按照最近插入来维护顺序.
  • 性能: 此实现提供map接口的所有功能,不允许null元素。和HashMap一样,它提供O(1)复杂度的基本操作:add(),contains(),remove(),假设hash函数将元素均匀的分布于buckets内。由于维护链表增加了额外的开销,性能轻微比HashMap更差;但是LinkedHashMap的迭代时间只与map的size有关,与capacity无关,相比之下HashMap更加昂贵,它的迭代时间与capacity有关。

  • 参数:初始容量 和负载系数。 它们的定义与 HashMap完全相同。 但是,与HashMap相比,此类为初始容量选择过高的值的惩罚不那么严重,因为此类的迭代时间不受容量的影响。

  • 安全: 此实现非线程安全,需要在外部进行同步。通常通过对封装这个map的对象进行同步来实现,也可以使用Collections.synchronizedMap来包装,使得在创建时就避免的非同步的操作。

    1
    Map m = Collections.synchronizedMap(new LinkedHashMap(...));

    Important Variables

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    // 链表头,更老的元素
    transient LinkedHashMap.Entry<K,V> head;
    // 链表尾,更新的元素
    transient LinkedHashMap.Entry<K,V> tail;
    // true:获取顺序,false:插入顺序
    final boolean accessOrder;
    // 继承,并增加节点的链表特性
    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);
    }
    }

    Main Methods

    由于继承了HashMap,LinkedHashMap并未直接实现put等接口方法,而是通过实现在HashMap里边定义回调(多态)来实现。

  • get()
    get调用在hashMap中实现的getNode实现.

    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;
    }
  • put()
    put时,如果存在entry与put的对象相同,这时在HashMap实现的put中回调afterNodeAccess用来将最近访问的节点移动到链表的最后.

    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
    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向后的链接;
    p.after = null;
    if (b == null)
    head = a; // p是头节点,指定a为头节点
    else
    b.after = a;
    if (a != null)
    a.before = b;
    else
    last = b; // last表示未来的倒数第二个节点,a为null,则指向b;否则用原来的tail
    if (last == null) // 只有一种情况,p既是head又是tail,a和b都为null
    head = p;
    else {
    p.before = last;
    last.after = p;
    }
    // 设置p为尾节点
    tail = p;
    ++modCount;
    }
    }

    需要注意的是,如果一个key被重复插入到map,插入顺序不会受到影响,在这种个情况linkedHashMap利用了afterNodeAccess进行HashMap处理完之后的处理,在这个方法中,并未对插入顺序进行调整。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    // evict=false, table 处于创建模式.
    void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    // removeEldestEntry 提供对外接口
    if (evict && (first = head) != null && removeEldestEntry(first)) {
    K key = first.key;
    // 调用hashMap中实现的方法
    removeNode(hash(key), key, null, false, true);
    }
    }
  • remove()
    remove接口回调了 afterNodeRemoval 实现删除hash表中entry之后链表对应的处理.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    void afterNodeRemoval(Node<K,V> e) { 
    // 获取前后的节点
    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;
    }

    除此之外还有多个方法,主要是通过hashMap中的函数回调,在LinkedHashMap主要对hash表修改之后的链表进行维护.

    Demo

    public static void main(String[] args) {
      // 修改第三个参数,进行试验
      Map<String, String> map = new LinkedHashMap<String, String>(16,0.75f,true);
      map.put("1", "a");
      map.put("2", "b");
      map.put("3", "c");
      map.put("4", "e");
      for (String name : map.values()) {
          System.out.print(name);
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章