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方法
网友评论