添加链接 注册    登录
link管理
链接快照平台
  • 输入网页链接，自动生成快照
  • 标签化管理网页链接
相关文章推荐
豪气的毛豆  ·  Get started: Install ...·  2 月前    · 
自信的凳子  ·  什么是公钥和私钥？ - 数字证书管理服务 ...·  2 月前    · 
文雅的登山鞋  ·  【星空体育】(中国)股份有限公司官网·  5 月前    · 
挂过科的机器猫  ·  余杭如何聚焦补齐教育、医疗等公共服务？公共服 ...·  5 月前    · 
高大的日光灯  ·  发展成果_华润集团欢迎您·  7 月前    · 
link管理  ›  Java编程拾遗『LinkedHashMap』_linkedhashmap(16, 0.75f, true)
lrucache 指针变量 链表 hashmap
https://blog.csdn.net/weixin_41835612/article/details/86686462
想表白的面包
3 月前

在之前的文章，分别介绍过HashMap、TreeMap。HashMap就是普通的K-V存储数据结构，TreeMap在K-V存储数据结构的基础上添加了K-V之间按键值有序的特性。本篇文章来介绍一下，另一种特殊的K-V存储数据结构LinkedHashMap。LinkedHashMap是HashMap的子类，但可以保持元素按插入或访问有序（默认是按插入顺序有序）。LinkedHashMap继承关系如下：

LinkedHashMap是HashMap的子类，每个键值对都是通过之前讲HashMap的存储方式(数组 + 链表 + 红黑树)存储的，但同时内部各个键值对之间还有一个双向链表维护键值对的顺序。所以，HashMap除了键值对之间无序之外所有的特性，LinkedHashMap都有，比如存储方式、hash策略、扩容机制等。LinkedHashMap支持两种顺序，一种是插入顺序，另外一种是访问顺序。插入顺序是指，先添加的在前面，后添加的在后面，修改操作不影响顺序。访问顺序是指get/put操作，对一个键执行get/put操作后，其对应的键值对会移到双向链表末尾，所以，最末尾的是最近访问的，最开始的最久没被访问的，这种顺序就是访问顺序。

1. 调用示例 

public static void main(String[] args) {
    /*默认构造函数，按照插入顺序有序*/
    System.out.println("按插入顺序有序：");
    Map<Integer, String> linkedHashMap = new LinkedHashMap<>();
    linkedHashMap.put(1, "a");
    linkedHashMap.put(2, "b");
    linkedHashMap.put(3, "c");
    linkedHashMap.put(4, "d");
    /*按插入顺序有序时，put修改操作，并不会改变顺序*/
    linkedHashMap.put(3, "e");
    Iterator iterator = linkedHashMap.entrySet().iterator();
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    * public LinkedHashMap(int initialCapacity,
                           float loadFactor,
                           boolean accessOrder)
      构造函数，指定accessOrder为true时，可以按照访问顺序有序
    System.out.println("按访问顺序有序：");
    linkedHashMap = new LinkedHashMap<>(16, 0.75f, true);
    linkedHashMap.put(1, "a");
    linkedHashMap.put(2, "b");
    linkedHashMap.put(3, "c");
    linkedHashMap.put(4, "d");
    /*1 -> 2 -> 3 -> 4*/
    linkedHashMap.get(2);//2被访问了，移动到内部双向链表末尾
    /*1 -> 3 -> 4 -> 2*/
    linkedHashMap.get(4);//4被访问了，移动到内部双向链表末尾
    /*1 -> 3 -> 2 -> 4*/
    linkedHashMap.put(1, "e");//1被访问(put)了，移动到内部双向链表末尾
    /*3 -> 2 -> 4 -> 1*/
    linkedHashMap.put(5, "f");//插入5
    /*3 -> 2 -> 4 -> 1 -> 5*/
    iterator = linkedHashMap.entrySet().iterator();
    while (iterator.hasNext()) {
        System.out.println(iterator.next());

运行结果：
 

按插入顺序有序：
按访问顺序有序：

1.1 按插入有序使用场景
 

LinkedHashMap经常用来处理一些数据，接受一些键值对作为输入，处理，然后输出，输出时希望跟插入的顺序保持一致。比如从数据库查询数据放到内存时，已经使用SQL的order by语句让数据库对数据排序，在数据输入有序的前提下，希望通过Map存储查询结果，并且保持顺序输出，这时候就没必要使用TreeMap了，效率比LinkedHashMap低(TreeMap直接使用红黑树存储，LinkedHashMap使用Hash表)，直接使用LinkedHashMap也能达到相同的排序目标。
 

1.2 按访问有序使用场景
 

上面的例子，已经讲了按访问有序的示例。那么按访问有序在开发中有什么使用场景？最常见的一个用法就是通过LinkedHashMap的按访问有序实现LRU(Least Recently Used—最近最久未使用)算法。
 
 
缓存，原始意义是指访问速度比一般随机存取存储器（RAM）快的一种RAM，通常它不像系统主存那样使用DRAM技术，而使用昂贵但较快速的SRAM技术。当CPU处理数据时，它会先到缓存中去寻找，如果数据因之前的操作已经读取而被暂存其中，就不需要再从随机存取存储器（Main memory）中读取数据——由于CPU的运行速度一般比主内存的读取速度快，主存储器周期（访问主存储器所需要的时间）为数个时钟周期。因此若要访问主内存的话，就必须等待数个CPU周期从而造成浪费。
 
 
CPU的缓存曾经是用在超级计算机上的一种高级技术，不过现今计算机上使用的的AMD或Intel微处理器都在芯片内部集成了大小不等的数据缓存和指令缓存，通称为L1缓存；而比L1更大容量的L2缓存曾经被放在CPU外部（主板或者CPU接口卡上），但是现在已经成为CPU内部的标准组件；更昂贵的CPU会配备比L2缓存还要大的L3缓存（level 3 On-die Cache第三级高速缓冲存储器）。L1容量缓存非常小、价格非常贵、读取速度快，三级缓存容量会大一些、便宜一些、读取速度也慢一些。
 
 
如今缓存的概念已被扩充，不仅在CPU和主内存之间有Cache，而且在内存和硬盘之间也有Cache（磁盘缓存），乃至在硬盘与网络之间也有某种意义上的Cache──称为Internet临时文件夹或网络内容缓存等。凡是位于速度相差较大的两种硬件之间，用于协调两者数据传输速度差异的结构，均可称之为Cache。
 

主存容量远大于CPU缓存，磁盘容量远大于主存，因此无论是哪一层次的缓存都面临一个同样的问题：当容量有限的缓存的空闲空间全部用完后，又有新的内容需要添加进缓存时，如何挑选并舍弃原有的部分内容，从而腾出空间放入这些新的内容。解决这个问题的算法有几种，如最久未使用算法（LFU）、先进先出算法（FIFO）、最近最少使用算法（LRU）、非最近使用算法（NMRU）等，这些算法在不同层次的缓存上执行时拥有不同的效率和代价，需根据具体场合选择最合适的一种。而本文讲的LinkedHashMap的按访问有序，就可以很容易的实现LRU算法。
 

LinkedHashMap中存在一个protected方法，如下：
 

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;

这个方法用于插入键值对后调用，如果返回true，则会清除LinkedHashMap中“最老”(最久未访问)的键值对，LinkedHashMap的实现总是返回false，所以无论何时插入键值对，都不会对之前的键值对进行清除。所以如果要实现实现LRU算法，只要继承LinkedHashMap类，并按照具体策略重写此方法即可，如下：
 

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private int maxSize;
    public LRUCache(int maxSize){
        super(16, 0.75f, true);
        this.maxSize = maxSize;
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxSize;
    public static void main(String[] args) {
        LRUCache<Integer, String> lruCache = new LRUCache<>(3);
        lruCache.put(1, "a");
        lruCache.put(2, "b");
        lruCache.put(3, "c");
        //访问1->a
        //key顺序为：2 -> 3 -> 1
        System.out.println(lruCache.get(1));
        //插入一个新键值对，理论上，由于超过LruCache的maxSize了，所以会删除最老的键值对
        //插入后，删除最老键值对前，key顺序：2 -> 3 -> 1 -> 4
        //所以最老的键值对，key为2
        lruCache.put(4, "d");
        System.out.println(lruCache);

运行结果：
 
{3=c, 1=a, 4=d}
 

限定缓存容量为3，先后添加了4个键值对，最久没被访问的key是”2″，会被删除。
 

2. 方法说明
 

LinkedHashMap的设计很巧妙，使用了钩子方法的设计模式，在HashMap中定义了钩子方法，然后再LinkedHashMap中实现，在钩子方法中保证键值对之间的顺序。
 

2.1 构造函数
 

S.N.方法说明
1public LinkedHashMap()默认构造函数，调用HashMap默认构造函数，元素保持按插入有序
2public LinkedHashMap(int initialCapacity)指定初始化时HashMap的容量，元素保持按插入有序
3public LinkedHashMap(int initialCapacity, float loadFactor)指定初始化时HashMap的容量和负载因子，元素保持按插入有序
4public LinkedHashMap(Map<? extends K, ? extends V> m)通过Map构建LinkedHashMap，，元素保持按插入有序
5public LinkedHashMap(int initialCapacity,
 float loadFactor,
 boolean accessOrder)		指定初始化时HashMap的容量和负载因子，以及迭代输出节点的顺序，accessOrder为true时，
 元素间保持按访问有序
 

2.2 Map接口
 

除了构造函数之外的方法，全部继承自HashMap，但是针对个别方法，进行了重写。
 

S.N.方法说明
1void clear()清除Map中所有的KV映射
2default V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction)Java 8新方法，如果key在Map中不存在，则根据Function规则计算key对应的value值，
 并进行put操作(前提计算得到的value值也不为null)
3default V computeIfPresent(K key,
 BiFunction<? super K, ? super V, ? extends V> remappingFunction)		Java 8新方法，如果key在Map中存在，则根据BiFunction规则通过key和对应的value
 计算newValue，如果newValue为null，则删除key对应的键值对，否则替换key对应的value值
4default V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction)Java 8新方法，相当于上述两个方法的综合，根据BiFunction，通过key和对应的value
 计算newValue，如果newValue为null，会删除对应KV映射，否则会插入或替换原KV映射
5boolean containsKey(Object key)判断Map中是否存在key键
6boolean containsValue(Object value)判断Map中是否存在value值
7Set<Map.Entry<K, V>> entrySet()将Map所有的键值对转换为Set集合
8boolean equals(Object o)equals方法
9default void forEach(BiConsumer<? super K, ? super V> action)Java 8新方法，遍历Map，通过BiConsumer处理Map中每一个键值对的key、value
10V get(Object key)获取Map中key对应的value
11default V getOrDefault(Object key, V defaultValue)Java 8新方法，获取Map中key对应的value，如果key不存在，则返回defaultValue
12int hashCode()hashCode方法
13boolean isEmpty()判断Map是否为空
14Set<K> keySet()将Map中所有的key转化为Set集合
15default V merge(K key, V value,
 BiFunction<? super V, ? super V, ? extends V> remappingFunction)		如果key在Map中不存在或者对应的值为null，则给其一个对应的非null值value。否则根据
 BiFunction规则通过oldValue和value计算一个newValue，替换或删除(newValue为null)原
 键值对
16V put(K key, V value);为Map添加一个键值对
17void putAll(Map<? extends K, ? extends V> m)将另一个Map的所有键值对添加到该Map中
18default V putIfAbsent(K key, V value)Java 8新方法，如果Map中key不存在，则添加一个key-value键值对
19V remove(Object key)从Map中移除key对应的键值对
20default boolean remove(Object key, Object value)Java8新方法，删除key-value键值对
21default V replace(K key, V value)Java8新方法，将Map中key对应的值替换为value
22default boolean replace(K key, V oldValue, V newValue)Java8新方法，将Map中key-oldValue键值对的value值替换为newValue
23default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function)Java8新方法，将Map中所有的键值对的value，替换为根据BiFunction规则通过key-value
 得到的新值
24int size()返回Map中EntrySet的数目
25Collection<V> values()返回Map中所有value组成的集合
 

3. 实现源码分析
 

3.1 LinkedHashMap类声明
 

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
     * LinkedHashMap键值对类
    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);
     * 双向链表头(最老的元素)
    transient LinkedHashMap.Entry<K,V> head;
     * 双向链表尾(最新的元素)
    transient LinkedHashMap.Entry<K,V> tail;
     * LinkedHashMap访问顺序:
     * true: 按访问有序
     * false: 按插入有序
     * @serial
    final boolean accessOrder;
    //成员方法

相比于HashMap，LinkedHashMap中的每一个节点Entry除了有一个next指针(继承自HashMap.Node)外，还有一个指向当前Entry前驱和后继的before、after指针。除此之外，还添加了一个成员变量accessOrder，表示LinkedHashMap访问顺序。LinkedHashMap可以说是通过数组 + 链表 + 红黑树 + 双向链表实现的。假设hash算法就是简单的用key mod 一下表的大小（也就是数组的长度），其中的哈希桶数组table的size=4，负载因子loadFactor=1，通过put顺序添加如下四个元素（5、1、9、3为键值对的key），则LinkedHashMap存储结构如下：
 


 由上图可以清楚的看到，LinkedHashMap = HashMap + before&after构成的双向链。当LinkedHashMap发生改变时，当前双向链表结构也会发生改变，保证head始终指向“最老”的节点，tail始终指向“最新”的节点。比如按访问有序前提下，现有LinkedHashMap结构如上图，这时候代码调用了linkedHashMap.get(1)操作，那么节点1会移动到双向链表的尾部，tail指向节点1，节点5的后继变为节点9。下面讲实现时，会详细讲解。
 

3.2 构造函数
 
* 调用HashMap默认构造函数初始化HashMap，访问顺序按插入有序
public LinkedHashMap() {
    super();
    accessOrder = false;
* 指定HashMap初始容量，访问顺序按插入有序
public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
* 通过Map初始化LinkedHashMap
public LinkedHashMap(Map<? extends K, ? extends V> m) {
    //调用HashMap默认构造函数初始化HashMap
    super();
    accessOrder = false;
    //通过调用putMapEntries方法，将Map中的键值对插入到默认构造函数构造的HashMap中
    //putMapEntries方法第二个参数控制插入后是否进行检查，清除最老元素
    //按插入有序，所以在插入元素后，不用考虑是否需要删除最老元素，直接赋值false即可
    putMapEntries(m, false);
* 初始化一定容量，负载因子的HashMap，并指定LinkedHashMap的访问顺序
* 这个构造函数也是唯一一个能够指定访问顺序的构造函数
public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;

3.3 put操作
 

LinkedHashMap类中没有重写HashMap的put和putAll，那么它是怎么实现上面讲的双向链表元素顺序的？我们可能有两个显而易见的疑问，第一LinkedHashMap的节点类型是内部类LinkedHashMap.Entry而非HashMap.Node，LinkedHashMap内部的Entry节点是如何初始化出来的；第二LinkedHashMap没有重写put/putAll方法，是通过什么方式维护双向链表的；
 

第一个问题，LinkedHashMap内部的Entry节点是如何实例化出来的。在之前讲HashMap的文章中，我们讲过在putVal方法中，通过调用newNode方法，构建一个待插入的Node对象，而LinkedHashMap重写了newNode方法，构建一个带插入的LinkedHashMap.Entry对象。在HashMap类中，newNode方法被putVal方法调用，而putVal方法会在put及putAll方法中调用，所以当LinkedHashMap对象调用put或putAll方法时，就能保证插入的节点是LinkedHashMap.Entry对象。
 

第二个问题，LinkedHashMap对象在调用put或putAll方法后，是如何保证双向链表顺序的。LinkedHashMap.newNode方法中，调用了一个linkNodeLast的linkNodeLast方法，新节点链接在内部双向链表的尾部。下面结合源码来看一下：
 

public V put(K key, V value) {
    // 对key的hashCode()做hash
    return putVal(hash(key), key, value, false, true);

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 1：tab为空则创建
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 2：计算index，并对null做处理 
    if ((p = tab[i = (n - 1) & hash]) == null) 
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 3：节点key存在，直接覆盖value
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 4：判断该链为红黑树
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 5：该链为链表
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key,value,null);
                     //链表长度大于8转换为红黑树进行处理
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st  
                        treeifyBin(tab, hash);
                    break;
                 // key已经存在直接覆盖value
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k)))) 
                           break;
                p = e;
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
    ++modCount;
    // 6：超过最大容量 就扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;

上面是HashMap的put方法，在putVal方法中，如果需要插入节点，则调用newNode方法生成待插入的节点对象。LinkedHashMap类中重写的newNode如下：
 

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    //调用LinkedHashMap.Entry的构造函数，生成Entry节点
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    //调整双向链表结构，是新插入的节点p插入到双向链表尾部
    linkNodeLast(p);
    return p;
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    //tail指针移到p节点
    tail = p;
    //如果插入p节点之前链表为null，则讲head指针指向新插入的节点p
    if (last == null)
        head = p;
    else {
        //讲新插入的节点p插入到双向链表尾部
        p.before = last;
        last.after = p;

这就是为什么调用HashMap的put/putAll方法，可以生成LinkedHashMap.Entry类型的节点插入，同时可以维护双向链表顺序的原因，如下图所示：
 

 下面看一下HashMap类putVal方法两个比较“别致”的方法afterNodeAccess和afterNodeInsertion。这两个方法是钩子方法，在HashMap中并没有具体实现，只是一个空方法，LinkedHashMap中重写了这两个方法。
 

  • afterNodeAccess：负责当LinkedHashMap按访问有序时，节点被访问后，调整双向链表结构，讲最新访问的节点移动到双向链表的尾部。
  • afterNodeInsertion：负责在插入节点后检查是否需要清除最老的节点(就是上文讲的实现LRU)
 

LinkedHashMap中afterNodeAccess实现如下：
 

void afterNodeAccess(Node<K,V> e) {
    LinkedHashMap.Entry<K,V> last;
    //如果LinkedHashMap按访问有序，并且刚被访问的节点e不是双向链表尾节点，则调整双向链表
    if (accessOrder && (last = tail) != e) {
        //p为刚被访问的节点，b为p的前驱节点，a为p的后继节点
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        //首先将p的后继指针断开
        p.after = null;
        //如果p为双向链表头结点，则将head指针指向p的后继节点a
        if (b == null)
            head = a;
            //如果p不是双向链表头结点，则将p的前驱节点的后继指针指向p的后继节点a
            b.after = a;
        //如果p的后继节点a不为null，则将a的前驱指针指向p的前驱节点b
        if (a != null)
            a.before = b;
            last = b;
        if (last == null)
            head = p;
        else {
            //将p节点连接到双向链表尾部
            p.before = last;
            last.after = p;
        tail = p;
        ++modCount;


 afterNodeAccess除了在HashMap类的put方法中调用外，在replace、merge、compute方法中也有调用，保证按访问有序情况下，最后被访问的节点会被移到双向链表尾部。
 

LinkedHashMap中afterNodeInsertion实现如下：
 

void afterNodeInsertion(boolean evict) {
    LinkedHashMap.Entry<K,V> first;
    //如果evit为tur(需要删除最老元素)，并且双向链表不为null，并且removeEldestEntry方法返回true
    //则清除head指向的节点(最老的节点)
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);

这里回头看一下本文开头讲的LRUCache类，重写了removeEldestEntry方法，因为LinkedHashMap中默认返回false，如下：
 

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;

如果想要实现LRU，子类中要重写该方法。
 

3.4 remove操作
 

LinkedHashMap也没有重写remove()方法，remove操作是通过调用HashMap的remove方法实现的，根据上节讲的LinkedHashMap要维护双向链表，那么是不是HashMap的remove方法中定义了钩子方法，然后在LinkedHashMap中实现，删除双向链表中的相应节点，答案是肯定的。
 

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    p = e;
                } while ((e = e.next) != null);
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                tab[index] = node.next;
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
    return null;

afterNodeRemoval就是钩子方法，LinkedHashMap中实现如下：
 
* LinkedHashMap删除节点后，将节点从双向链表中移除
void afterNodeRemoval(Node<K,V> e) {
    //当前删除的节点是p，b是删除节点的前驱节点，a是删除节点的后继节点1
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    //首先将p的前驱指针和后继指针清空
    p.before = p.after = null;
    //如果p为双向链表头结点，则直接将head指针指向p的后继节点a
    if (b == null)
        head = a;
    //如果p不是双向链表头结点，则将p的前驱节点的后继指针指向p的后继节点a
        b.after = a;
    //如果p为双向链表尾节点，则直接将tail指针指向p的前驱节点b
    if (a == null)
        tail = b;
    //如果p不是双向链表的尾节点，则将p的后继节点的前驱指针指向p的前驱节点b
        a.before = b;

 也就是讲当LinkedHashMap删除节点，是通过调用HashMap的remove方法实现的，在HashMap删除节点后，会调用afterNodeRemoval方法，该方法在LinkedHashMap中实现，讲待删除节点从双向链表中移除。
 

3.5 get方法
 

LinkedHashMap中重写了HashMap的get方法，如果LinkedHashMap按访问有序，则在访问后会调用上面讲的afterNodeAccess方法，调整双向链表结构。实现如下：
 

public V get(Object key) {
    Node<K,V> e;
    //调用HashMap的getNode方法，获取key对应的Node节点
    if ((e = getNode(hash(key), key)) == null)
        return null;
    //如果LinkedHashMap按访问有序，则将刚访问的节点e，移动到双向链表的尾部
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;

同样，getOrDefault的实现思想也是一样的，如下：
 

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;

其实对比HashMap的实现，可以发现，LinkedHashMap其实就是比HashMap多了个如果按访问有序，则维护双向链表的逻辑。
 

3.6 containsKey方法
 

LinkedHashMap中没有重写containsKey方法，完全复用HashMap的containsKey方法，因为判断key是否存在，不涉及双向链表的维护，且HashMap的containsKey方法的时间复杂度为O(1)，效率较高，没必要重写。
 

3.7 containsValue方法
 

HashMap中判断value是否存在，是通过遍历hash桶数组的每个元素，然后依次判断链表/红黑树中是否存在相等的value得到的，如下：
 

public boolean containsValue(Object value) {
    Node<K,V>[] tab; V v;
    if ((tab = table) != null && size > 0) {
        for (int i = 0; i < tab.length; ++i) {
            for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                if ((v = e.value) == value ||
                    (value != null && value.equals(v)))
                    return true;
    return false;

两层for循环，时间复杂度应该在O(n) ~ O(n^2)之间。虽然判断value在Map中是否存在也不涉及双向链表的改变，但LinkedHashMap依然没有采用这种方式，因为LinkedHashMap内部维护了一个双向链表，直接通过双向链表访问HashMap所有节点，依次判断即可，时间复杂度为O(n)。LinkedHashMap中重写的containsValue方法如下：
 

public boolean containsValue(Object value) {
    //遍历双向链表，判断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;

4. LinkedHashMap特点
 

  • LinkedHashMap是基于HashMap实现的，除了HashMap键值对之间无序这一特点之外的特点，LinkedHashMap都有
  • LinkedHashMap可以保证插入有序或访问有序，访问有序可以很方便地实现LRU算法
 
 
参考链接：
 
 
  1. Java API源码
  2. 《Java编程的逻辑》
 
1、继承扩展HashMap，实现Map接口，基于双链表实现有序，支持插入有序和访问顺序
2、允许NULL元素，基本操作(add、contrains、remove)与HashMap一样有稳定性能（hash分布均匀情况下）
3、由于需要维护链表，性能较HashMap差，而迭代可能不一定，LinkedHashMap的迭代所需时间与 大小 成比例，HashMap迭代所需时间与 容量 成比例...
源码基于jdk 1.7.81
LinkedHashMap 继承自 HashMap，实现了 Map 接口，所以它具有 Map 的所有方法和特性，同时 LinkedHashMap 继承了 HashMap 所有非私有的成员变量方法。
public class LinkedHashMap&lt;K,V&gt; extends HashMap&lt;K,V&g...
在Map集合框架中，除了HashMap以外，TreeMap也是我们工作中常用到的集合对象之一。
与HashMap相比，TreeMap是一个能比较元素大小的Map集合，会对传入的key进行了大小排序。其中，可以使用元素的自然顺序，也可以使用集合中自定义的比较器来进行排序；
不同于HashMap的哈希映射，TreeMap底层实现了树形结构，至于具体形态，你可以简单的理解为一颗倒过来的树---根在上--叶在下。如果用计算机术语来说的话，TreeMap实现了红黑树的结..
				
LinkedHashMap是基于HashMap实现的一种集合，具有HashMap 集合的所有特点，除了 HashMap 无序的特点，LinkedHashMap 是有序的。
#include<iostream
import java.util.LinkedHashMap;
Map<Integer,Integer>mp = new LinkedHashMap<Integer, Integer>();
mp.put(key,value);
				
我们总说哈希表（HashMap）是以O（1）的时间插入，然后遍历时是无序的，也就是说，hash过后就不一定插在了数组什么位置了。这样导致我们无法保证获取到的键顺序。
但是LinkedHashMap就不一样，按照我们的理解，里面应该还有一个线性结构，来保存HashMap的插入顺序，以至于遍历时能够获得按插入顺序得到的顺序。
接下来我们就分析一下它的源码。
public class Linke...

				
LinkedHashMap是HashMap的子类，但内部还有一个双向链表维护键值对的顺序，每个键值对既位于哈希表中，也位于这个双向链表中。LinkedHashMap支持两种顺序：一种是插入顺序；另外一种是访问顺序。
插入顺序容易理解，先添加的在前面，后添加的在后面，修改操作不影响顺序。
        LinkedHashMap<String, Integer> seqMap = new LinkedHashMap<>();
        seqMap.put(

                    一行代码能搞定的事情，没必要写个工具类
// List<Shop>转换为List<ShopQueryDto> 
        List<Shop> shopList= getXxxList(shop);
        List<ShopQueryDto> list = shopList.stream().map(x -> dozer.map(x,ShopQueryDto.class)).collect(Collectors.toList());
                Spring Boot + Mybatis数据源配置的三种方式
                    Sharon~: 
                    同问3.3@Import注解是必须加的吗？
                golang websocket编程
                    Nihility/: 
                    能跑起来吗
                Spring Boot + Mybatis数据源配置的三种方式
                    征途黯然.: 
                    感谢博主，你的文章让我得到一些收获！(￣ˇ￣)
 
推荐文章
豪气的毛豆  ·  Get started: Install and Run MMSeg — MMSegmentation 1.2.2 documentation
2 月前
自信的凳子  ·  什么是公钥和私钥？ - 数字证书管理服务 - 阿里云
2 月前
文雅的登山鞋  ·  【星空体育】(中国)股份有限公司官网
5 月前
挂过科的机器猫  ·  余杭如何聚焦补齐教育、医疗等公共服务？公共服务配套设施什么时候完善？-杭州新闻中心-杭州网
5 月前
高大的日光灯  ·  发展成果_华润集团欢迎您
7 月前
Link管理   ·   51好读   ·   Sov5搜索   ·   小百科
link管理 - 链接快照平台