本文共 3416 字，大约阅读时间需要 11 分钟。

之前介绍过HashMap，HashMap的存储是无序的，LinkedHashMap在HashMap的基础上记录了每次添加的顺序，LinkedHashMap总体上实现方法大都是HashMap的方法。其实现方式，是数组+单向链表+双向链表+红黑树

我们先来看下LinkedHashMap保存元素的结构

static class Entry
   
     extends HashMap.Node
    
      {        Entry
     
       before, after;        Entry(int hash, K key, V value, Node
      
        next) {            super(hash, key, value, next);        }    }
      
     
    
   

这个Entry对象继承了HashMap.Node对象，同时又添加了前后节点，实现LinkedHashMap的顺序，在每次添加一个元素时，都会将新增元素放在Entry的最后，通知将原tail的after指向新添加的元素，新添加元素的before指向原来的tail, next是用来记录hash值计算出来的桶的位置相同时，将新添加元素放在桶中链表的最后。

在添加元素时：

如果新添加一个Node元素

Node
   
     newNode(int hash, K key, V value, Node
    
      e) {        LinkedHashMap.Entry
     
       p =            new LinkedHashMap.Entry
      
       (hash, key, value, e); //创建一个新的Node节点，这一步和HashMap相同        linkNodeLast(p);  //LinkedHashMap需要关联好添加元素的前后关系        return p;    }
      
     
    
   

private void linkNodeLast(LinkedHashMap.Entry
   
     p) {        LinkedHashMap.Entry
    
      last = tail; //获取到最后一个添加的元素        tail = p;  //设定当前元素为tail        if (last == null)  //如果tail等于null，说明head也是null, 将当前元素设置成head            head = p;        else {              p.before = last; //将原来的tail设置成新添加元素的before            last.after = p; //将tail的after设置成新添加元素，        }    }
    
   

这一步主要是按照添加元素的顺序建立好双向链表的关联关系。

接下来我们来看afterNodeAccess方法，这个方法会在每次更新节点，get查询某个节点之后调用

void afterNodeAccess(Node
   
     e) { // 将当前节点移动至最后        LinkedHashMap.Entry
    
      last;        if (accessOrder && (last = tail) != e) { //如果当前节点已经是tail了，就不需要移动了            LinkedHashMap.Entry
     
       p =                (LinkedHashMap.Entry
      
       )e, b = p.before, a = p.after;            p.after = null; //            if (b == null) //如果当前节点的前一个节点为null,说明当前节点是head节点，移动之后，将head节点设置成当前节点的后面节点                head = a;            else                b.after = a; // 将前一个节点的后置节点设置成当前节点后面的节点            if (a != null)  // 如果当前节点后面的节点不为null,                a.before = b; // 将当前节点的前置节点设置成当前节点的原前置节点            else                last = b; //否则将tail设置成当前节点的前面的节点            if (last == null)  //如果tail是null,将head设置成当前节点的前一个节点                head = p;            else {                p.before = last; // 否则把当前节点前面的节点设置成tail                last.after = p;            }            tail = p;            ++modCount;        }    }
      
     
    
   

如果我们之前设定了accessOrder为true,那么每次就会重新更新一下链表的顺序,这个方法主要是将当前操作的元素，原来维护的双向链表关系修改为前后链表双向关联，当前元素和tail元素双向关联，1,2,3,4,5,6为插入元素时顺序

关于判断是否包含某个value的值，LinkedHashMap的处理方式

public boolean containsValue(Object value) {        for (LinkedHashMap.Entry
   
     e = head; e != null; e = e.after) {            V v = e.value;            if (v == value || (value != null && value.equals(v)))                return true;        }        return false;    }
   

可以看出来是从head元素一直遍历到tail,直到找到value相同的，而HashMap的遍历方式，先从Table最外层开始遍历，然后从链表当中遍历，直到找到value相同的值

对于双向链表，如果要移除一个元素，那么双向链表之间维护的关系也需要重新修改

void afterNodeRemoval(Node
   
     e) { // unlink        LinkedHashMap.Entry
    
      p =            (LinkedHashMap.Entry
     
      )e, b = p.before, a = p.after;        p.before = p.after = null; //将当前需要移除元素的前后关联都清空，gc回收数据        if (b == null) //如果当前元素的前面元素等于null            head = a;//说明当前删除元素是head，需要把head改为当前元素后面的元素        else             b.after = a; // 将前面的节点的后置节点设置原后置节点        if (a == null)            tail = b;        else            a.before = b;    }
     
    
   

这个方法主要是，将删除元素的双向关联关系去除掉

在遍历LinkedHashMap时，取出来的顺序就是我们插入进去的顺序。