Java还要再学一遍基础（十）LinkedHashMap原理

LinkedHashMap概述

LinkedHashMap继承自HashMap并且实现Map接口，内部哈希散列表的实现沿用HashMap的功能，同时LinkedHashMap单独维护了一个双向链表用于记录插入顺序或者访问顺序，以达到按插入顺序或者访问顺序迭代的目的。

详解

首先看一个LinkedHashMap的简单的例子： public static void main(String[] args) { Map<String, String> map = new LinkedHashMap<>(); for(int i = 0; i < 5; i++) map.put("key" + i, "value" + i); for(Iterator<Map.Entry<String, String>> it = map.entrySet().iterator(); it.hasNext();){ System.out.println(it.next()); } }

上面的代码输出：

key0=value0 key1=value1 key2=value2 key3=value3 key4=value4

可以看出是有序输出的。 再看下面：

public static void main(String[] args) { Map<String, String> map = new LinkedHashMap<>(16, .75F, true); for(int i = 0; i < 5; i++) map.put("key" + i, "value" + i); for(int i = 4; i >= 0 ; i--) map.get("key" + i); for(Iterator<Map.Entry<String, String>> it = map.entrySet().iterator(); it.hasNext();){ System.out.println(it.next()); } }

输出：

key4=value4 key3=value3 key2=value2 key1=value1 key0=value0

这里是按照访问的顺序迭代。

源码解析

Entry。LinkedHashMap的Entry是继承的HashMap.Node但是在这基础之上同时还增加了两个属性before和after。很明显这是为了实现双向链表而增加的两个引用，跟别用于指向上一个节点和下一个节点。 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); } }

与之相对的LinkedHashMap同时也增加了两个属性：head和tail，用于实现双向链表的操作。

transient LinkedHashMap.Entry<K,V> head; transient LinkedHashMap.Entry<K,V> tail;

同时还有一个accessOrder属性，用于判断是否需要进行按照访问顺序的迭代。默认是false（按照插入顺序迭代）

final boolean accessOrder;

---

构造函数。LinkedHashMap的构造函数基本都是依赖于HashMap的构造器。 public LinkedHashMap(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor); accessOrder = false; } public LinkedHashMap(int initialCapacity) { super(initialCapacity); accessOrder = false; } public LinkedHashMap() { super(); accessOrder = false; }

---

put方法。LinkedHashMap并没有去重写put方法而是去重写了HashMap的newNode和newTreeNode方法返回LinkedHashMap中的Entry对象。并且将此借点添加到双向链表之中。 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; }

---

get方法。LinkedHashMap重写了HashMap的get方法，实现按照访问顺序迭代。 public V get(Object key) { Node<K,V> e; //getNode是HashMap的方法。这里没有变化 if ((e = getNode(hash(key), key)) == null) return null; //当需要进行按照访问循序迭代的情况下，调用afterNodeAccess方法 if (accessOrder) afterNodeAccess(e); return e.value; } //将访问的节点移动到双向链表的末尾 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; } }