LinkedHashMap

LinkedHashMap

LinkedHashMap是Java集合框架中的一种实现，它是 HashMap 的子类，并使用双向链表来维护元素的插入顺序或访问顺序。与 HashMap 不同，LinkedHashMap 中元素的顺序是可以预测的。因此，LinkedHashMap 非常适合需要按照顺序遍历元素的场景。

作用

1. LinkedHashMap 的主要作用是维护元素的顺序，这使得它非常适合于需要按照顺序遍历元素的场景。例如，缓存实现或记录某些操作的日志。
2. LinkedHashMap 还能支持按照访问顺序来维护元素顺序，这意味着可以根据元素的访问顺序进行遍历。

优势

相比于 HashMap，LinkedHashMap 的优势在于它可以维护元素的插入顺序或访问顺序。这使得 LinkedHashMap 非常适合需要按照顺序遍历元素的场景。虽然与 HashMap 相比，在插入和删除操作上 LinkedHashMap 稍慢，但遍历操作更快。

思考点：

1. LinkedHashMap 在 HashMap 的基础上做了什么改动，是怎么样实现双向链表的？

   想了解 LinkedHashMap 的调整, 首先我们需要记住 LinkedHashMap 中的两个变量 head (头节点)和 tail (尾节点)。

   双向链表的实现: 在 LinkedHashMap 中对 HashMap.Node 节点进行了扩展, 补充了before(前), **after(后)**节点信息, 然后在创建新Note节点时, 进行了双向链表的(**before、after)**的绑定

   // 对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);
       }
   }
   
   Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
   	  LinkedHashMap.Entry<K,V> p =
   	      new LinkedHashMap.Entry<>(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<>(hash, key, value, next);
       // 设置双向链表节点
       linkNodeLast(p);
       return p;
   }
   
   // 设置节点双向链表
   private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
       // 缓存尾节点tail
       LinkedHashMap.Entry<K,V> last = tail;
   		// 重新定义尾节点
       tail = p;
       if (last == null)
           // 如果之前不存在尾节点时, 则当前是第一次插入, 不进行处理
           head = p;
       else {
           // 把插入节点的前一个节点设置为尾节点last
           p.before = last;
           // 尾节点的后一个节点设置为插入节点p
           last.after = p;
       }
   }
   

   对 HashMap 的扩展: 在 HashMap 中提供了如下方法

   // 在对设置节点value后的扩展
   void afterNodeAccess(Node<K,V> p) { }
   // 节点添加完成后的扩展
   void afterNodeInsertion(boolean evict) { }
   // 删除节点后的扩展
   void afterNodeRemoval(Node<K,V> p) { }
   

   而 LinkedHashMap 对上述三个方法进行了调整

   • afterNodeAccess 设置值后, 在按照 访问顺序排序 时, 会把操作节点移动到链表最后一位
   • afterNodeInsertion 插入新节点后执行一些操作, 主要目的是实现基于访问顺序的缓存策略
   • afterNodeRemoval 删除节点后的操作, 重新删除节点的前后节点关系

2. LinkedHashMap 和 HashMap 相比为什么说遍历操作更快。

   在为什么快之前需要先大概了解 HashMap 的遍历方式。已经知道 HashMap 是通过 数组+链表(黑红树)实现的, 那么 HashMap 在遍历的时候, 其实是先遍历遍历数组获取到hash桶, 然后在遍历hash桶获取到真实的节点数据。

   而对于 LinkedHashMap 来说, 因为已经实现了双向链表, 所以不需要想 HashMap 中一样关心那么多, 只需要通过内部定义的变量 head (头节点)直接对链表进行遍历就好。

   所以才会说 LinkedHashMap 在遍历上比 HashMap 快。

使用案例

在 LinkedHashMap 中, 模式是按照插入顺序排序, 但是如果将 accessOrder 设置为 true，那么 LinkedHashMap 将会按照访问/操作顺序来调整元素的顺序，即最近访问/操作的元素将被放在最后。

LinkedHashMap<String, String> linkedHashMap = new LinkedHashMap<>(16 , 0.75f, Boolean.TRUE);
linkedHashMap.put("1", "1");
linkedHashMap.put("2", "2");
linkedHashMap.get("2");
System.out.println(linkedHashMap); // {"2"="2","1"="1"} 发送改变

实现原理, 通过对 HashMap.afterNodeAccess 进行扩展, 当插入时, 对链表进行重新排序, 把访问/操作的节点设置到尾节点

// e为操作节点
void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {
        // p -> 操作节点
        LinkedHashMap.Entry<K,V> p =(LinkedHashMap.Entry<K,V>)e, 
        // b -> 操作节点前节点
        b = p.before, 
        // a -> 操作节点后节点
        a = p.after;
				
        // 设置操作节点到尾节点, 然后重新绑定操作节点的前后节点关系
        p.after = null;
        // 如果前节点不存在, 标识操作节点为头节点, 把a设置为头节点信息
        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;
    }
}