Java源码系列3——LinkedHashMap

Java源码系列3——LinkedHashMap


title: Java源码系列3——LinkedHashMap
date: 2020-02-16 19:25:24
updated: 2020-02-16 19:25:24
tags:

  • Java
  • Java源码系列

什么是LinkedHashMap?

LinkedHashMapHashMap 的有序实现。LinkedHashMap 用一条双向链表来维护顺序,迭代的时候也使用自己实现的迭代器。

public static void main(String[] args) {
    HashMap<String, Integer> h = new HashMap<>(33);
    h.put("one", 1);
    h.put("two", 2);
    h.put("three", 3);
    h.put("four", 4);
    for (String key : h.keySet()) {
        System.out.println("key:" + key + "value:" + h.get(key));
    }

    LinkedHashMap<String, Integer> lh = new LinkedHashMap<>(33);
    lh.put("one", 1);
    lh.put("two", 2);
    lh.put("three", 3);
    lh.put("four", 4);
    for (String key : lh.keySet()) {
        System.out.println("key:" + key + "value:" + lh.get(key));
    }
}

输出

key:twovalue:2
key:threevalue:3
key:fourvalue:4
key:onevalue:1

key:onevalue:1
key:twovalue:2
key:threevalue:3
key:fourvalue:4

底层数组结构

HashMap的底层是由数组,链表,红黑树组成的。数组用来存储节点,当出现哈希碰撞时使用链表存储,当链表超过一定长度后会优化成红黑树。

LinkedHashMap 的底层除了继承自 HashMap 的数组,链表,红黑树,还多了链接所有节点的双向链表(图中红色和绿色箭头),用于存储各个节点的顺序。

Entry的继承关系

LinkedHashMap.Entry 继承了 HashMap.Node,多维护了 before 和 after 两个指针,这两个属性指向该Entry的前一个Entry和后一个Entry,也就是那条用于存储顺序的双向链表。

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

但是 LinkedHashMap 中确没有覆写 HashMap 中 TreeNode 的代码,那红黑树中各个节点的顺序是如何存储的。

我们可以从 HashMap.TreeNode 的继承关系中找出端倪:

呦吼,这一小家子也真够乱的,子类继承了父类的内部类,父类的内部类又继承了子类的内部类,上演一出鸡生蛋,蛋生鸡的戏码。

// 继承了 LinkedHashMap.Entry
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);
    }
}

为什么 HashMap.TreeNode 要继承 LinkedHashMap.Entry,继承过来的 before 和 after 指针在 HashMap 中也没有被用到,何不直接继承 HashMap.Node

这样的继承关系其实并不是为 HashMap 设计的,在 HashMap 中确实没什么用。但在 LinkedHashMap 中,就可以直接使用继承过来的 HashMap.TreeNode,因为 TreeNode 这个类通过继承已经拥有了 before 和 after 指针。

这就是为什么,LinkedHashMap 中有一个继承了 HashMap.Node 的内部类,却没有继承 HashMap.TreeNode 的内部类。

链表的创建过程

链表的创建过程是在第一个元素插入的时候才开始的,一开始链表的头部(head)和尾巴(tail)都为null。

LinkedHashMap 没有覆写父类的put方法,元素的插入流程基本相同,只是 HashMap 插入的是 Node 类型的节点,LinkedHashMap 插入的是 Entry 类型的节点,并且更新链表。

那么 LinkedHashMap 是怎么插入节点,并且更新链表的呢?

// HashMap 中实现
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

// HashMap 中实现
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 桶为空时初始化桶
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 取模得到节点在桶中的索引位置,并且该位置没有元素,直接插入
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 哈希碰撞了,本节不介绍,可以看上一篇讲 HashMap 的文章
    else {
        // ... 省略部分代码
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

// HashMap 中实现的 newNode
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
    return new Node<>(hash, key, value, next);
}

// LinkedHashMap 中覆写的 newNode
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    linkNodeLast(p);
    return p;
}

// LinkedHashMap 中实现
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    // 如果链表为空,头部和尾部都赋值为p
    if (last == null)
        head = p;
    // 把新插入的节点放在链表尾部
    else {
        p.before = last;
        last.after = p;
    }
}

从代码里可以很明显的看出,LinkedHashMap 中索引的计算,桶的赋值,哈希碰撞时链表或者红黑树的创建,都使用的 HashMap 的实现。LinkedHashMap 只需要覆写节点的创建,并且在创建节点的时候,更新储存顺序的链表。真的是把复用利用到了极致。

节点的删除

与插入操作一样,LinkedHashMap 也是使用的父类的删除操作,然后覆写了回调方法 afterNodeRemoval,用于维护双向链表。

// HashMap 中实现
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 (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;
            else
                p.next = node.next;
            ++modCount;
            --size;
            // 删除后回调
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

// LinkedHashMap 中覆写
void afterNodeRemoval(Node<K,V> e) { // unlink
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    p.before = p.after = null;
    // 如果b为空,则为头节点
    if (b == null)
        head = a;
    else
        b.after = a;
    // 如果a为空,则为尾节点
    if (a == null)
        tail = b;
    else
        a.before = b;
}

访问顺序的维护

如果我们在初始化 LinkedHashMap 时,把 accessOrder 参数设为 true,那么我们不仅在插入的时候会维护链表,在访问节点的时候也会维护链表。

当我们调用 get, getOrDefault, replace 等方法时,会更新链表,把访问的节点移动到链表尾部。

// LinkedHashMap 中覆写
public V get(Object key) {
    Node<K,V> e;
    // 调用了 HashMap 中的 getNode 方法
    if ((e = getNode(hash(key), key)) == null)
        return null;
    // 如果accessOrder为true,调用afterNodeAccess
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

// LinkedHashMap 中覆写
void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    // 如果本来就在尾部,就不需要更新
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.after = null;
        // 如果b为空,则为头部
        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
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

使用测试代码体验一下效果

public static void main(String[] args) {
    LinkedHashMap<String, Integer> lh = new LinkedHashMap<>(33, 0.75f, true);
    lh.put("one", 1);
    lh.put("two", 2);
    lh.put("three", 3);
    lh.put("four", 4);
    lh.get("two");
    for (String key : lh.keySet()) {
        System.out.println("key:" + key + "value:" + lh.get(key));
    }
}

竟然报错了

看一下 LinkedHashMap 覆写的迭代器代码

final LinkedHashMap.Entry<K,V> nextNode() {
    LinkedHashMap.Entry<K,V> e = next;
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    if (e == null)
        throw new NoSuchElementException();
    current = e;
    next = e.after;
    return e;
}

ConcurrentModificationException 这个报错是为了防止并发条件下,遍历的同时链表发生变化。因为我们在遍历的时候又调用了 get 方法,导致链表发生变化,才会抛这个错。

accessOrder 为 true 时的正确遍历姿势如下,使用 LinkedHashMap 覆写forEach 方法,就不会在读取值的时候修改顺序链表了。

lh.forEach((String k, Integer v) -> {
    System.out.println("key:" + k + ", value:" + v);
});

使用 LinkedHashMap 实现简单的 LRU

LRU 全称 Least Recently Used,也就是最近最少使用的意思,是一种内存管理算法,该算法最早应用于 Linux 操作系统。

这个算法基于一种假设:长期不被使用的数据,在未来被用到的几率也不大。因此,当数据所占内存达到一定阈值时,我们要移除最近最少被使用的数据。

下面我们介绍一下前置知识。

afterNodeInsertion 是一个回调方法,在插入元素的时候回调。LinkedHashMap 覆写了这个方法,主要用来判断是否需要将链表的 head 移除。

// LinkedHashMap 中覆写
void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    // 根据条件判断是否移除链表的head节点
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

// LinkedHashMap 中实现,默认返回false
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

下面我们将继承 LinkedHashMap,通过覆写 removeEldestEntry,达到当 Map 的节点个数超过指定阈值时,删除最少访问的节点。从而实现 LRU 缓存策略。

public class SimpleCache<K, V> extends LinkedHashMap<K, V> {

    private static final int MAX_NODE_NUM = 100;

    private int limit;

    public SimpleCache(){
        this(MAX_NODE_NUM);
    }

    public SimpleCache(int limit) {
        super(limit, 0.75f, true);
        this.limit = limit;
    }

    /**
     * 判断节点数是否超出限制
     * @param eldest
     * @return boolean
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > limit;
    }

    /**
     * 测试
     */
    public static void main(String[] args) {
        SimpleCache<Integer, Integer> cache = new SimpleCache<>(3);

        for (int i = 0; i < 10; i++) {
            cache.put(i, i * i);
        }

        System.out.println("插入10个键值对后,缓存内容:");
        System.out.println(cache);

        System.out.println("访问键值为7的节点后,缓存的内容:");
        cache.get(7);
        System.out.println(cache);

        System.out.println("插入键值为1的键值对后,缓存的内容:");
        cache.put(1, 1);
        System.out.println(cache);
    }
}

测试结果如下:

总结

本文围绕 LinkedHashMap 如何维护存储顺序的双向链表展开,介绍了 LinkedHashMap 和 HashMap 节点类的继承关系,介绍了新增,删除,访问时,LinkedHashMap 如何在复用 HashMap 的同时,维护双向链表。最后通过继承 LinkedHashMap 很简单的实现了 LRU 缓存策略。

全文的代码量较多,但都较为好理解。理解JDK的设计思路,探寻背后的实现原理,也是一件很有趣的事。

本文讨论的源代码都基于JDK1.8版本。

参考资料

LinkedHashMap 源码详细分析(JDK1.8)

【Java入门提高篇】Day28 Java容器类详解(十)LinkedHashMap详解

源码系列文章

Java源码系列1——ArrayList

Java源码系列2——HashMap

Java源码系列3——LinkedHashMap

本文首发于我的个人博客 https://chaohang.top

作者张小超

转载请注明出处

欢迎关注我的微信公众号 【超超不会飞】,获取第一时间的更新。

发表评论

电子邮件地址不会被公开。 必填项已用*标注