基于双向链表实现Dict扩容后插入顺序异常的修复咨询

问题现象 #

实现类似Python dict的Dict类，通过双向链表维护插入顺序：

• 插入前7个键值对(4,4),(5,5),(6,6),(7,7),(1,1),(2,2),(3,3)时，顺序正常，为[(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(7,7)]
• 插入(8,8)触发扩容后，双向链表出现重复元素，顺序变为(4,4),(5,5),(6,6),(7,7),(1,1),(2,2),(3,3),(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(7,7)，插入顺序完全混乱

现有代码 #

双向链表类 #

public class DoubleLinkedList {
    Node<K, V> head;
    Node<K, V> tail;

    public DoubleLinkedList() {
        head = null;
        tail = null;
    }

    public void insertAtEnd(Node<K, V> node)
    {
        if (tail == null) {
            head = node;
            tail = node;
        }
        else {
            tail.next = node;
            node.prev = tail;
            tail = node;
        }
    }
}

Dict类与Node类 #

public class Dict<K, V> implements Iterable<K>{

    public static class Node<K, V> {
        private K key;
        private V value;
        // liberado == 1, ocupado == 0
        private int state;
        private Node<K, V> next;
        private Node<K, V> prev;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            this.state = 0;
            this.next = null;
            this.prev = null;
        }

        public Node(K key, V value, int state) {
            this.key = key;
            this.value = value;
            this.state = state;
            this.next = null;
            this.prev = null;
        }

        public int getState() {
            return state;
        }

        public K getKey() {
            return key;
        }
    }

    private Node<K, V>[] dict;
    private int size;
    private final double loadFactor = 0.80;
    private DoubleLinkedList list;

    public Dict() {
        this.size = 0;
        this.dict = new Node[10];
        this.list = new DoubleLinkedList();
    }

    // 假设散列方法已实现
    private int disperse(K key) {
        return key.hashCode() % dict.length;
    }
}

put与原resize方法 #

public void put(K key, V value) {
    if (this.size + 1 > (this.dict.length * 0.8)) {
        resize();
    }

    int clave = disperse(key);
    for (int i = 0; i <= dict.length; i++) {
        int index = (clave + i) % this.dict.length;
        if (dict[index] == null || dict[index].getState() == 1) {
            Node<K, V> newNode = new Node(key, value);
            dict[index] = newNode;
            list.insertAtEnd(newNode);
            this.size++;
            return;
        } else if (dict[index] != null && dict[index].key.equals(key)) {
            dict[index].value = value;
            System.out.println(dict[index].value);
            return;
        }
    }
}

private void resize() {
    int capacidad = (int) (dict.length * 1.5);
    Node<K, V>[] antiguoDict = this.dict;
    this.dict = new Node[capacidad];
    size = 0;
    for(Node<K, V> node : antiguoDict){
        if(node != null){
            put(node.key, node.value);
        }
    }
}

错误尝试的resize方案及pop方法 #

private void resize() {
    int capacidad = (int) (dict.length * 1.5);
    int prev_size = size;
    Node<K, V>[] nuevoDict= new Node[capacidad];
    Node<K, V> current = this.list.head;

    this.dict = nuevoDict;

    for (int i = 0; i < prev_size; i++) {
        put(current.key, current.value);
        pop(current.getKey());
        current = this.list.head;
    }
}

public void pop(K key) throws NullPointerException {
    int clave = disperse(key);
    for (int i = 0; i < dict.length; i++) {
        int index = (clave + i) % this.dict.length;
        Node<K, V> node = dict[index];
        if (node == null) {
            throw new NullPointerException();
        }
        if (node.key.equals(key)) {
            if (node.prev != null) {
                node.prev.next = node.next;
            } else {
                list.head = node.next;
            }
            if (node.next != null) {
                node.next.prev = node.prev;
            } else {
                list.tail = node.prev;
            }
            dict[index] = new Node<>(null, null, 1);
            size--;
            return;
        }
    }
    throw new NullPointerException();
}

问题根源与解决方案 #

问题根源 #

1. 原resize方法：遍历旧数组调用put，put会创建新的Node并插入双向链表，但原链表中的旧Node并未被移除，导致链表中同时存在新旧节点，出现重复。
2. 错误尝试的resize方案：每次put后立刻pop原节点，且循环中current重置为list.head，最终会把所有节点都删除，导致字典为空。

正确的resize实现 #

核心思路：双向链表已经维护了正确的插入顺序，扩容只需要将现有节点重新哈希到新数组，不需要修改链表结构，避免重复添加节点。

修改后的resize方法：

private void resize() {
    int capacidad = (int) (dict.length * 1.5);
    Node<K, V>[] nuevoDict = new Node[capacidad];
    Node<K, V> current = list.head;

    // 遍历双向链表，将每个节点重新哈希到新数组
    while (current != null) {
        Node<K, V> nextNode = current.next; // 提前保存下一个节点，避免操作影响遍历
        int clave = disperse(current.key);
        
        // 线性探测找新数组的空闲位置
        for (int i = 0; i <= nuevoDict.length; i++) {
            int index = (clave + i) % nuevoDict.length;
            if (nuevoDict[index] == null) {
                nuevoDict[index] = current;
                break;
            }
        }
        current = nextNode;
    }

    // 替换为新数组，size保持不变（节点数量未变）
    this.dict = nuevoDict;
}

补充说明 #

• 此方法直接复用原有的Node对象，不会创建新节点，因此双向链表的结构和顺序完全保留，不会出现重复元素。
• 遍历双向链表而非旧数组，能确保只处理有效节点（跳过被标记为liberado的节点，因为这类节点不在链表中）。
• 无需重置size，因为扩容只是改变数组容量，节点总数没有变化。

内容的提问来源于stack exchange，提问作者GoldenPlus 89