数据结构和算法六（LinkedHashMap实现原理解析）

2017-11-19 本文已影响0人小窦子

LinkedHashMap简介

首先LinkedHashMap是HashMap的子类，和HashMap有着同样的存储结构，但是它加入了一个双向链表的头结点，将所有put的元素全部串成了一个双向循环链表，因此保留了插入的顺序，所以它是有序的。
而且它也可以用来实现LRU算法，我们可以看LruCache源码知道，内部维护了一个LinkedHahMap，同样它是非线程安全的

源码解析（基于25的）

变量

private transient LinkedHashMapEntry<K,V> header;
双向循环链表的头结点，整个LinkedHashMap都只有一个header，它是将哈希表中所有的实体连接起来的，header中不保存key-value，只保存前后结点的引用
private final boolean accessOrder; 双向链表中元素排序规则的标志，为false的时候按照插入顺序，为true按照访问顺序
构造函数

public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
这是构造函数，调用父类的构造函数构造数组，然后这个是按照插入顺序来访问的。
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
这个是支持自定义访问顺序的

方法

@Override
  void init() {
  header = new LinkedHashMapEntry<>(-1, null, null, null);
  header.before = header.after = header;
}
这是init方法 是父类的也就是hashmap的 但是父类是空实现，子类实现并且创建一个header结点

  复写HashMap中的transfer方法，它在父类的resize方法中调用，扩容后 将key和value对重新映射到新table中，复写该方法的目的是为了提高复制的效率，这里迭代是利用了循环链表进行迭代，并不对底层的数组的进行for循环
@Override
  void transfer(HashMapEntry[] newTable) {
  int newCapacity = newTable.length;
  for (LinkedHashMapEntry<K,V> e = header.after; e != header; e = e.after) {
      int index = indexFor(e.hash, newCapacity);
      e.next = newTable[index];
      newTable[index] = e;
  }
}

内部类

  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  注意这里得到的当前的对象  
  private void remove() {  
      before.after = after;  //  this.before.after=this.after;
      after.before = before;  //this.after.brfore=this.before; 这么写肯定看懂 也就是说将当前节点删除
  }  

  //双向循环立链表中，将当前的Entry插入到existingEntry的前面  
  private void addBefore(Entry<K,V> existingEntry) {  
      after  = existingEntry;  
      before = existingEntry.before;  
      before.after = this;  
      after.before = this;  
  }  


  //覆写HashMap中的recordAccess方法（HashMap中该方法为空），  
  //当调用父类的put方法，在发现插入的key已经存在时，会调用该方法，  
  //调用LinkedHashmap覆写的get方法时，也会调用到该方法，  
  //该方法提供了LRU算法的实现，它将最近使用的Entry放到双向循环链表的尾部，  
  //accessOrder为true时，get方法会调用recordAccess方法  
  //put方法在覆盖key-value对时也会调用recordAccess方法  
  //它们导致Entry最近使用，因此将其移到双向链表的末尾  
  void recordAccess(HashMap<K,V> m) {  
      LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;  
      //如果链表中元素按照访问顺序排序，则将当前访问的Entry移到双向循环链表的尾部，  
      //如果是按照插入的先后顺序排序，则不做任何事情。  
      if (lm.accessOrder) {  
          lm.modCount++;  
          //移除当前访问的Entry  
          remove();  
          //将当前访问的Entry插入到链表的尾部  
          addBefore(lm.header);  
      }  
  }  

  void recordRemoval(HashMap<K,V> m) {  
      remove();  
  }  
}

这里在贴一下get方法的源码

  public V get(Object key) {  
  Entry<K,V> e = (Entry<K,V>)getEntry(key);  
  if (e == null)  
      return null;  
  e.recordAccess(this);  
  return e.value;

}
//以上就是linkedmap源码解析大多数都是调用父类的方法，

总结

image.png

从源码中可以看出LinkedHashmap就是加入了一个head节点，将所有插入到该map中的entry按照插入的先后顺序依次插入到以head为头结点的双向循环链表的尾部
LinkedHashMap由于继承自HashMap，因此它具有HashMap的所有特性，同样允许key和value为null。
注意源码中的accessOrder标志，当它false时，表示双向链表中的元素按照Entry插入LinkedHashMap到中的先后顺序排序，即每次put到LinkedHashMap中的Entry都放在双向链表的尾部，这样遍历双向链表时，Entry的输出顺序便和插入的顺序一致，这也是默认的双向链表的存储顺序；当它为true时，表示双向链表中的元素按照访问的先后顺序排列，可以看到，虽然Entry插入链表的顺序依然是按照其put到LinkedHashMap中的顺序，但put和get方法均有调用recordAccess方法（put方法在key相同，覆盖原有的Entry的情况下调用recordAccess方法），该方法判断accessOrder是否为true，如果是，则将当前访问的Entry（put进来的Entry或get出来的Entry）移到双向链表的尾部（key不相同时，put新Entry时，会调用addEntry，它会调用creatEntry，该方法同样将新插入的元素放入到双向链表的尾部，既符合插入的先后顺序，又符合访问的先后顺序，因为这时该Entry也被访问了），否则，什么也不做。
注意构造方法，第一个构造方法是按照插入顺序来访问的，第二个构造方法是你可以自定义的，因此可以指定双向循环链表中元素的排序规则，一般要用LinkedHashMap实现LRU算法，就要用该构造方法，将accessOrder置为true。
5、LinkedHashMap并没有覆写HashMap中的put方法，而是覆写了put方法中调用的addEntry方法和recordAccess方法

数据结构和算法六（LinkedHashMap实现原理解析）

LinkedHashMap简介

源码解析（基于25的）

总结

猜你喜欢

热点阅读