网站公告

本次更新：没啥更新的

“钱塘江上潮信起，今日方知我是我”

朕知道了
Noctiflorous Garden

外观

LinkedHashMap(附源码) ​

字数: 0 字 时长: 0 分钟

假如我们需要一个按照插入顺序来排列的键值对集合，那 HashMap 就无能为力了，这时候就要用到 LinkedHashMap。

为了提高查找效率，HashMap 在插入的时候会对键进行哈希计算，这也导致 HashMap 本身并不能保证元素的插入顺序。

那怎么保证键值对的插入顺序呢？

LinkedHashMap 就是为这个需求应运而生的。

LinkedHashMap 继承了 HashMap，所以 HashMap 有的关于键值对的功能，它也有。

java
public class LinkedHashMap<K, V>
        extends HashMap<K, V>
        implements Map<K, V> {
}

在此基础上，LinkedHashMap 内部追加了双向链表，用来维护元素的顺序。

注意下面代码中的：

text
before

after

它们就是用来维护当前元素的前一个元素和后一个元素的。

java
static class Entry<K, V>
        extends HashMap.Node<K, V> {

    Entry<K, V> before;
    Entry<K, V> after;

    Entry(
            int hash,
            K key,
            V value,
            Node<K, V> next) {

        super(
                hash,
                key,
                value,
                next
        );
    }
}

用 LinkedHashMap 替换 HashMap，就可以做到有序插入。

1. 插入顺序 ​

在 HashMap 中，null 会插入到 HashMap 的第一位。

java
Map<String, String> hashMap =
        new HashMap<>();

hashMap.put(
        "张",
        "张无忌"
);

hashMap.put(
        "赵",
        "赵敏"
);

hashMap.put(
        "韦",
        "韦一笑"
);

hashMap.put(
        "灭",
        "灭绝师太"
);

hashMap.put(
        null,
        null
);

for (
        String key :
                hashMap.keySet()
) {

    System.out.println(
            key
                    + " : "
                    + hashMap.get(key)
    );
}

输出结果：

text
null : null
张 : 张无忌
赵 : 赵敏
韦 : 韦一笑
灭 : 灭绝师太

虽然：

text
null

是最后一个 put() 进去的，但遍历输出时却跑到了第一位。

再对比一下 LinkedHashMap：

java
public static void main(
        String[] args) {

    Map<String, String> linkedHashMap =
            new LinkedHashMap<>();

    linkedHashMap.put(
            "张",
            "张无忌"
    );

    linkedHashMap.put(
            "赵",
            "赵敏"
    );

    linkedHashMap.put(
            "韦",
            "韦一笑"
    );

    linkedHashMap.put(
            "灭",
            "灭绝师太"
    );

    linkedHashMap.put(
            null,
            null
    );

    for (
            String key :
                    linkedHashMap.keySet()
    ) {

        System.out.println(
                key
                        + " : "
                        + linkedHashMap.get(key)
        );
    }
}

输出结果：

text
张 : 张无忌
赵 : 赵敏
韦 : 韦一笑
灭 : 灭绝师太
null : null

null 在最后一位插入，也在最后一位输出。

输出结果可以再次证明：

HashMap 是无序的，LinkedHashMap 可以维持插入顺序。

那 LinkedHashMap 是如何做到这一点的？

要想搞清楚，就需要深入研究一下 LinkedHashMap 的源码。

LinkedHashMap 并没有重写 HashMap 的 put() 方法，而是重写了 put() 方法需要调用的内部方法：

java
newNode()

这是 HashMap 的：

java
Node<K, V> newNode(
        int hash,
        K key,
        V value,
        Node<K, V> next) {

    return new Node<>(
            hash,
            key,
            value,
            next
    );
}

这是 LinkedHashMap 的：

java
HashMap.Node<K, V> newNode(
        int hash,
        K key,
        V value,
        HashMap.Node<K, V> e) {

    LinkedHashMap.Entry<K, V> p =
            new LinkedHashMap.Entry<>(
                    hash,
                    key,
                    value,
                    e
            );

    linkNodeLast(p);

    return p;
}

LinkedHashMap.Entry 继承了：

java
HashMap.Node

并且追加了两个字段：

text
before

after

用来维持键值对之间的关系。

java
static class Entry<K, V>
        extends HashMap.Node<K, V> {

    Entry<K, V> before;
    Entry<K, V> after;

    Entry(
            int hash,
            K key,
            V value,
            Node<K, V> next) {

        super(
                hash,
                key,
                value,
                next
        );
    }
}

在 LinkedHashMap 中，链表中的节点顺序按照插入顺序维护。

当使用 put() 方法向 LinkedHashMap 中添加键值对时，会把新节点插入到链表尾部，并更新：

text
before

after

从而保证链表的顺序关系。

这个过程由：

java
linkNodeLast()

完成。

java
/**
 * 将指定节点插入到链表的尾部
 *
 * @param p 要插入的节点
 */
private void linkNodeLast(
        LinkedHashMap.Entry<K, V> p) {

    // 获取链表的尾节点
    LinkedHashMap.Entry<K, V> last =
            tail;

    // 将 p 设置为新的尾节点
    tail =
            p;

    // 如果链表为空
    if (last == null) {

        // p 同时也是头节点
        head =
                p;

    } else {

        // p 的前驱指向原来的尾节点
        p.before =
                last;

        // 原尾节点的后继指向 p
        last.after =
                p;
    }
}

LinkedHashMap 添加第一个元素的时候：

text
head
    ↓
第一个元素

等第二个元素添加进来以后：

text
第二个元素.before
    ↓
第一个元素


第一个元素.after
    ↓
第二个元素

这样就保证了键值对按照插入顺序排列。

2. 访问顺序 ​

LinkedHashMap 不仅能够维持插入顺序，还能够维持访问顺序。

访问包括调用：

text
get()

remove()

put()

要维护访问顺序，需要在声明 LinkedHashMap 的时候指定三个参数：

java
LinkedHashMap<String, String> map =
        new LinkedHashMap<>(
                16,
                0.75f,
                true
        );

第一个参数：

text
初始容量

第二个参数：

text
负载因子

第三个参数如果为：

text
true

表示 LinkedHashMap 维护访问顺序。

否则维护插入顺序。

默认值：

text
false

来看一个例子：

java
Map<String, String> linkedHashMap =
        new LinkedHashMap<>(
                16,
                0.75f,
                true
        );

linkedHashMap.put(
        "灭",
        "灭绝师太"
);

linkedHashMap.put(
        "绝",
        "灭绝师太"
);

linkedHashMap.put(
        "师",
        "灭绝师太"
);

linkedHashMap.put(
        "太",
        "灭绝师太"
);

System.out.println(
        linkedHashMap
);

linkedHashMap.get(
        "绝"
);

System.out.println(
        linkedHashMap
);

linkedHashMap.get(
        "师"
);

System.out.println(
        linkedHashMap
);

输出结果：

text
{灭=灭绝师太, 绝=灭绝师太, 师=灭绝师太, 太=灭绝师太}

{灭=灭绝师太, 师=灭绝师太, 太=灭绝师太, 绝=灭绝师太}

{灭=灭绝师太, 太=灭绝师太, 绝=灭绝师太, 师=灭绝师太}

当使用 get() 访问键为：

text
绝

的元素以后：

text
绝=灭绝师太

被移动到了最后。

继续访问键为：

text
师

的元素以后：

text
师=灭绝师太

又被移动到了最后。

此时：

text
绝=灭绝师太

位于倒数第二位。

也就是说：

最不经常访问的元素会逐渐位于链表头部。

这就有意思了。

有意思在哪呢？

3. LRU 缓存 ​

可以使用 LinkedHashMap 来实现：

text
LRU 缓存

LRU 是：

text
Least Recently Used

的缩写，也就是：

text
最近最少使用

它是一种常用的页面置换算法，会优先淘汰最近最久没有使用的数据。

java
/**
 * 自定义 MyLinkedHashMap，继承 LinkedHashMap。
 *
 * 用于实现一个具有固定大小的缓存。
 * 当缓存达到最大容量时，
 * 自动移除最早加入的元素。
 *
 * @param <K> 键的类型
 * @param <V> 值的类型
 */
public class MyLinkedHashMap<K, V>
        extends LinkedHashMap<K, V> {

    // 最大键值对数量
    private static final int MAX_ENTRIES =
            5;

    /**
     * @param initialCapacity 初始容量
     * @param loadFactor      负载因子
     * @param accessOrder     访问顺序
     */
    public MyLinkedHashMap(
            int initialCapacity,
            float loadFactor,
            boolean accessOrder) {

        super(
                initialCapacity,
                loadFactor,
                accessOrder
        );
    }

    /**
     * 判断是否删除最早加入的元素
     *
     * @param eldest 最早加入的元素
     * @return 超过最大容量返回 true
     */
    @Override
    protected boolean removeEldestEntry(
            Map.Entry eldest) {

        return size()
                > MAX_ENTRIES;
    }
}

MyLinkedHashMap 是一个自定义类，它继承了 LinkedHashMap，并且重写：

java
removeEldestEntry()

让 Map 最多保存：

text
5 个元素

超过以后就进行淘汰。

测试一下：

java
MyLinkedHashMap<String, String> map =
        new MyLinkedHashMap<>(
                16,
                0.75f,
                true
        );

map.put(
        "灭",
        "灭绝师太"
);

map.put(
        "绝",
        "灭绝师太"
);

map.put(
        "师",
        "灭绝师太"
);

map.put(
        "太",
        "灭绝师太"
);

map.put(
        "一个固执倔强的老女人",
        "一个固执倔强的老女人"
);

System.out.println(
        map
);

map.put(
        "一个顽固迂腐的老女人",
        "一个顽固迂腐的老女人"
);

System.out.println(
        map
);

map.put(
        "一个爱恨分明的老女人",
        "一个爱恨分明的老女人"
);

System.out.println(
        map
);

输出：

text
{灭=灭绝师太, 绝=灭绝师太, 师=灭绝师太, 太=灭绝师太, 一个固执倔强的老女人=一个固执倔强的老女人}

{绝=灭绝师太, 师=灭绝师太, 太=灭绝师太, 一个固执倔强的老女人=一个固执倔强的老女人, 一个顽固迂腐的老女人=一个顽固迂腐的老女人}

{师=灭绝师太, 太=灭绝师太, 一个固执倔强的老女人=一个固执倔强的老女人, 一个顽固迂腐的老女人=一个顽固迂腐的老女人, 一个爱恨分明的老女人=一个爱恨分明的老女人}

可以看到：

text
灭=灭绝师太

绝=灭绝师太

依次被淘汰出局。

假如在：

text
put("一个爱恨分明的老女人")

之前访问一下键为：

text
绝

的元素：

java
MyLinkedHashMap<String, String> map =
        new MyLinkedHashMap<>(
                16,
                0.75f,
                true
        );

map.put(
        "灭",
        "灭绝师太"
);

map.put(
        "绝",
        "灭绝师太"
);

map.put(
        "师",
        "灭绝师太"
);

map.put(
        "太",
        "灭绝师太"
);

map.put(
        "一个固执倔强的老女人",
        "一个固执倔强的老女人"
);

System.out.println(
        map
);

map.put(
        "一个顽固迂腐的老女人",
        "一个顽固迂腐的老女人"
);

System.out.println(
        map
);

map.get(
        "绝"
);

map.put(
        "一个爱恨分明的老女人",
        "一个爱恨分明的老女人"
);

System.out.println(
        map
);

输出结果就会发生变化：

text
{灭=灭绝师太, 绝=灭绝师太, 师=灭绝师太, 太=灭绝师太, 一个固执倔强的老女人=一个固执倔强的老女人}

{绝=灭绝师太, 师=灭绝师太, 太=灭绝师太, 一个固执倔强的老女人=一个固执倔强的老女人, 一个顽固迂腐的老女人=一个顽固迂腐的老女人}

{太=灭绝师太, 一个固执倔强的老女人=一个固执倔强的老女人, 一个顽固迂腐的老女人=一个顽固迂腐的老女人, 绝=灭绝师太, 一个爱恨分明的老女人=一个爱恨分明的老女人}

这次：

text
灭=灭绝师太

师=灭绝师太

被淘汰出局。

那 LinkedHashMap 是如何维持访问顺序的？

可以研究下面这三个方法：

java
void afterNodeAccess(
        Node<K, V> p) {
}

void afterNodeInsertion(
        boolean evict) {
}

void afterNodeRemoval(
        Node<K, V> p) {
}

afterNodeAccess() 会在调用：

java
get()

的时候被调用。

afterNodeInsertion() 会在调用：

java
put()

的时候被调用。

afterNodeRemoval() 会在调用：

java
remove()

的时候被调用。

以：

java
afterNodeAccess()

为例来看一下。

java
/**
 * 在访问节点后，将节点移动到链表尾部
 *
 * @param e 要移动的节点
 */
void afterNodeAccess(
        HashMap.Node<K, V> e) {

    LinkedHashMap.Entry<K, V> last;

    // 按访问顺序排列，
    // 并且当前访问节点不是尾节点
    if (
            accessOrder
                    && (
                    last = tail
            ) != e
    ) {

        LinkedHashMap.Entry<K, V> p =
                (
                        LinkedHashMap.Entry<K, V>
                ) e;

        LinkedHashMap.Entry<K, V> b =
                p.before;

        LinkedHashMap.Entry<K, V> a =
                p.after;

        // 当前节点准备移动到最后
        p.after =
                null;

        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;
    }
}

为什么 LinkedHashMap 可以实现 LRU 缓存，把最不经常访问的元素淘汰？

插入元素时需要调用：

java
put()

该方法最后会调用：

java
afterNodeInsertion()

这个方法被 LinkedHashMap 重写。

java
/**
 * 在插入节点以后，
 * 根据需要删除最早加入的元素
 *
 * @param evict 是否需要删除最早加入的元素
 */
void afterNodeInsertion(
        boolean evict) {

    LinkedHashMap.Entry<K, V> first;

    if (
            evict
                    && (
                    first = head
            ) != null
                    && removeEldestEntry(
                    first
            )
    ) {

        // 获取要删除元素的 Key
        K key =
                first.key;

        // 删除元素
        removeNode(
                hash(key),
                key,
                null,
                false,
                true
        );
    }
}

removeEldestEntry() 会判断第一个元素是否已经超出了允许容纳的最大范围。

如果超出：

text
removeEldestEntry()
    ↓
返回 true
    ↓
removeNode()
    ↓
删除最不经常访问的元素

4. 小结 ​

由于 LinkedHashMap 需要额外维护：

text
双向链表

所以 LinkedHashMap 在插入、删除操作时，花费的时间会比 HashMap 多一些。

简单总结一下。

HashMap 是一种常用的哈希表数据结构，可以快速进行键值对的：

text
查找

插入

但是 HashMap 本身并不能保证键值对的顺序。

如果需要按照：

text
插入顺序

访问顺序

遍历键值对，就可以使用：

text
LinkedHashMap

LinkedHashMap 继承自 HashMap，并在 HashMap 的基础上增加：

text
双向链表

用来维护键值对的顺序。

链表可以按照：

text
插入顺序

访问顺序

排列。

其中：

text
head
    ↓
最早插入或访问的元素


tail
    ↓
最晚插入或访问的元素

这个链表使 LinkedHashMap 可以保持键值对的顺序，并按照顺序进行遍历。

LinkedHashMap 还可以通过构造方法指定：

text
插入顺序

访问顺序

在按照访问顺序排列的情况下，每次访问一个键值对，都会将该键值对移动到链表尾部，从而保证最近访问的元素位于最后。

如果需要删除最早加入的元素，可以通过重写：

java
removeEldestEntry()

实现。

总之：

LinkedHashMap 通过维护双向链表来保持键值对的顺序，可以按照插入顺序或者访问顺序遍历键值对。

Noctiflorous Garden · MIT License

© 2024 Kerwim · 冀ICP备2024088775号-1 · Built in silence. Running against entropy.