java源码解读--linkedhashmap

LinkedHashMap

HashMap存储元素是无序的，而LinkedHashMap在hashmap的基础上，能够保持元素的有序性，并且能够基于LinkedHashMap实现LRU缓存

类定义

继承了HashMap类，实现了Map接口，所以LinkedHashMap大部分功能与HashMap一致，在保持元素顺序上有区别。

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>

类成员变量

//entry头指针
   transient LinkedHashMap.Entry<K,V> head;
//entry尾指针
   transient LinkedHashMap.Entry<K,V> tail;
//是否按照访问顺序排序
   final boolean accessOrder;

构造方法

//初始容量和负载因子，排序标志默认为关闭
  public LinkedHashMap(int initialCapacity, float loadFactor) {
       super(initialCapacity, loadFactor);
       accessOrder = false;
   }
//初始容量，负载因子默认0.75，排序标志默认关闭
  public LinkedHashMap(int initialCapacity) {
       super(initialCapacity);
       accessOrder = false;
   }
//初始容量默认16，负载因子默认为0.75，排序标志默认关闭
   public LinkedHashMap() {
       super();
       accessOrder = false;
   }
//初始化输入map
   public LinkedHashMap(Map<? extends K, ? extends V> m) {
       super();
       accessOrder = false;
       putMapEntries(m, false);
   }
//初始容量、负载因子、是否按照访问顺序排序，基于linkedhashmap的lru实现会调用该构造方法
   public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) {
       super(initialCapacity, ladFactor);
       this.accessOrder = accessOrder;
   }

entry定义

   static class Entry<K,V> extends HashMap.Node<K,V> {
//在hashmap.node的基础上增加了前后指针
       Entry<K,V> before, after;
       Entry(int hash, K key, V value, Node<K,V> next) {
           super(hash, key, value, next);
       }
   }

建立链表

LinkedHashMap添加元素操作复用了HashMap的put()方法，但是重写了以下两个方法

   Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
//新建Entry
       LinkedHashMap.Entry<K,V> p =
           new LinkedHashMap.Entry<K,V>(hash, key, value, e);
//链表操作，新加入的元素放作为tail
       linkNodeLast(p);
       return p;
   }

   private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
       LinkedHashMap.Entry<K,V> last = tail;
//把新节点p作为tail
       tail = p;
//如果原来的tail==null，说明链表中没有元素，将p设置为头节点
       if (last == null)
           head = p;
       else {
//如果链表中有元素，则把原来最后一个元素的后项指针指向p，p的前向指针指向last
           p.before = last;
           last.after = p;
       }
   }

删除链表节点

   void afterNodeRemoval(Node<K,V> e) { 
//待删除节点为p，前驱节点为b，后继节点为a
       LinkedHashMap.Entry<K,V> p =
           (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
//释放p的前后指针
       p.before = p.after = null;
// 如果p的前驱节点为null，
       if (b == null)
           head = a;
       else
//链表中有元素，则直接把p的前驱节点的后继节点设置为p的后继节点
           b.after = a;
       if (a == null)
//如果后继节点为空，则说明b节点为tail
           tail = b;
       else
//后继节点不为空，设置a的前驱节点为b
           a.before = b;
   }

插入节点

此处可能涉及是否移除过期元素的处理

//插入节点后如何维护链表
   void afterNodeInsertion(boolean evict) { 
       LinkedHashMap.Entry<K,V> first;
//removeEldestEntry用来判断是否加入过期策略，移除最老的元素。evict是从hashmap传过来的参数，一般情况下初始化时为false，其他情况为true
       if (evict && (first = head) != null && removeEldestEntry(first)) {
           K key = first.key;
           removeNode(hash(key), key, null, false, true);
       }
   }

访问顺序维护

   void afterNodeAccess(Node<K,V> e) { 
       LinkedHashMap.Entry<K,V> last;
//顺序访问维护标志设置为true，并且e不是最后一个元素
       if (accessOrder && (last = tail) != e) {
           LinkedHashMap.Entry<K,V> p =
               (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
	//p的后继节点设置为null
           p.after = null;
	//p的前驱节点为null，则头节点设置为a
           if (b == null)
               head = a;
           else
	//p的前驱节点的后继节点设置为p的后继节点，即删除p
               b.after = a;
	//p的后继节点存在，设置a的前驱节点为b
           if (a != null)
               a.before = b;
           else
	//否则，尾节点为b
               last = b;
	//如果尾节点为null，则头节点设置为p
           if (last == null)
               head = p;
           else {
	//否则，把p设置为last节点后
               p.before = last;
               last.after = p;
           }
	//设置尾节点为p
           tail = p;
           ++modCount;
       }
   }

是否移除过期元素

//需要覆盖该方法实现是否移除元素的逻辑
   protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
       return false;
   }

基于LinkedHashMap实现LRUMap

public class LRUMap extends LinkedHashMap{
		
	private int capacity;

	public LRUMap(int capacity){
		super(16,0.75f,true);
		this.capacity = capacity;				
	}
	
	@Override
	public boolean removeEldestEntry(Map.Entry<K,V> eldest){
		return size()>capacity;
	}
	
}