重识java-LinkedHashMap

使用场景

如果需要使用的Map中的key无序，选择HashMap；如果要求key有序，则选择TreeMap。 但是选择TreeMap就会有性能问题，因为TreeMap的get操作的时间复杂度是O(log(n))的，相比于HashMap的O(1)还是差不少的，LinkedHashMap的出现就是为了平衡这些因素，使得 能够以O(1)时间复杂度增加查找元素，又能够保证key的有序性 此外，LinkedHashMap提供了两种key的顺序：

• 访问顺序（access order）。非常实用，可以使用这种顺序实现LRU（Least Recently Used）缓存
• 插入顺序（insertion orde）。同一key的多次插入，并不会影响其顺序

源代码解读

类声明

public class LinkedHashMap
    
         extends HashMap
     
          implements Map
      
     
    

继承自HashMap，此处实现Map接口，用来表明该类是Map系的类。

功能和特点

1. LinkedHashMap中采用的这种环型双向链表.
2. key有序，并且get时间复杂度为O(1)。
3. 有两种记录顺序的方式，一种是访问顺序，一种是key插入的顺序。

常量

final boolean accessOrder;//true：key的顺序为访问顺序；false：key的顺序为插入式顺序。默认为插入顺序transient LinkedHashMap.Entry
    
      head;//双向链表头结点transient LinkedHashMap.Entry
     
       tail;//双向链表尾结点
     
    

构造函数

public LinkedHashMap(int initialCapacity, float loadFactor) {    super(initialCapacity, loadFactor);    //默认为false，也就是插入顺序    accessOrder = false;}public LinkedHashMap(int initialCapacity) {    super(initialCapacity);    accessOrder = false;}public LinkedHashMap() {    super();    accessOrder = false;}public LinkedHashMap(Map
     m) {    super();    accessOrder = false;    putMapEntries(m, false);}public LinkedHashMap(int initialCapacity,                     float loadFactor,                     boolean accessOrder) {    super(initialCapacity, loadFactor);    this.accessOrder = accessOrder;}

节点数据结构

主要基于HashMap的节点数据结构实现。

static class Entry
    
      extends HashMap.Node
     
       {	    //每个节点包含两个指针，指向前继节点与后继节点        Entry
      
        before, after;        Entry(int hash, K key, V value, Node
       
         next) {            super(hash, key, value, next);        }    }
       
      
     
    

双向链表实现的LinkedHshMap，所以每个节点须在HashMap的基础上添加指向前继节点与后继节点指针：before，after。

private void linkNodeLast(LinkedHashMap.Entry
    
      p) {    LinkedHashMap.Entry
     
       last = tail;    tail = p;    if (last == null)        head = p;    else {        p.before = last;        last.after = p;    }}
     
    

在最后添加一个节点，需要取LinkedHashMap的末尾节点，

1. 双向链表为空（末为节点为空），这新添加的既是头节点，也是尾节点；
2. 如果不为空，p的前继指向原最后一个节点，最后一个节点的后继指向p。

void afterNodeRemoval(Node
    
      e) { // unlink    LinkedHashMap.Entry
     
       p =        (LinkedHashMap.Entry
      
       )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;}
      
     
    

删除一个节点时，需要把

1. 前继节点的后继指针 指向 要删除节点的后继节点
2. 后继节点的前继指针 指向 要删除节点的前继节点

核心方法

afterNodeRemoval

void afterNodeRemoval(Node
    
      e) { // unlink    LinkedHashMap.Entry
     
       p =        (LinkedHashMap.Entry
      
       )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

void afterNodeInsertion(boolean evict) { // possibly remove eldest    LinkedHashMap.Entry
    
      first;    // 如果定义了溢出规则，则执行相应的溢出    if (evict && (first = head) != null && removeEldestEntry(first)) {        K key = first.key;        removeNode(hash(key), key, null, false, true);    }}
    

如果用户定义了removeEldestEntry的规则，那么便可以执行相应的移除操作。

afterNodeAccess

void afterNodeAccess(Node
    
      e) { // move node to last    LinkedHashMap.Entry
     
       last;    // 如果定义了accessOrder，那么就保证最近访问节点放到最后    if (accessOrder && (last = tail) != e) {        LinkedHashMap.Entry
      
        p =            (LinkedHashMap.Entry
       
        )e, b = p.before, a = p.after;        p.after = null;		//e的前驱还有节点，e不是头结点，否则e是头结点。        if (b == null)            head = a;//把头结点后移一个        else            b.after = a;//把中间节点移除                //e是不是tail节点，是tail节点，则使last为e的前驱        if (a != null)            a.before = b;        else            last = b;                //链表中只有节点e         if (last == null)            head = p;        else {//将p移到最后            p.before = last;            last.after = p;        }        tail = p;        ++modCount;    }}
       
      
     
    

进行put之后,对节点的访问了，那么这个时候就会更新链表，把最近访问的放到最后，保证链表的key按照访问有序。

put put函数在LinkedHashMap中未重新实现，只是实现了afterNodeAccess和afterNodeInsertion两个回调函数。

get

public V get(Object key) {    Node
    
      e;    if ((e = getNode(hash(key), key)) == null)        return null;    if (accessOrder)        afterNodeAccess(e);    return e.value;}
    

get函数重新实现并加入了afterNodeAccess来保证访问顺序

总结

1. 怎样保证插入顺序？ 使用前驱和后继指针，使得原来的HashMap有序，在LinkedHashMap中覆盖HashMap中newNode 方法，使得每次put数据时，新建的节点都是LinkedHashMap.Entry<K,v> 类型的，比普通的HsahMap.Entry 多一个前驱结点和一个后继节点，使用前驱和后继保证插入有序。
2. 怎么样保证访问顺序？ 覆盖父类HashMap的afterNodeAccess 方法，使得每次访问后，都改变链表顺序。使得原链表按访问排序。将最新一次访问的节点放到链表的最后。

Thanks for reading!