LinkedHashMap小抄

public class LinkedHashMap {
   
   static class Entry<K,V> extends HashMap.Node<K,V> {
       // 每个Node的基础上增加了before和after这两个节点
       // 实现了双向链表
       // 最占内存的数据结构
       Entry<K,V> before, after;
       // Node本身的next只是桶里的顺序，after指的是整个链表的顺序
       Entry(int hash, K key, V value, Node<K,V> next) {
           super(hash, key, value, next);
       }
   }
   
   // false 基于插入顺序  
   // true  基于访问顺序（get一个元素后，这个元素被加到最后，使用了LRU  最近最少被使用的调度算法）
   final boolean accessOrder;
   
   public V get(Object key) {
       Node<K,V> e;
       if ((e = getNode(hash(key), key)) == null)
           return null;
       if (accessOrder) // 访问到元素后，根据accessOrder是否要改变链表顺序
           afterNodeAccess(e);
       return e.value;
   }
   
   // 移动元素e到链表最后
   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;
       }
   }
   
   // 这个方法重载了父类HashMap（HashMap.afterNodeInsertion 没有逻辑）
   void afterNodeInsertion(boolean evict) { // possibly remove eldest
       LinkedHashMap.Entry<K,V> first;
       // removeEldestEntry(Map.Entry eldest)方法，默认返回false
       // 通过覆盖这个方法，加入一定的条件，满足条件返回true。
       // 当put进新的值方法返回true时，便移除该map中最老的键和值。
       if (evict && (first = head) != null && removeEldestEntry(first)) {
           K key = first.key; // 最老的键值对就是first
           removeNode(hash(key), key, null, false, true);
       }
   }
}