LinkedHashMap 源码分析

2017-07-16  本文已影响176人  zlb
LinkedHashMap 认识

LinkedHashMap 继承自HashMap,因此继承了所有HashMap 的功能，但是LinkedHashMap通过维护一个运行于所有条目的双向链表，LinkedHashMap保证了元素迭代的顺序，这也是与HashMap的不同之处

关注点 结论
LinkedHashMap 是否允许空 允许
LinkedHashMap 是否允许重复数据 Key重复会覆盖、Value允许重复
LinkedHashMap 是否有序 有序
LinkedHashMap 是否线程安全 非线程安全
LinkedHashMap基本数据结构【这部分内容出自 ostracod】

LinkedHashMap不仅像HashMap那样对其进行基于哈希表和单链表的Entry数组+ next链表的存储方式，而且还结合了LinkedList的优点，为每个Entry节点增加了前驱和后继，并增加了一个为header头结点，构造了一个双向循环链表。也就是说，每次put进来KV，除了将其保存到对哈希表中的对应位置外，还要将其插入到双向循环链表的尾部

结构图

上图是LinkedHashMap的全部数据结构，包含散列表和循环双向链表，由于循环双向链表线条太多了，不好画，简单的画了一个节点(黄色圈出来的)示意一下，注意左边的红色箭头引用为Entry节点对象的next引用(散列表中的单链表)，绿色线条为Entry节点对象的before, after引用(循环双向链表的前后引用)；

结构图

上图专门把循环双向链表抽取出来，直观一点，注意该循环双向链表的头部存放的是最久访问的节点或最先插入的节点，尾部为最近访问的或最近插入的节点，迭代器遍历方向是从链表的头部开始到链表尾部结束，在链表尾部有一个空的header节点，该节点不存放key-value内容，为LinkedHashMap类的成员属性，循环双向链表的入口；

结构图
LinkedHashMap 构造器
//构造一个空的LinkedHashMap实例, 默认初始容量（16）和负载因子（0.75）
//排序方式为 按插入的顺序
public LinkedHashMap() {
        super();
        accessOrder = false;
    }

//构造一个空的LinkedHashMap实例与指定的初始容量和加载因子（0.75）
//排序方式为 按插入的顺序
 public LinkedHashMap(int initialCapacity) {
        super(initialCapacity);
        accessOrder = false;
    }

//构建了一个按插入顺序排序的LinkedHashMap，并将 指定的 Map 映射进去
//排序方式为 按插入的顺序
  public LinkedHashMap(Map<? extends K, ? extends V> m) {
        super(m);
        accessOrder = false;
    }

//构造一个空的LinkedHashMap实例与指定的初始容量和加载因子
//排序方式为 按插入的顺序
public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }

//构造一个空LinkedHashMap实例与指定的初始容量，负载因子和排序方式
 public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }
accessOrder
    public static void main(String[] args) {
        Map<String,String> map = new java.util.LinkedHashMap<String,String>(16,0.75f,true);
        map.put("cc", "dddd");
        map.put("ff", "12");
        map.put("aa", "13");
        map.put("bb", "ccc");
        map.put(null, "ddd");
        
        map.get("aa");
        map.get("bb");
        
        Set<java.util.Map.Entry<String, String>> entrys = map.entrySet();
        for(java.util.Map.Entry<String, String> entry : entrys){
            System.out.println(entry.getKey());;
        }
    }

输出结果

cc  ff  null    aa  bb  

    public static void main(String[] args) {
        Map<String,String> map = new java.util.LinkedHashMap<String,String>(16,0.75f,false);
        map.put("cc", "dddd");
        map.put("ff", "12");
        map.put("aa", "13");
        map.put("bb", "ccc");
        map.put(null, "ddd");
        
        map.get("aa");
        map.get("bb");
        
        Set<java.util.Map.Entry<String, String>> entrys = map.entrySet();
        for(java.util.Map.Entry<String, String> entry : entrys){
            System.out.println(entry.getKey());;
        }
    }

输出结果

cc  ff  aa  bb  null
了解 Entry
private static class Entry<K,V> extends HashMap.Entry<K,V> {
        // These fields comprise the doubly linked list used for iteration.
        Entry<K,V> before, after;

        Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
            super(hash, key, value, next);
        }
  .......
}
Entry
LinkedHashMap 插入元素

LinkedHashMap 添加元素 首先调用的事HashMap 的put 方法

public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;

                //LinkedHashMap  重写了该方法，把当前访问的节点 移动到 尾部
                e.recordAccess(this);

                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

不过LinkedHashMap 重写了 addEntry 方法 和 createEntry 方法


 void addEntry(int hash, K key, V value, int bucketIndex) {
      //调用父类的addEntry 方法
        super.addEntry(hash, key, value, bucketIndex);
      
        //获取头节点 的下一个 节点
        Entry<K,V> eldest = header.after;

        //是否需要移除最不常用的 Entry ,通常用来实现缓存
        if (removeEldestEntry(eldest)) {
            // 移除Entry
            removeEntryForKey(eldest.key);
        }
    }

 void createEntry(int hash, K key, V value, int bucketIndex) {
        //查看该索引位置是否存在 元素
        HashMap.Entry<K,V> old = table[bucketIndex];

        //new 一个 Entry 并将 e 的下一个节点指向 old 节点
        Entry<K,V> e = new Entry<>(hash, key, value, old);

        table[bucketIndex] = e;
        e.addBefore(header);
        size++;
    }

// 维护链表的顺序，结合 结构图看 更容易理解
  private void addBefore(Entry<K,V> existingEntry) {
            after  = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
  }
LinkedHashMap 访问元素
 public V get(Object key) {
        //调用父类的getEntry方法获取 节点
        Entry<K,V> e = (Entry<K,V>)getEntry(key);
        if (e == null)
            return null;
        //如果 accessOrder 为true 则将 该节点移到 链表尾部
        e.recordAccess(this);

        return e.value;
    }
recordAccess 方法

就是说你这次访问了双向链表，我就把你记录下来，怎么记录？把你访问的Entry移到尾部去。这个方法在HashMap中是一个空方法，就是用来给子类记录访问用的，看一下LinkedHashMap中的实现：

  void recordAccess(HashMap<K,V> m) {
            LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
            if (lm.accessOrder) {
                lm.modCount++;
                //移除当前元素
                remove();
                //将当前元素置为 链表尾部
                addBefore(lm.header);
            }
        }

看到每次recordAccess的时候做了两件事情：

1、把待移动的Entry的前后Entry相连

2、把待移动的Entry移动到尾部

看下 结构图就 会明白：

recordAccess 结构图
上一篇下一篇

猜你喜欢

热点阅读