1、概述
LinkedHashMap继承自HashMap;在HashMap基础上,通过维护一条双向链表,解决了HashMap键值对遍历顺序和插入顺序一致的问题。
想了解LinkedHashMap源码,首先需要了解HashMap源码。
2、原理
3、源码分析
结合我的《源码分析(1)-HashMap(JDK1.8)》文章 https://www.cnblogs.com/wangymd/p/11750194.html。
3.1、成员属性
//双向联调头 transient LinkedHashMap.Entry<K,V> head; //双向联调尾 transient LinkedHashMap.Entry<K,V> tail; // final boolean accessOrder;
//数据结构 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); } }
3.2、插入操作
插入操作复用父类方法putVal方法,重写创建节点方法、增加维护双向联调的方法。
//重写父类HashMap的newNode方法,创建hash桶节点 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; } //重写父类HashMap的newTreeNode方法,创建红黑树节点 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; } //新增加点添加到双向联调尾部 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; } }
//重写父类HashMap的replacementNode方法,红黑树节点转换为链表节点 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; } //重写父类HashMap的replacementTreeNode方法,链表节点转换为红黑树节点 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; }
3.3、删除操作
删除操作复用父类方法removeNode方法,重写afterNodeRemoval维护双向链表数据结构。
//重写父类HashMap的afterNodeRemoval方法,维护双向链表数据结构 void afterNodeRemoval(Node<K,V> e) { // unlink 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; }
3.4、查询操作
查询操作重写父类方法get方法。
// 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; } // final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {//定位hash桶位置 if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k))))//查询结果头结点 return first; if ((e = first.next) != null) {//查询结果不是头结点 if (first instanceof TreeNode)//节点类型红黑树 return ((TreeNode<K,V>)first).getTreeNode(hash, key); do {//节点类型链表 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }
参考文章: