java基础|关于LinkedHashMap中accessOrder属性的理解 accessOrder|LinkedHashMap

今天学习了使用LinkedHashMap来实现LRU算法，具体的关于LinkedHashMap的深入了解可以查看：Java集合详解5：深入理解LinkedHashMap和LRU缓存这篇文章，在介绍accessOrder属性的时候说accessOrder设置为false时，按照插入顺序，设置为true时，按照访问顺序，不过我在查看JDK1.8的LinkedHashMap的put方法时没有看到关于将节点插入到链表尾部的操作，经过一番查看还是找到了这个操作。
【java基础|关于LinkedHashMap中accessOrder属性的理解】LinkedHashMap没有对put方法进行重写，使用的是HashMap里面的put方法。

public class HashMap extends AbstractMap implements Map, Cloneable, Serializable {/**省略无关紧要的代码*/ public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }/** * Implements Map.put and related methods * * @param hash hash for key * @param key the key * @param value the value to put * @param onlyIfAbsent if true, don't change existing value * @param evict if false, the table is in creation mode. * @return previous value, or null if none */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node[] tab; Node p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // existing mapping for key V oldValue = https://www.it610.com/article/e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); //该方法HashMap并没有具体实现，而是LinkedHashMap实现了该方法 return oldValue; } } ++modCount; if (++size> threshold) resize(); afterNodeInsertion(evict); //该方法HashMap并没有具体实现，而是LinkedHashMap实现了该方法 return null; }// Callbacks to allow LinkedHashMap post-actions void afterNodeAccess(Node p) { }//这三个方法在HashMap均没有具体的实现 void afterNodeInsertion(boolean evict) { } void afterNodeRemoval(Node p) { } }

在afterNodeAccess和afterNodeInsertion方法中没有找到将节点插入到双向链表的操作，而在afterNodeAccess方法中，会判断accessOrder是否为true，然后将该节点放到尾部(JDK1.8中最后插入的元素放在尾部)。所以可以判断在afterNodeAccess方法之前已经将该节点插入到了双向链表。具体的afterNodeAccess如下：

void afterNodeAccess(Node e) { // move node to last LinkedHashMap.Entry last; if (accessOrder && (last = tail) != e) {//是否按顺序访问，而且判断尾节点是否是当前节点 LinkedHashMap.Entry p = (LinkedHashMap.Entry)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; } }

我们可以查看一下LinkedHashMap的newNode方法，该方法重写了HashMap的newNode方法，

Node newNode(int hash, K key, V value, Node e) { LinkedHashMap.Entry p = new LinkedHashMap.Entry(hash, key, value, e); linkNodeLast(p); return p; }// link at the end of list private void linkNodeLast(LinkedHashMap.Entry p) {//该方法会将节点放到双向链表的尾部，也就是最近访问的一个 LinkedHashMap.Entry last = tail; tail = p; if (last == null) head = p; else { p.before = last; last.after = p; } }

这样我们再看一下LinkedHashMap的put方法（也就是HashMap的put方法）

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node[] tab; Node p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); //在此步骤会创建新的节点，因为LinkedHashMap重写了newNode方法，所以会调用LinkedHashMap的newNode方法 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // existing mapping for key V oldValue = https://www.it610.com/article/e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size> threshold) resize(); afterNodeInsertion(evict); return null; }

这样就知道了在创建新节点的时候，把该节点放到了尾部。所以我们就清楚了当accessOrder设置为false时，会按照插入顺序进行排序，当accessOrder为true是，会按照访问顺序（也就是插入和访问都会将当前节点放置到尾部，尾部代表的是最近访问的数据，这和JDK1.6是反过来的，jdk1.6头部是最近访问的）。