## 2. 代码分析

### 2.1 节点类 Entry

LinkedHashMap 内部有一个嵌套类 Entry，它继承自 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);}``}``

``static class Node<K,V> implements Map.Entry<K,V> {final int hash;final K key;V value;Node<K,V> next;Node(int hash, K key, V value, Node<K,V> next) {this.hash = hash;this.key = key;this.value = value;this.next = next;}// ...``}``

### 2.2 成员变量

``/*** The head (eldest) of the doubly linked list.*/transient LinkedHashMap.Entry<K,V> head;/*** The tail (youngest) of the doubly linked list.*/transient LinkedHashMap.Entry<K,V> tail;/*** The iteration ordering method for this linked hash map: true* for access-order, false for insertion-order.* LinkedHashMap 的迭代顺序：true 为访问顺序；false 为插入顺序。*/``final boolean accessOrder;``

### 2.3 构造器

• 构造器1

``/*** Constructs an empty insertion-ordered LinkedHashMap instance* with the default initial capacity (16) and load factor (0.75).*/public LinkedHashMap() {super();accessOrder = false;``}``

• 构造器 2、3、4、5

``public LinkedHashMap(int initialCapacity) {super(initialCapacity);accessOrder = false;}public LinkedHashMap(int initialCapacity, float loadFactor) {super(initialCapacity, loadFactor);accessOrder = false;}public LinkedHashMap(Map<? extends K, ? extends V> m) {super();accessOrder = false;putMapEntries(m, false);}public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) {super(initialCapacity, loadFactor);this.accessOrder = accessOrder;``}``

### 2.4 put 方法

LinkedHashMap 本身没有实现 put 方法，它通过调用父类（HashMap）的方法来进行读写操作。这里再贴下 HashMap 的 put 方法：

``public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;if ((p = tab[i = (n - 1) & hash]) == null)// 新的 bin 节点tab[i] = newNode(hash, key, value, null);else {Node<K,V> e; K k;// key 已存在if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;// 散列冲突else if (p instanceof TreeNode)e = ((TreeNode<K,V>)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 1sttreeifyBin(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 keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;if (++size > threshold)resize();afterNodeInsertion(evict);return null;``}``

``Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {return new Node<>(hash, key, value, next);``}``

``// 新建一个 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;``}``

``// link at the end of listprivate void linkNodeLast(LinkedHashMap.Entry<K,V> p) {LinkedHashMap.Entry<K,V> last = tail;tail = p;// list 为空if (last == null)head = p;else {// 将新节点插入到 list 末尾p.before = last;last.after = p;}``}``

``// Callbacks to allow LinkedHashMap post-actionsvoid afterNodeAccess(Node<K,V> p) { }``void afterNodeInsertion(boolean evict) { }``

``void afterNodeAccess(Node<K,V> e) { // move node to lastLinkedHashMap.Entry<K,V> last;// accessOrder 为 true 表示访问顺序if (accessOrder && (last = tail) != e) {// p 为访问的节点，b 为其前驱，a 为其后继LinkedHashMap.Entry<K,V> p =(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;p.after = null;// p 是头节点if (b == null)head = a;elseb.after = a;if (a != null)a.before = b;elselast = b;if (last == null)head = p;else {p.before = last;last.after = p;}tail = p;++modCount;}``}``

### 2.5 get 方法

LinkedHashMap 重写了 HashMap 的 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;``}``

``void afterNodeInsertion(boolean evict) { // possibly remove eldestLinkedHashMap.Entry<K,V> first;if (evict && (first = head) != null && removeEldestEntry(first)) {K key = first.key;removeNode(hash(key), key, null, false, true);}}// LinkedHashMap 中默认的返回值为 false，即这里的 removeNode 方法不执行protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {return false;``}``

removeNode 方法是父类 HashMap 中的：

``final Node<K,V> removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable) {Node<K,V>[] tab; Node<K,V> p; int n, index;// table 不为空，且给的的 hash 值所在位置不为空if ((tab = table) != null && (n = tab.length) > 0 &&(p = tab[index = (n - 1) & hash]) != null) {Node<K,V> node = null, e; K k; V v;// 给定 key 对应的节点，在数组中第一个位置if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))node = p;// 给定的 key 所在位置为红黑树或链表else if ((e = p.next) != null) {if (p instanceof TreeNode)node = ((TreeNode<K,V>)p).getTreeNode(hash, key);else {do {if (e.hash == hash &&((k = e.key) == key ||(key != null && key.equals(k)))) {node = e;break;}p = e;} while ((e = e.next) != null);}}// 删除节点if (node != null && (!matchValue || (v = node.value) == value ||(value != null && value.equals(v)))) {if (node instanceof TreeNode)((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);else if (node == p)tab[index] = node.next;elsep.next = node.next;++modCount;--size;// 删除节点后的操作afterNodeRemoval(node);return node;}}return null;``}``

afterNodeRemoval 方法在 HashMap 中的实现也是空的：

``void afterNodeRemoval(Node<K,V> p) { }``

``void afterNodeRemoval(Node<K,V> e) { // unlinkLinkedHashMap.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;elseb.after = a;if (a == null)tail = b;elsea.before = b;``}``

## 3. 用法示例

``Map<String, String> map = new HashMap<>();map.put("bush", "a");map.put("obama", "b");map.put("trump", "c");map.put("lincoln", "d");System.out.println(map);// 输出结果（无序）：``// {obama=b, trump=c, lincoln=d, bush=a}``

``Map<String, String> map = new LinkedHashMap<>();map.put("bush", "a");map.put("obama", "b");map.put("trump", "c");map.put("lincoln", "d");System.out.println(map);// 输出结果（插入顺序）：``// {bush=a, obama=b, trump=c, lincoln=d}``

``Map<String, String> map = new LinkedHashMap<>(2, 0.75f, true);map.put("bush", "a");map.put("obama", "b");map.put("trump", "c");map.put("lincoln", "d");System.out.println(map);map.get("obama");System.out.println(map);// 输出结果（插入顺序）：// {bush=a, obama=b, trump=c, lincoln=d}// 访问 obama 后，obama 移到了末尾``// {bush=a, trump=c, lincoln=d, obama=b}``

### 3.2 实现 LRU 缓存

``private static class LRUCache<K, V> extends LinkedHashMap<K, V> {private int capacity;public LRUCache(int capacity) {super(16, 0.75f, true);this.capacity = capacity;}@Overrideprotected boolean removeEldestEntry(Map.Entry<K, V> eldest) {return size() > capacity;}``}``

``LRUCache<String, String> lruCache = new LRUCache<>(2);lruCache.put("bush", "a");lruCache.put("obama", "b");lruCache.put("trump", "c");System.out.println(lruCache);// 输出结果：``// {obama=b, trump=c}``

## 4. 小结

1. LinkedHashMap 继承自 HashMap，其结构可以理解为「双链表 + 散列表」；
2. 可以维护两种顺序：插入顺序或访问顺序；
3. 可以方便的实现 LRU 缓存；
4. 线程不安全。

1 声望

0 粉丝

0 条评论

## 2. 代码分析

### 2.1 节点类 Entry

LinkedHashMap 内部有一个嵌套类 Entry，它继承自 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);}``}``

``static class Node<K,V> implements Map.Entry<K,V> {final int hash;final K key;V value;Node<K,V> next;Node(int hash, K key, V value, Node<K,V> next) {this.hash = hash;this.key = key;this.value = value;this.next = next;}// ...``}``

### 2.2 成员变量

``/*** The head (eldest) of the doubly linked list.*/transient LinkedHashMap.Entry<K,V> head;/*** The tail (youngest) of the doubly linked list.*/transient LinkedHashMap.Entry<K,V> tail;/*** The iteration ordering method for this linked hash map: true* for access-order, false for insertion-order.* LinkedHashMap 的迭代顺序：true 为访问顺序；false 为插入顺序。*/``final boolean accessOrder;``

### 2.3 构造器

• 构造器1

``/*** Constructs an empty insertion-ordered LinkedHashMap instance* with the default initial capacity (16) and load factor (0.75).*/public LinkedHashMap() {super();accessOrder = false;``}``

• 构造器 2、3、4、5

``public LinkedHashMap(int initialCapacity) {super(initialCapacity);accessOrder = false;}public LinkedHashMap(int initialCapacity, float loadFactor) {super(initialCapacity, loadFactor);accessOrder = false;}public LinkedHashMap(Map<? extends K, ? extends V> m) {super();accessOrder = false;putMapEntries(m, false);}public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) {super(initialCapacity, loadFactor);this.accessOrder = accessOrder;``}``

### 2.4 put 方法

LinkedHashMap 本身没有实现 put 方法，它通过调用父类（HashMap）的方法来进行读写操作。这里再贴下 HashMap 的 put 方法：

``public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;if ((p = tab[i = (n - 1) & hash]) == null)// 新的 bin 节点tab[i] = newNode(hash, key, value, null);else {Node<K,V> e; K k;// key 已存在if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;// 散列冲突else if (p instanceof TreeNode)e = ((TreeNode<K,V>)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 1sttreeifyBin(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 keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;if (++size > threshold)resize();afterNodeInsertion(evict);return null;``}``

``Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {return new Node<>(hash, key, value, next);``}``

``// 新建一个 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;``}``

``// link at the end of listprivate void linkNodeLast(LinkedHashMap.Entry<K,V> p) {LinkedHashMap.Entry<K,V> last = tail;tail = p;// list 为空if (last == null)head = p;else {// 将新节点插入到 list 末尾p.before = last;last.after = p;}``}``

``// Callbacks to allow LinkedHashMap post-actionsvoid afterNodeAccess(Node<K,V> p) { }``void afterNodeInsertion(boolean evict) { }``

``void afterNodeAccess(Node<K,V> e) { // move node to lastLinkedHashMap.Entry<K,V> last;// accessOrder 为 true 表示访问顺序if (accessOrder && (last = tail) != e) {// p 为访问的节点，b 为其前驱，a 为其后继LinkedHashMap.Entry<K,V> p =(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;p.after = null;// p 是头节点if (b == null)head = a;elseb.after = a;if (a != null)a.before = b;elselast = b;if (last == null)head = p;else {p.before = last;last.after = p;}tail = p;++modCount;}``}``

### 2.5 get 方法

LinkedHashMap 重写了 HashMap 的 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;``}``

``void afterNodeInsertion(boolean evict) { // possibly remove eldestLinkedHashMap.Entry<K,V> first;if (evict && (first = head) != null && removeEldestEntry(first)) {K key = first.key;removeNode(hash(key), key, null, false, true);}}// LinkedHashMap 中默认的返回值为 false，即这里的 removeNode 方法不执行protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {return false;``}``

removeNode 方法是父类 HashMap 中的：

``final Node<K,V> removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable) {Node<K,V>[] tab; Node<K,V> p; int n, index;// table 不为空，且给的的 hash 值所在位置不为空if ((tab = table) != null && (n = tab.length) > 0 &&(p = tab[index = (n - 1) & hash]) != null) {Node<K,V> node = null, e; K k; V v;// 给定 key 对应的节点，在数组中第一个位置if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))node = p;// 给定的 key 所在位置为红黑树或链表else if ((e = p.next) != null) {if (p instanceof TreeNode)node = ((TreeNode<K,V>)p).getTreeNode(hash, key);else {do {if (e.hash == hash &&((k = e.key) == key ||(key != null && key.equals(k)))) {node = e;break;}p = e;} while ((e = e.next) != null);}}// 删除节点if (node != null && (!matchValue || (v = node.value) == value ||(value != null && value.equals(v)))) {if (node instanceof TreeNode)((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);else if (node == p)tab[index] = node.next;elsep.next = node.next;++modCount;--size;// 删除节点后的操作afterNodeRemoval(node);return node;}}return null;``}``

afterNodeRemoval 方法在 HashMap 中的实现也是空的：

``void afterNodeRemoval(Node<K,V> p) { }``

``void afterNodeRemoval(Node<K,V> e) { // unlinkLinkedHashMap.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;elseb.after = a;if (a == null)tail = b;elsea.before = b;``}``

## 3. 用法示例

``Map<String, String> map = new HashMap<>();map.put("bush", "a");map.put("obama", "b");map.put("trump", "c");map.put("lincoln", "d");System.out.println(map);// 输出结果（无序）：``// {obama=b, trump=c, lincoln=d, bush=a}``

``Map<String, String> map = new LinkedHashMap<>();map.put("bush", "a");map.put("obama", "b");map.put("trump", "c");map.put("lincoln", "d");System.out.println(map);// 输出结果（插入顺序）：``// {bush=a, obama=b, trump=c, lincoln=d}``

``Map<String, String> map = new LinkedHashMap<>(2, 0.75f, true);map.put("bush", "a");map.put("obama", "b");map.put("trump", "c");map.put("lincoln", "d");System.out.println(map);map.get("obama");System.out.println(map);// 输出结果（插入顺序）：// {bush=a, obama=b, trump=c, lincoln=d}// 访问 obama 后，obama 移到了末尾``// {bush=a, trump=c, lincoln=d, obama=b}``

### 3.2 实现 LRU 缓存

``private static class LRUCache<K, V> extends LinkedHashMap<K, V> {private int capacity;public LRUCache(int capacity) {super(16, 0.75f, true);this.capacity = capacity;}@Overrideprotected boolean removeEldestEntry(Map.Entry<K, V> eldest) {return size() > capacity;}``}``

``LRUCache<String, String> lruCache = new LRUCache<>(2);lruCache.put("bush", "a");lruCache.put("obama", "b");lruCache.put("trump", "c");System.out.println(lruCache);// 输出结果：``// {obama=b, trump=c}``

## 4. 小结

1. LinkedHashMap 继承自 HashMap，其结构可以理解为「双链表 + 散列表」；
2. 可以维护两种顺序：插入顺序或访问顺序；
3. 可以方便的实现 LRU 缓存；
4. 线程不安全。