LinkedHashMap代码详解(一)

HashMap 在遍历map时，数据是无序的，在某些需要按照put顺序遍历时，就用到了LinkedHashMap，LinkedHashMap是HashMap的子类，并且用一条双向链表来存储数据插入的顺序

transient LinkedHashMap.Entry<K,V> head; //链表的头节点 transient LinkedHashMap.Entry<K,V> tail; //链表的尾节点 final boolean accessOrder; //是否开启lru算法(最活跃的点放在链表头部)

put():
由于LinkedHashMap没有put方法，put操作用的还是HashMap的方法，但是重写了newNode(int hash, K key, V value, Node e) ，afterNodeAccess(Node e),afterNodeInsertion(boolean evict)方法
1 table中不存在相同的key

if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null);

LinkedhashMap重写了newNode方法，将新增的节点加入链表尾部，上代码

 Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) { LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e); linkNodeLast(p); return p; } private void linkNodeLast(LinkedHashMap.Entry<K,V> p) { LinkedHashMap.Entry<K,V> last = tail; tail = p;//尾节点指向新节点 if (last == null)//如果原尾节点为空，证明链表还没有数据，头节点指向新节点p head = p; else { //链表不为空 p.before = last; last.after = p;//原尾节点建立双向链接 } }

2 table数组中存在相同的key

 if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; }

发生了节点数据操作(value替换)，如果开启了LRU(accessOrder=true)，则将修改的节点放入链表尾部，HashMap.afterNodeAccess() 为空函数
LinkedHashMap overwirte了该方法

 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; /**重写上面的赋值操作 LinkedHashMap.Entry<K,V> p =(LinkedHashMap.Entry<K,V>)e； LinkedHashMap.Entry<K,V> b(befor) = p.before； LinkedHashMap.Entry<K,V> a(after) = p.after; **/ p.after = null; //将修改的节点after置为null if (b == null) //如果b==null 证明e是头结点 head = a; //将链表头结点指向 e.next else //e不是头结点 b.after = a; // e.befor.after = e.after // e节点的上一个节点的next指向e的下一个节点,移除e if (a != null) //如果e的下一个节点不为空 a.before = b;//e.after.befor= e.after // e节点的下一个节点的befor指向e的上一个节点，双向链表的反向箭头 else // a == null e是尾部节点 last = b; //last指向e的上一个节点 if (last == null) //如果 last== null 证明 只有一个节点 head = p; //头部尾部都指向该节点 else { // p不是头节点 p.before = last; //将p放在链表尾部 last.after = p; } tail = p; ++modCount; //map操作数+1，(重新赋值且开启LRU，modCount会两次+1) } }

3 在执行完put操作后，调用afterNodeInsertion方法

 void afterNodeInsertion(boolean evict) { // possibly remove eldest LinkedHashMap.Entry<K,V> first; if (evict && (first = head) != null && removeEldestEntry(first)) { K key = first.key; removeNode(hash(key), key, null, false, true); } } protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { return false; }

evict 在hashMap中默认为true，LinkedHashMap.removeEldestEntry ()默认返回false，
该方法的yongfasj用法是 配合LRU算法，自定义Class继承LinkedHashMap方法并重写removeEldestEntry 方法，
在特定条件下返回true，移除链表中最左侧的节点
可以使用该特性进行缓存创建，保留最近活跃的数据，开启LRU需要将开头提到的accessOrder 置为true

该参数只能在LinkedHashMap new时指定，需要同时指定扩展因子loadFactor 默认为0.75f

 public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder; }

get():
LinkedHashMap get方法，可以看到 和hashMap是一致的，只是加了accessOrder 判断，开启LRU后，将获取的数据放在链表的最右侧，提高该节点的活跃程度

 public V get(Object key) { Node<K,V> e; if ((e = getNode(hash(key), key)) == null) return null; if (accessOrder) afterNodeAccess(e); return e.value; }