LinkedHashMap

LinkedHashMap

要点

  1. 底层是散列表和双向链表
  2. 允许为 null key value
  3. 不同步
  4. 拆入的顺序是有序的
  5. 装载因子和初始化容量对性能会有影响
  6. 初始化容量对遍历的性能无影响
  7. access-ordered和insertion-ordered

LinkedHashMap的域

  1. 实体 Entry

    1. 源码

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

    2. 说明

      1. 继承了HashMap的Node类
      2. 双向链表，Entry<K,V> before, after;
      3. access-ordered和insertion-ordered 得到了解释：访问顺序，插入顺序

LinkedHashMap重写的方法

  1. reinitialize() 初始化散列表和双向链表

    1. 源码

      void reinitialize() {
    super.reinitialize();
    head = tail = null;
}

  2. newNode() 创建一个entry，将entry插入到双向链表的末尾，最后反回entry

    1. 源码

      1. Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    linkNodeLast(p);
    return p;
}

    2. 注意点

      1. 在构造节点时，构造的不是Node了，而是Entry节点

构造方法

  1. 5个构造

  2. 方法解析

    1. LinkedHashMap(int intialCapacity, float loadFactor)

      1. 源码

        public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}

      2. 注意点

        • accessOrder = false; 可以看出，LinkedHashMap是插入顺序的

        • 测试

          // 测试默认插入有序
Map<String, String> test = new LinkedHashMap<>();
for (int i = 0; i < 16; i++) {
    test.put("CT-" + i, "Lee测试-ST" + i);
}
// 遍历
// 1、拿到key结合
Set<String> keys = test.keySet();
for (String key : keys) {
    System.out.println("key:    " + key + " ----------------->  " + test.get(key));
}

          key: CT-0 -----------------> Lee测试-ST0
          key: CT-1 -----------------> Lee测试-ST1
          key: CT-2 -----------------> Lee测试-ST2
          key: CT-3 -----------------> Lee测试-ST3
          key: CT-4 -----------------> Lee测试-ST4
          key: CT-5 -----------------> Lee测试-ST5
          key: CT-6 -----------------> Lee测试-ST6
          key: CT-7 -----------------> Lee测试-ST7
          key: CT-8 -----------------> Lee测试-ST8
          key: CT-9 -----------------> Lee测试-ST9
          key: CT-10 -----------------> Lee测试-ST10
          key: CT-11 -----------------> Lee测试-ST11
          key: CT-12 -----------------> Lee测试-ST12
          key: CT-13 -----------------> Lee测试-ST13
          key: CT-14 -----------------> Lee测试-ST14
          key: CT-15 -----------------> Lee测试-ST15

put方法

  1. 没有重写put
  2. 直接调用的HashMap的put方法
  3. 但是创建节点时，调用的是LinkedHashMap的方法

get方法

  1. 源码

    public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null) // 调用的HashMap的方法
        return null;
    if (accessOrder)
        afterNodeAccess(e); // 把该节点放到链表的最后面
    return e.value;
}

  2. 逻辑

    1. 直接调用的HashMap的get做的处理

    2. 如果 accessOrder 为true(访问顺序)，那就调用afterNodeAccess把节点移动到链表的最后

      1. get方法改变了结构
      2. 常用的元素放在最后
      3. 可能是做扩展来用，因为在类的解释上提到了，最近最久未使用的算法

    3. afterNodeAccess方法

      1. 源码

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

remove方法

  1. remove本身没有重写，直接调用的hashMap的remove

  2. 但是重写了 afterNodeRemoval(Node<K,V> e) 方法

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

遍历

  1. 重写了 EntrySet

    1. 源码

      public Set<Map.Entry<K,V>> entrySet() {
    Set<Map.Entry<K,V>> es;
    return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;
}

  2. 可以看出，LinkedHashMap的遍历是对内部维护的一个双向链表的遍历，从而推断出，初始化容量对遍历不是有影响的，但是双向链表的元素，都来源于散列表中

总结

  1. LinkedHashMap比HashMap多了一个内部维护的双向链表，导致初始化容量的大小对遍历不产生影响
  2. 大多数方法都是使用的HashMap的方法，充分的体现了多态的设计原则
    1. 没有重写put, 但是newNode方法重写了，在以LinkedHashMap的对象调用put方法时，走到newNode函数的时候，会去调用HashMap子类的LinkedHashMap的重写的newNode方法 -> 多态的强大
  3. LinkedHashMap设置了两种遍历顺序
    1. 访问顺序 (access-ordered) 在调用get方法时，会改变链表的结构
    2. 插入顺序 (insertion-ordered)(插入的时候，所有的节点都是有序的)
    3. 默认的是插入顺序
    4. 设置访问顺序用处不大
      1. 访问顺序(access-ordered)为LRU算法实现提供服务的
      2. LRU算法：最近最少未使用的节点的算法，可能会定时清理
      3. 若要实现 LRU算法，需要手动实现removeEldestEntry(Map.Entry<K,V> eldest) afterNodeInsertion(boolean evict)，或者扩展LRUMap来使用
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/JQ04/p/15096327.html