Java基础之LinkedHashMap源码解析

Java集合源码解析系列

• Java基础之HashMap源码解析
• Java基础之ArrayList源码解析

LinkedHashMap

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> { /** * HashMap.Node的子类 * 增加了前后节点的引用，因此不再是单链表而是双向链表 */ static class Entry<K,V> extends HashMap.Node<K,V> { Entry<K,V> before, after; Entry(int hash, K key, V value, Node<K,V> next) { super(hash, key, value, next); } } /** * 双向链表的头节点和尾节点 * */ transient LinkedHashMap.Entry<K,V> head; transient LinkedHashMap.Entry<K,V> tail; /** * 排序规则的标志 * false表示按节点插入顺序排序 * true表示按节点访问顺序排序 * 默认是false */ final boolean accessOrder; /** *将节点插入链表尾部 */ private void linkNodeLast(LinkedHashMap.Entry<K,V> p) { LinkedHashMap.Entry<K,V> last = tail; tail = p; //如果是插入第一个节点，则头节点和尾节点都指向这个节点 if (last == null) head = p; //已经插入过节点了，就直接插入链表尾部 else { p.before = last; last.after = p; } } /** *将dst节点替换src节点 */ private void transferLinks(LinkedHashMap.Entry<K,V> src, LinkedHashMap.Entry<K,V> dst) { LinkedHashMap.Entry<K,V> b = dst.before = src.before; LinkedHashMap.Entry<K,V> a = dst.after = src.after; //src是第一个节点 if (b == null) head = dst; else b.after = dst; //src是最后一个节点 if (a == null) tail = dst; else a.before = dst; } /** *初始化LinkedHashMap，这里在调用HashMap的初始化方法之外，还需要将头节点和尾节点初始化 */ void reinitialize() { super.reinitialize(); head = tail = null; } /** * 这里覆写了HashMap的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; } /** * 用next节点替换p节点 */ Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) { LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p; LinkedHashMap.Entry<K,V> t = new LinkedHashMap.Entry<K,V>(q.hash, q.key, q.value, next); transferLinks(q, t); return t; } /** * 红黑树节点的相关方法 */ TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) { TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next); linkNodeLast(p); return p; } TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) { LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p; TreeNode<K,V> t = new TreeNode<K,V>(q.hash, q.key, q.value, next); transferLinks(q, t); return t; } /** * 覆写HashMap中的afterNodeRemoval方法 * 将节点从链表中删除 */ void afterNodeRemoval(Node<K,V> e) { LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; p.before = p.after = null; //删除的是第一个节点 if (b == null) head = a; else b.after = a; //删除的是最后一个节点 if (a == null) tail = b; else a.before = b; } /** * 覆写HashMap中的afterNodeInsertion方法 * evict为true并且removeEldestEntry方法也为true的话就会删除近期最少使用的节点 * 所以这里可以看出LinkedHashMap能实现LRU算法 * 由HashMap的源码可知evict默认是true */ void afterNodeInsertion(boolean evict) { LinkedHashMap.Entry<K,V> first; if (evict && (first = head) != null && removeEldestEntry(first)) { K key = first.key; //满足条件则删除近期使用最少的节点 removeNode(hash(key), key, null, false, true); } } /** * 覆写HashMap中的afterNodeAccess方法，每当节点被访问时被调用 * 如果accessOrder为true，也就是LinkedHashMap的节点是按照访问顺序排序的，则需要将节点移到链表的末尾 * 这也是LinkedHashMap实现LRU算法的条件之一，即accessOrder要为true */ 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; } } /** * 可以看到默认accessOrder为false，也就是按节点插入顺序排序 */ public LinkedHashMap(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor); accessOrder = false; } public LinkedHashMap(int initialCapacity) { super(initialCapacity); accessOrder = false; } public LinkedHashMap() { super(); accessOrder = false; } /** * 这个构造函数可以设置排序规则 * 所以如果要实现LRU算法，也就是要设置accessOrder为true，就要用这个构造函数 */ public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder; } /** * 判断值是否存在，只需要循环双向链表 * 这里相比HashMap需要2层循环，提升了效率 */ public boolean containsValue(Object value) { for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) { V v = e.value; if (v == value || (value != null && value.equals(v))) return true; } return false; } /** * LinkedHashMap的get方法调用的是HashMap的getNode方法 * 注意这里会调用recordAccess方法 */ public V get(Object key) { Node<K,V> e; //如果没找到返回null if ((e = getNode(hash(key), key)) == null) return null; //如果节点是按照访问顺序排序的，那就得去更新下顺序，把刚刚获取的节点放到链表末尾去 if (accessOrder) afterNodeAccess(e); return e.value; } /** * 跟上面的方法一样，只是如果对应的key的节点不存在，会返回一个默认的数据 */ public V getOrDefault(Object key, V defaultValue) { Node<K,V> e; if ((e = getNode(hash(key), key)) == null) return defaultValue; if (accessOrder) afterNodeAccess(e); return e.value; } /** * 这个好理解，清空数据 */ public void clear() { super.clear(); head = tail = null; } /** * 这个方法用于控制是否要删除近期使用最少的节点 * 默认返回是false，所以如果要实现LRU算法，需要覆写该方法，比如节点满了返回true以便删掉使用较少的节点 */ protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { return false; } <!--省略其他方法--> }

LinkedHashMap没有put方法，是怎么插入数据的呢

• 答案就在newNode方法

/** * 这里覆写了HashMap的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; } /** * 红黑树节点的相关方法 */ TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) { TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next); linkNodeLast(p); return p; }

• LinkedHashMap实际只是在HashMap的基础上加上了一个双向链表来保存节点插入的顺序，因此很多的逻辑都和HashMap是一样的。比如插入节点时，LinkedHashMap相比HashMap只需要在HashMap的基础上将节点插入双向链表，以及根据排序要求更新节点的顺序就行了
• 对于插入双向链表的功能，LinkedHashMap覆写了HashMap的newNode方法；而对于更新节点的顺序问题，LinkedHashMap覆写了afterNodeAccess方法和afterNodeInsertion方法

总结

• LinkedHashMap继承自HashMap，是HashMap的子类，因此也不是线程安全的
• LinkedHashMap底层存储结构与HashMap一样，不同的是LinkedHashMap增加了一个双向链表的头节点，插入的数据除了插入HashMap，还会插入链表中，因而可以保存插入节点的顺序
• LinkedHashMap的节点在HashMap节点的基础上增加了前后节点的引用
• LinkedHashMap可以插入null
• LinkedHashMap相比HashMap在查找值和删除值时效率要高
• LinkedHashMap还可以设置按插入顺序排序或是按访问顺序排序，默认是按插入顺序排序
• LinkedHashMap没有put方法，而是覆写了afterNodeAccess方法和afterNodeInsertion方法。当插入的数据已经存在时，会调用afterNodeAccess方法看是否需要将数据插入到链表末尾；当插入的数据是新数据时，会通过afterNodeInsertion方法来根据设置删除近期使用最少的节点
• LinkedHashMap可以用来实现LRU算法。首先需要用可以设置accessOrder的构造函数设置accessOrder为true，也就是按照节点访问顺序排序；然后removeEldestEntry方法设置当超过节点数时返回true，也就是删除近期最少使用的数据

以上是基于Java1.8并且只介绍了常用的一些方法的原理，详细的LinkedHashMap源码请查看：LinkedHashMap源码

---

欢迎关注我的微信公众号，和我一起学习一起成长！