java - LinkedHashMap 中的 addbefore 方法如何工作

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 方法的参数始终是 header 条目，因此 addBefore 方法中的 after 变量始终是 header 条目。此外， header 节点永远不会更改。

我的问题是 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 中查找 bucketindex 的第一个条目，并将新节点添加到该存储桶的列表开头。所以这里传递的旧参数基本上变成了插入节点的下一个指针。

第四行调用 addBefore 方法，其中 header 作为引用传递。

after = ExistingEntry → 这里existingEntry是header，after基本上是this.after，所以它有效地使新节点的after指针指向header。

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

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

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

因此，linkedhashmap维护一个循环双向链表，用于维护插入顺序/访问顺序(由accessOrder参数控制)。我希望这对您有所帮助。