加载项在LinkedHashMap中是如何工作的？

Question

我正在查看LinkedHashMap的源代码，而addBefore方法使我非常困惑：

private void addBefore(Entry<K,V> existingEntry) {
            after  = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
}

在createEntry方法中调用此方法：

void createEntry(int hash, K key, V value, int bucketIndex) {
        HashMap.Entry<K,V> old = table[bucketIndex];
        Entry<K,V> e = new Entry<>(hash, key, value, old);
        table[bucketIndex] = e;
        e.addBefore(header);
        size++;
}

很明显，传入addBefore方法的参数始终是标头条目，因此addBefore方法中变量之后的始终是标头条目。此外，头节点从不更改。

我的问题是，addBefore方法是如何形成一个双链接列表的？

Answer 1

如果您注意到，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);
    }
}

我要一条条地走：

HashMap.Entry<K,V> old = table[bucketIndex];
Entry<K,V> e = new Entry<>(hash, key, value, old);
table[bucketIndex] = e;

这3行只需在hashmap中找到存储桶索引的第一个条目，并在此桶的列表开始时添加新节点。因此，这里传递的旧参数基本上成为插入节点的下一个指针。

第4行调用addBefore方法，其中标头作为引用传递。

这里的after = existingEntry→是标头，而existingEntry基本上是this.after，因此它有效地使新节点的后指针指向标头。

before = existingEntry.before;→，这再次使新节点的前指针指向头的，这是列表中的最后一个元素(它是一个循环双链接列表)。

before.after = this;→--这使得列表中的最后一个节点(因为之前的新节点现在指向列表中的最后一个节点)的后指针指向我们要插入的新节点。

after.before = this;→--它现在更改了头的前指针。必须更改头的前一个，因为列表中的最后一个节点现在是我们要插入的新节点，这个语句有效地做到了这一点。

因此，linkedhashmap维护一个循环双链接列表，用于保持插入顺序/访问顺序(由accessOrder参数控制)。希望这能帮到你。