LinkedHashMap原理和源码分析详解编程语言

LinkedHashMap 在HashMap的基础上，新增一个双向链表，每个Node增加了一个before，after，表示上一个结点和下一个结点。不过，双向链表顺序是根据插入或者访问顺序来决定的。before、after跟hashMap的next表达的含义是不一样的，next表示hash桶内部顺序，而before、after表示插入或访问顺序。

在上面的图可以很清晰的看到，蓝色的线表示的就是访问或者顺序，串联成为一个双向链表。由此也可以猜想到LinkedHashMap的原理，就是在HashMap插入、访问、删除等操作后，及时修改LinkedHashMap的双向链表，维持顺序。

LinkedHashMap 源码分析

重要的数据结构

 static class LinkedHashMapEntry K,V extends HashMap.Node K,V {

 LinkedHashMapEntry K,V before, after; 

 LinkedHashMapEntry(int hash, K key, V value, Node K,V next) {

 super(hash, key, value, next); 

LinkedHashMapEntry继承自HashMap的Node，内部多了before, after，形成一个双向链表。

transient LinkedHashMapEntry K,V head; // 双向链表头部结点 

transient LinkedHashMapEntry K,V tail; // 双向链表尾部结点 

final boolean accessOrder;// 是否按照访问顺序排序，若false，则按照插入顺序 

接下来看下LinkedHashMap内部常用的比较重要的方法：

// 插入P结点到链表尾部 

private void linkNodeLast(LinkedHashMapEntry K,V p) {

 LinkedHashMapEntry K,V last = tail; 

 tail = p; 

 if (last == null) 

 head = p; 

 else {

 p.before = last; 

 last.after = p; 

linkNodeLast 顾名思义就是把结点P挂在链表尾部，如果链表为空，就将P设置为头节点。

// 将中间的src节点（链表）替换成 dest 节点（链表） 

private void transferLinks(LinkedHashMapEntry K,V src, LinkedHashMapEntry K,V dst) {

 LinkedHashMapEntry K,V b = dst.before = src.before; 

 LinkedHashMapEntry K,V a = dst.after = src.after; 

 if (b == null) // dst.before为null，说明是头节点 

 head = dst; // 设置成头节点 

 else 

 b.after = dst; 

 if (a == null) 

 tail = dst; 

 else 

 a.before = dst; 

将中间的src节点（链表）替换成 dest 节点（链表），src、dest既可以表示链表头部也可以表示单独结点。

直接看上面的转换可能会有点难以理解的，如果参照下面的图会清晰很多。

几个重要的方法

Node K,V newNode(int hash, K key, V value, Node K,V e) {

 LinkedHashMapEntry K,V p = 

 new LinkedHashMapEntry K,V (hash, key, value, e); 

 linkNodeLast(p); 

 return p; 

 Node K,V replacementNode(Node K,V p, Node K,V next) {

 LinkedHashMapEntry K,V q = (LinkedHashMapEntry K,V )p; 

 LinkedHashMapEntry K,V t = 

 new LinkedHashMapEntry 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) {

 LinkedHashMapEntry K,V q = (LinkedHashMapEntry K,V )p; 

 TreeNode K,V t = new TreeNode K,V (q.hash, q.key, q.value, next); 

 transferLinks(q, t); 

 return t; 

以上的方法都是重写了HashMap的方法，操作基本是相同的：

将LinkedHashMapEntry替换掉Node； 修改LinkedHashMap的双向链表，插入或者替换节点，维持顺序。

例如：newNode方法，外部调用newNode获取一个新结点，而内部生成LinkedHashMapEntry，并插入LinkedhashMap内部链表的尾部。同理，replacementNode也是修改了链表。

再来看三个重要的方法

这几个方法在HashMap中都是空实现，但LinkedHashMap重写了，全都是HashMap在一些操作之后调用，例如插入、删除操作后。

afterNodeRemoval

// HashMap删除hash桶中的结点之后调用，负责将节点从双向链表移除 

void afterNodeRemoval(Node K,V e) {

 // unlink 

 LinkedHashMapEntry K,V p = 

 (LinkedHashMapEntry 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; 

afterNodeInsertion

 // HashMap插入结点之后调用，eveict表示是否移除最老的hash结点（首结点） 

 void afterNodeInsertion(boolean evict) {

 // possibly remove eldest 

 LinkedHashMapEntry K,V first; 

 if (evict (first = head) != null removeEldestEntry(first)) {

 K key = first.key; 

 removeNode(hash(key), key, null, false, true);// 需要移除最老的节点 

 // 是否移除最老的节点，默认是false 

 protected boolean removeEldestEntry(Map.Entry K,V eldest) {

 return false; 

newNode 和 afterNodeInsertion 都是在新增结点操作中引发的，但是负责的事情不一样。

newNode 负责新增一个结点，并将结点添加到双向链表中； afterNodeInsertion 负责在新增结点完成后，可能需要移除最老的结点（首结点），如LruCache。

 // hashmap调用get、replace等访问节点方法会调用 

 // 如果accessOrders是true，会将访问的节点移动到尾部，表示最新节点 

 void afterNodeAccess(Node K,V e) {

 // move node to last 

 LinkedHashMapEntry K,V last; 

 if (accessOrder (last = tail) != e) {

 LinkedHashMapEntry K,V p = 

 (LinkedHashMapEntry 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; 

entrySet
返回一个 LinkedEntrySet，内部遍历是有序的，根据双向链表进行访问

public Set Map.Entry K,V entrySet() {

 Set Map.Entry K,V es; 

 return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es; 

final class LinkedEntrySet extends AbstractSet Map.Entry K,V {

 ... 

 public final Iterator Map.Entry K,V iterator() {

 return new LinkedEntryIterator(); 

final class LinkedEntryIterator extends LinkedHashIterator 

 implements Iterator Map.Entry K,V {

 public final Map.Entry K,V next() {

 return nextNode(); } 

顺着再看下LinkedHashIterator怎么实现的

abstract class LinkedHashIterator {

 LinkedHashMapEntry K,V next; 

 LinkedHashMapEntry K,V current; 

 int expectedModCount; 

 LinkedHashIterator() {

 next = head;// 双向链表首节点 

 expectedModCount = modCount; 

 current = null; 

 final LinkedHashMapEntry K,V nextNode() {

 LinkedHashMapEntry K,V e = next; 

 if (modCount != expectedModCount) 

 throw new ConcurrentModificationException(); 

 if (e == null) 

 throw new NoSuchElementException(); 

 current = e; 

 next = e.after; 

 return e; 

 ... 

在LinkedHashIterator 构造函数中，next被赋为首节点，每次nextNode()就顺着LinkHashMap的双向链表往后访问，这样就能维持entrySet()的有序访问

19400.html

cjavaxml