亲宝软件园·资讯

展开

Java LinkedHashMap Java源码解析之LinkedHashMap

不会编程的派大星 人气:0
想了解Java源码解析之LinkedHashMap的相关内容吗,不会编程的派大星在本文为您仔细讲解Java LinkedHashMap的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:Java,LinkedHashMap,Java集合,下面大家一起来学习吧。

一、成员变量

先来看看存储元素的结构吧:

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

这个Entry在HashMap中被引用过,主要是为了能让LinkedHashMap也支持树化。在这里则是用来存储元素。

// 双向链表的头,用作AccessOrder时也是最老的元素
transient LinkedHashMap.Entry<K,V> head;

// 双向链表的尾,用作AccessOrder时也是最新的元素
transient LinkedHashMap.Entry<K,V> tail;

// true则为访问顺序,false则为插入顺序
final boolean accessOrder;

二、构造函数

关于LinkedHashMap的构造函数我们只关注一个,其他的都和HashMap类似,只是把accessOrder设置为了false。在上边的文档说过,initialCapacity并没有在HashMap中那般重要,因为链表不需要像数组那样必须先声明足够的空间。下面这个构造函数是支持访问顺序的。

// 双向链表的头,用作AccessOrder时也是最老的元素
transient LinkedHashMap.Entry<K,V> head;

// 双向链表的尾,用作AccessOrder时也是最新的元素
transient LinkedHashMap.Entry<K,V> tail;

// true则为访问顺序,false则为插入顺序
final boolean accessOrder;

三、重要方法

LinkedHashMap并没有再实现一整套增删改查的方法,而是通过复写HashMap在此过程中定义的几个方法来实现的。对此不熟悉的可以查看上一篇关于HashMap分析的文章,或者对照HashMap的源码来看。

1、插入一个元素

HashMap在插入时,调用了newNode来新建一个节点,或者是通过replacementNode来替换值。在树化时也有两个对应的方法,分别是newTreeNode和replacementTreeNode。完成之后,还调用了afterNodeInsertion方法,这个方法允许我们在插入完成后做些事情,默认是空实现。

为了方便分析,我们会对比HashMap中的实现与LinkedHashMap的实现,来摸清它是如何做的。

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

// LinkedHashMap中的实现
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;
}

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

// LinkedHashMap中的实现
Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
    LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
    LinkedHashMap.Entry<K,V> t =
        new LinkedHashMap.Entry<K,V>(q.hash, q.key, q.value, next);
    transferLinks(q, t);
    return t;
}

// newTreeNode和replacementTreeNode和此类似

通过以上对比,可以发现,LinkedHashMap在新增时,调用了linkNodeLast,再替换时调用了transferLinks。以下是这两个方法的实现。

// 就是将元素挂在链尾
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    if (last == null)
        head = p;
    else {
        p.before = last;
        last.after = p;
    }
}

// 用dst替换src
private void transferLinks(LinkedHashMap.Entry<K,V> src,
                            LinkedHashMap.Entry<K,V> dst) {  
    LinkedHashMap.Entry<K,V> b = dst.before = src.before;
    LinkedHashMap.Entry<K,V> a = dst.after = src.after;
    if (b == null)
        head = dst;
    else
        b.after = dst;
    if (a == null)
        tail = dst;
    else
        a.before = dst;
}

最后我们看下afterNodeInsertion做了哪些事情吧:

// evict在HashMap中说过,为false表示是创建阶段
void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    // 不是创建阶段
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        // 自动删除最老的元素,也就是head元素
        removeNode(hash(key), key, null, false, true);
    }
}

removeEldestEntry是当想要在插入元素时自动删除最老的元素时需要复写的方法。其默认实现如下:

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

2、查询

因为要支持访问顺序,所以获取元素的方法和HashMap也有所不同。下面我们看下其实现:

public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)
        // 数据被访问,需要将其移动到末尾
        afterNodeAccess(e);
    return e.value;
}

getNode方法是在HashMap中实现的,所以这是包装了一下HashMap的方法,并添加了一个afterNodeAccess,其实现如下:

void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    // e元素不在末尾
    if (accessOrder && (last = tail) != e) {
        // p是e,b是前一个元素,a是后一个元素
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        // e要放在末尾,所以没有after
        p.after = null;

        // 把e去掉,把b和a接起来
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a != null)
            a.before = b;
        else
            last = b;

        //把e接在末尾
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

加载全部内容

相关教程
猜你喜欢
用户评论