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来使用

LinkedHashMap

上一篇:ABP框架禁用数据过滤


下一篇:6、什么是跨域?跨域解决方案?