前言

前几篇我们解释了

原来你是这样的HashMap

可"重复"key的HashMap

原来你是这样的TreeMap之RBTree【remove缺失】

本篇介绍一下LinkedHashMap

背景

开发者需要基于插入顺序的容器（很常见的需求），而hashMap是不支持这种操作的【hashMap的iterator拿出来的顺序其实就是table数组中entry的顺序】

那么现在需要实现基于插入顺序（或者访问顺序）的容器呢？【是不是想到了缓存】基于容量的缓存（将最老的元素移除或者将最久未访问的元素移除）

实现

首先查看LinkedHashMap的类图

LinkedHashMap顾名思义还是HashMap但是Linked也说明了其结构 必然是链表。

看一下构造函数

/**  * The iteration ordering method for this linked hash map: <tt>true</tt>  * for access-order, <tt>false</tt> for insertion-order.  *  * @serial  */ private final boolean accessOrder;  /**  * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance  * with the specified initial capacity and load factor.  *  * @param  initialCapacity the initial capacity  * @param  loadFactor      the load factor  * @throws IllegalArgumentException if the initial capacity is negative  *         or the load factor is nonpositive  */ public LinkedHashMap(int initialCapacity, float loadFactor) {     super(initialCapacity, loadFactor);     accessOrder = false; }  /**  * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance  * with the specified initial capacity and a default load factor (0.75).  *  * @param  initialCapacity the initial capacity  * @throws IllegalArgumentException if the initial capacity is negative  */ public LinkedHashMap(int initialCapacity) {     super(initialCapacity);     accessOrder = false; }  /**  * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance  * with the default initial capacity (16) and load factor (0.75).  */ public LinkedHashMap() {     super();     accessOrder = false; } 

可以发现想必HashMap多了一个属性为accessOrder并且默认均是false。该属性表示Linked的有序是按照何种顺序。

accessOrder为false表示链表顺序是插入顺序【对应时间最久】否则是访问顺序【对应最久未访问】

LinkedHashMap中会在调用超类构造函数同时初始化header

/**  * Called by superclass constructors and pseudoconstructors (clone,  * readObject) before any entries are inserted into the map.  Initializes  * the chain.  */ @Override void init() {     header = new Entry<>(-1, null, null, null);     header.before = header.after = header; }

这个头结点是个特殊节点，其指定为特殊hash为-1 并且并未放入hashmap的table数组中。

那么很明显关键在做遍历的时候其迭代器应该不是和原hashMap一样直接遍历table数组

而是根据链表来进行遍历并且返回相应entry

/**  * LinkedHashMap 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);     }      /**      * Removes this entry from the linked list.      */     private void remove() {         before.after = after;         after.before = before;     }      /**      * Inserts this entry before the specified existing entry in the list.      */     private void addBefore(Entry<K,V> existingEntry) {         after  = existingEntry;         before = existingEntry.before;         before.after = this;         after.before = this;     }      /**      * This method is invoked by the superclass whenever the value      * of a pre-existing entry is read by Map.get or modified by Map.set.      * If the enclosing Map is access-ordered, it moves the entry      * to the end of the list; otherwise, it does nothing.      */     void recordAccess(HashMap<K,V> m) {         LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;         if (lm.accessOrder) {             lm.modCount++;             remove();             addBefore(lm.header);         }     }      void recordRemoval(HashMap<K,V> m) {         remove();     } } 

entry中多了指向before和after两个指针，那么可以再做remove或者put的时候进行指针操作。

而对应迭代器如下

private abstract class LinkedHashIterator<T> implements Iterator<T> {     Entry<K,V> nextEntry    = header.after;     Entry<K,V> lastReturned = null;      /**      * The modCount value that the iterator believes that the backing      * List should have.  If this expectation is violated, the iterator      * has detected concurrent modification.      */     int expectedModCount = modCount;      public boolean hasNext() {         return nextEntry != header;     }      public void remove() {         if (lastReturned == null)             throw new IllegalStateException();         if (modCount != expectedModCount)             throw new ConcurrentModificationException();          LinkedHashMap.this.remove(lastReturned.key);         lastReturned = null;         expectedModCount = modCount;     }      Entry<K,V> nextEntry() {         if (modCount != expectedModCount)             throw new ConcurrentModificationException();         if (nextEntry == header)             throw new NoSuchElementException();          Entry<K,V> e = lastReturned = nextEntry;         nextEntry = e.after;         return e;     } }

默认情况下jcf迭代器都是FailFast机制，即当有任意线程更改了相关数据modCount和expectModCount不一致直接抛出ConcurrentModificationException

因此做遍历的时候直接按照链表读下去直到下一个数据为head即可这样就完成了有序。

那么如果需要做对于访问顺序的有序呢？

在HashMap中有方法如下

/**  * This method is invoked whenever the value in an entry is  * overwritten by an invocation of put(k,v) for a key k that's already  * in the HashMap.  */ void recordAccess(HashMap<K,V> m) { }

在LinkedhashMap中做了如下处理

/**  * This method is invoked by the superclass whenever the value  * of a pre-existing entry is read by Map.get or modified by Map.set.  * If the enclosing Map is access-ordered, it moves the entry  * to the end of the list; otherwise, it does nothing.  */ void recordAccess(HashMap<K,V> m) {     LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;     if (lm.accessOrder) {         lm.modCount++;         remove();         addBefore(lm.header);     } } /**  * Removes this entry from the linked list.  */ private void remove() {     before.after = after;     after.before = before; } /**  * Inserts this entry before the specified existing entry in the list.  */ private void addBefore(Entry<K,V> existingEntry) {     after  = existingEntry;     before = existingEntry.before;     before.after = this;     after.before = this; } 

可以看到如果是会将该节点直接放入到header节点的前面。但是header的before在初始化时也是header 那么此时节点就会出现在header节点的after【这是一个环形链表】

这边存在一个性能点，如果调用recordAccess时会将自身节点删除并且重新插入链表最后

因此在hashMap在调用put时

/**  * Associates the specified value with the specified key in this map.  * If the map previously contained a mapping for the key, the old  * value is replaced.  *  * @param key key with which the specified value is to be associated  * @param value value to be associated with the specified key  * @return the previous value associated with <tt>key</tt>, or  *         <tt>null</tt> if there was no mapping for <tt>key</tt>.  *         (A <tt>null</tt> return can also indicate that the map  *         previously associated <tt>null</tt> with <tt>key</tt>.)  */ public V put(K key, V value) {     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;             e.recordAccess(this);             return oldValue;         }     }      modCount++;     addEntry(hash, key, value, i);     return null; } 

那么这边的操作可能对于系统来说就是一个重复的操作。

那么可以优化的点在于只有当put时发生替换的时候才会做recordAccess操作即可。

因此只需要在查找到旧的key存在并且替换的时候才执行。

那么正常的put（addEntry）是不会二次触发recordAccess的。

 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {             V oldValue = e.value;             e.value = value;             e.recordAccess(this);             return oldValue;         }

缓存

HashMap在提供了一系列的基于插入顺序或者访问顺序的特性之后那么和cache唯一的差别在于其提供了无穷大的size，

那么我们是否只需要扩展到当达到指定size之后直接remove某一个最差的节点呢（基于插入顺序或者访问顺序）

LinkedHashMap提供如下方法

/**  * Returns <tt>true</tt> if this map should remove its eldest entry.  * This method is invoked by <tt>put</tt> and <tt>putAll</tt> after  * inserting a new entry into the map.  It provides the implementor  * with the opportunity to remove the eldest entry each time a new one  * is added.  This is useful if the map represents a cache: it allows  * the map to reduce memory consumption by deleting stale entries.  *  * <p>Sample use: this override will allow the map to grow up to 100  * entries and then delete the eldest entry each time a new entry is  * added, maintaining a steady state of 100 entries.  * <pre>  *     private static final int MAX_ENTRIES = 100;  *  *     protected boolean removeEldestEntry(Map.Entry eldest) {  *        return size() > MAX_ENTRIES;  *     }  * </pre>  *  * <p>This method typically does not modify the map in any way,  * instead allowing the map to modify itself as directed by its  * return value.  It <i>is</i> permitted for this method to modify  * the map directly, but if it does so, it <i>must</i> return  * <tt>false</tt> (indicating that the map should not attempt any  * further modification).  The effects of returning <tt>true</tt>  * after modifying the map from within this method are unspecified.  *  * <p>This implementation merely returns <tt>false</tt> (so that this  * map acts like a normal map - the eldest element is never removed).  *  * @param    eldest The least recently inserted entry in the map, or if  *           this is an access-ordered map, the least recently accessed  *           entry.  This is the entry that will be removed it this  *           method returns <tt>true</tt>.  If the map was empty prior  *           to the <tt>put</tt> or <tt>putAll</tt> invocation resulting  *           in this invocation, this will be the entry that was just  *           inserted; in other words, if the map contains a single  *           entry, the eldest entry is also the newest.  * @return   <tt>true</tt> if the eldest entry should be removed  *           from the map; <tt>false</tt> if it should be retained.  */ protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {     return false; }

我天，注释里面详细描写了设置一个最大size即可！一个简易版本的LocalCache就这么出现了！

只要继承LinkedHashMap并重写removeEldestEntry

 private static final int MAX_ENTRIES = 100;       protected boolean removeEldestEntry(Map.Entry eldest) {         return size() > MAX_ENTRIES;      }

而访问顺序或者插入顺序只需要在初始化是传入accessOrder即可！