乐趣区

关于java:你真的了解LinkedHashMap吗

一、前言

LinkedHashMap 继承于 HashMap,因而,倡议在学习本篇内容前,先学习 HashMap 系列,这样使得更加容易了解。

HashMap 系列

(一)HashMap 系列:负载因子 0.75

(二)HashMap 系列:树化阀值 8,进化阀值 6

(三)HashMap 系列:2 次方扩容

(四)HashMap 系列:put 元素(不看完将悔恨毕生!)

二、LinkedHashMap 应用

可能很多人会说,LinkedHashMap 谁不会用?你真的确定你会用?

上例子之前,先写几个工具办法,以便前面了解不便:

public class Main {
    // 字符串左对齐(未思考中英文长度,仅便于观看)private static String spaceFill(Object object) {return String.format("%-20s", object);
    }

    // 反射获取 HashMap 中的数组对象
    // 啥?你不晓得数组对象名称?// 倡议去看看源码,或是看看我写的 HashMap 系列
    private static Map.Entry<Integer, String>[] getArray(Object object, Field field) throws Exception {return (Map.Entry<Integer, String>[]) field.get(object);
    }

    // 反射获取 Map.Entry
    // 因为 HashMap.Node 是公有动态类
    private static Map.Entry<Integer, String> getObject(Object object, String name) throws Exception {Field field = getField(object.getClass(), name);
        return (Map.Entry<Integer, String>) field.get(object);
    }

    // 反射获取指定字段
    private static Field getField(Class<?> clazz, String name) {if (clazz == null) {return null;}

        Field field = null;
        try {field = clazz.getDeclaredField(name);
            field.setAccessible(true);

        } catch (NoSuchFieldException e) {field = getField(clazz.getSuperclass(), name);
        }
        return field;
    }
}
复制代码

好了,下面的工具办法曾经实现,前面的所有例子都会应用下面的办法。

咱们来看两个例子:

2.1、例子一

public class Main {public static void main(String[] args) {
        // 个别大家都应用默认构造函数
        LinkedHashMap<Integer, String> map = new LinkedHashMap<>();
        map.put(1, "chris");
        map.put(2, "qingye");
        map.put(3, "24854015@qq.com");

        // 反射获取 table 数组对象
        Field field = getField(map.getClass(), "table");
        if (field != null && field.getType().isArray()) {
            try {
                // 类型强转
                Map.Entry<Integer, String>[] table = getArray(map, field);
                for (int i = 0; i < table.length; i ++) {if (table[i] != null) {
                        // LinkedHashMap.Node 特有的 before & after 指针
                        Map.Entry<Integer, String> before = getObject(table[i], "before");
                        Map.Entry<Integer, String> after = getObject(table[i], "after");

                        if (before == null) {System.out.print("This is Head");
                        } else if (after == null) {System.out.print("This is Tail");
                        } else {System.out.print("ttt");
                        }
                        System.out.println("[" + i + "] =>" + spaceFill(table[i]) + ", before =>" + spaceFill(before) + ", after =>" + spaceFill(after));
                    }
                }

            } catch (Exception e) {}}
    }
}
复制代码

输入后果:

This is Head [1] => 1=chris             , before => null                , after => 2=qingye            
             [2] => 2=qingye            , before => 1=chris             , after => 3=24854015@qq.com   
This is Tail [3] => 3=24854015@qq.com   , before => 2=qingye            , after => null   
复制代码

2.2、例子二

public class Main {public static void main(String[] args) {
        // 指定构造函数来初始化
        LinkedHashMap<Integer, String> map = new LinkedHashMap<>(16, 0.75f, true);
        map.put(1, "chris");
        map.put(2, "qingye");
        map.put(3, "24854015@qq.com");
        map.get(1); // 留神:这里仅仅 get 了一下

        Field field = getField(map.getClass(), "table");
        if (field != null && field.getType().isArray()) {
            try {Map.Entry<Integer, String>[] table = getArray(map, field);
                for (int i = 0; i < table.length; i ++) {if (table[i] != null) {Map.Entry<Integer, String> before = getObject(table[i], "before");
                        Map.Entry<Integer, String> after = getObject(table[i], "after");

                        if (before == null) {System.out.print("This is Head");
                        } else if (after == null) {System.out.print("This is Tail");
                        } else {System.out.print("ttt");
                        }
                        System.out.println("[" + i + "] =>" + spaceFill(table[i]) + ", before =>" + spaceFill(before) + ", after =>" + spaceFill(after));
                    }
                }

            } catch (Exception e) {}}
    }
}
复制代码

输入后果:

This is Tail [1] => 1=chris             , before => 3=24854015@qq.com   , after => null                
This is Head [2] => 2=qingye            , before => null                , after => 3=24854015@qq.com   
             [3] => 3=24854015@qq.com   , before => 2=qingye            , after => 1=chris   
复制代码

WTF?!产生了啥?怎么 [1] 元素从『Head』变成了『Tail』?这就是 LinkedHashMap 的其妙之处!

三、深刻解读 LinkedHashMap 的神秘

3.1、LinkedHashMap 与 HashMap 的关系

本篇结尾也说了,前者继承于后者,因而,LinkedHashMap 的 putXXX 和 getXXX 都间接继承于 HashMap,并没有重载,其 put & get 的逻辑也就和 HashMap 一样。HashMap 的 put & get 是啥逻辑?如果大家遗记了,倡议去看看我写的(四)HashMap 系列:put 元素(不看完将悔恨毕生!)。既然是继承,同样的,它们的数组构造也就简直统一(99% 的统一):

数据结构:数组 + 链表 <—> 红黑树

那 1% 的不统一在哪?

3.2、Map.Entry

HashMap 的节点实现了 Map.Entry:

public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {
    
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
    
        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
       }
       
}
复制代码

那 LinkedHashMap 的节点呢?

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {
    
    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);
        }
    }
    
}
复制代码

额,真是简略的令人发指啊!仅仅多了两个索引(指针)节点:before & after!

3.3、HashMap.TreeNode

之前再讲 HashMap 时,并没有提到 TreeNode 这个类型,因为波及到 LinkedHashMap,所以有所调整,这里进行补充:

public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {
    
    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
        TreeNode(int hash, K key, V val, Node<K,V> next) {super(hash, key, val, next);
       }
        
}
复制代码

完满的继承:

3.4、before & after

依据这两个字段的名称,咱们就能很容易的猜测出,别离指向前一个节点和后一个节点(事实上,咱们结尾的两个例子,曾经证实了这种关系),那么,具体是如何在数据结构或者说,节点对象上体现出关联关系的呢?

画图很辛苦 …… LinkedHashMap 之所以加了 before 与 after 节点索引,次要目标:

  • 双向链表(即能够双向拜访),从头结点能够始终遍历到最初一个节点,而不须要中途定位到桶;
  • 能够依照插入程序来拜访(默认),【例子一】;

四、LinkedHashMap 非凡之处

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

该字段含意:

  • true 时,遍历双向链表中元素是依照拜访程序来遍历(LRU);
  • false 时,遍历双向链表中的元素是依照插入程序来遍历(默认);

Android 零碎中的 LRU 的实现,其实就是基于 LinkedHashMap,并采纳了【例子二】的形式来初始化对象实例。

五、LinkedHashMap 索引的源码实现

咱们同样从 put 元素还是剖析源码,还记得咱们剖析 HashMap 的 putVal 时,有两个空函数么?

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        ......
        else {
            ......
            if (e != null) { // 元素曾经存在
                ......
                afterNodeAccess(e); // 调整节点程序
                return oldValue;
            }
        }
        ......
        afterNodeInsertion(evict); // 新增元素,调整节点程序
        return null;
    }
}
复制代码

5.1、LinkedHashMap.afterNodeAccess

该办法会被多个其它办法触发,例如:put 一个已存在的节点对象,get 对象,replace 对象等等,该办法就是判断是否须要调整的遍历拜访程序。

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMap.Entry<K,V> last;
        
        // accessOrder = true,示意 LRU
        // 将要挪动的节点曾经在最初一个,那么就不必调整了
        if (accessOrder && (last = tail) != e) {
            // p 指向 e 自身,b 指向 e 前一个,a 指向 e 后一个
            LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
            p.after = null;
            
            // 如果 e 的前一个为 null,示意 e 是头节点,那么将头节点指向 e 的下一个元素
            if (b == null)
                head = a;
            else
                b.after = a; // 否则 e 的上一个元素,其下一个指向从 e 改为 e 的下一个
            
            // a 为 null 则示意 e 是尾节点
            // 否则将 e 的下一个元素,其上一个指向从 e 改为 e 的上一个
            if (a != null)
                a.before = b;
            else
                last = b; // 否则,尾节点指向 e 的上一个元素
                
            // 总之,下面判断:b,a 不为 null,则互指 
            
            // 如果 last 为 null,则示意整个 LinkedHashMap 只有一个元素
            if (last == null)
                head = p;
            else {
                // 否则,将 p 移至最初一个(拜访程序上,即逻辑上最初一个,理论地位不会变)p.before = last;
                last.after = p;
            }
            tail = p; // 最初,尾指向最初一个元素
            ++modCount;
        }
    }
}
复制代码

5.2、LinkedHashMap.afterNodeInsertion

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {
    // 新增节点后,调用此办法判断是否须要移除最老的节点
    // 因为 accessOrder = true 时,拜访次数多的节点肯定是在链尾,而拜访次数起码的则在链头
    void afterNodeInsertion(boolean evict) { // possibly remove eldest
        LinkedHashMap.Entry<K,V> first;
        if (evict && (first = head) != null && removeEldestEntry(first)) {
            K key = first.key;
             // 如果须要移除最老的,则先从链头开始移除
             // 移除节点,调用的是 HashMap.removeNode 办法
            // 同样是从数组开始,再红黑树,再链表查找,删除,调整
            removeNode(hash(key), key, null, false, true);
        }
    }
}
复制代码

5.3、LinkedHashMap.removeEldestEntry

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {
    // 该办法在 LinkedHashMap 中,默认返回 false,即不移除最老的元素
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {return false;}
}
复制代码

那为啥我还始终提到 LRU 呢?因为,咱们如果本人基于 LinkedHashMap 来实现 LRU,就能够重载此办法,返回 true,这样就达到了 LRU 的成果。

好了,LinkedHashMap 就聊到这里!

参考:《2020 最新 Java 根底精讲视频教程和学习路线!》

链接:https://juejin.cn/post/692396…

退出移动版