LinkedHashMap-一一网

这是我参与8月更文挑战的第20天，活动详情查看：8月更文挑战

类头

This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries.
复制代码

在hashMap的基础上，针对数组的bin，额外添加了双向链表存储结构。

类声明

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
复制代码

重写方法：

newNode()
replacementNode() //hashMap中，树退化时使用的生产方法,配合使用的是LHM中的transferLinks
newTreeNode()
replacementTreeNode()
internalWriteEntries()//IO序列化相关
get()//以及相关方法  
reinitialize()//super（）+首尾=null
复制代码

实现父类中留口的三个特殊方法：

void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
复制代码

hashMap中对这三个方法的注释是：

Callbacks to allow LinkedHashMap post-actions

维护变量

数据结构相关

transient LinkedHashMap.Entry<K,V> head;

transient LinkedHashMap.Entry<K,V> tail;
复制代码

声明了双向链表的关键托管结构：首尾节点，符合上面说的

it maintains a doubly-linked list running through all of its entries

遍历相关

/**
 * The iteration ordering method for this linked hash map: <tt>true</tt>
 * for access-order, <tt>false</tt> for insertion-order.
 *
 * @serial
 */
final boolean accessOrder;
复制代码

这个变量的含义是（from blog.csdn.net/weixin_3691…

值	含义
true	会把访问过的元素放在链表后面，放置顺序是访问的顺序
false	按插入顺序来遍历

主存储结构

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);
    }
}
复制代码

类方法

结构特化方法

linkNodeLast（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;
    }
}
复制代码

本身没什么特殊的，就是把节点挂到尾节点的后面。

调用该方法的方法：

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中的数组，而是额外维护了一个双向链表来存储数据。

transferLinks

// apply src's links to dst
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;
    if (b == null)
        head = dst;
    else
        b.after = dst;
    if (a == null)
        tail = dst;
    else
        a.before = dst;
}
复制代码

把src的节点，都赋给dst
- 调用该方法的方法

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> 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留口方法

 void afterNodeAccess(Node<K,V> p) { }
 void afterNodeInsertion(boolean evict) { }
 void afterNodeRemoval(Node<K,V> p) { }
复制代码

afterNodeAccess

节点访问后的操作
- 如果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;
     }
 }
复制代码

afterNodeInsertion

节点插入后的操作

 void afterNodeInsertion(boolean evict) { // possibly remove eldest
     LinkedHashMap.Entry<K,V> first;
     if (evict && (first = head) != null && removeEldestEntry(first)) {
         K key = first.key;
         removeNode(hash(key), key, null, false, true);
     }
 }
 
     protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
         return false;
     }
复制代码

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;
 }
复制代码

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;
  }
 
  /**
   * {@inheritDoc}
   */
  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;
 }
复制代码

这里就能看到accessOrder的用处之一了：查询节点的控制。

但是get方法并没有进行完整的重写，可能是hash值+节点数据结构的形式，查询起来直观上就能感觉到，比链表+节点数据结构要快的原因吧。

 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;
 }
复制代码