简单的哈希图删除函数不会更新地图条目

Question

我正在尝试实现一个简单的哈希映射，其中映射的每个条目表示为Node单个链表，并且我有一个条目数组，例如Node[] nodes:

static final class Node {
int key;
int value;
Node next;
int hash;
Node(int key, int value, Node next, int hash) {
this.key = key;
this.value = value;
this.next = next;
this.hash = hash;
}
}

下面是remove方法，它首先尝试在HashMap中找到键的索引位置，然后线性扫描该条目中的每个节点，并在映射中删除匹配的键:

public void remove(int key) {
int hash = computeHash(key);
Node node = nodes[hash];
if (node == null) {
return;
}
Node prev = null;
while (node.key != key && node.next != null) {
prev = node;
node = node.next;
}
if (node.key == key) {
if (prev != null) {
prev.next = node.next;
} else if (prev == null) {
node = node.next;
} else {
node = null;
}
size--;
}
}

不使匹配的节点从外部的nodes中移除，只影响被引用的局部变量。由于我有对节点的引用，我想将其从nodes中删除(如果有匹配的键)，拥有其地址并试图将其与null相关联，但它无效。我很高兴听到一些解释为什么这段代码不能工作。

我有一个简单的测试，像这样:

MyHashMap map = new MyHashMap();
map.put(1, 1);
map.put(2, 1);
map.remove(1);
System.out.println(map.get(1)); // still returns 1

Answer 1

您的本地变量node是副本nodes[hash]。分配给副本并不会改变原件。您需要更改您的代码，以便它更新原始代码。你不需要检查node.next是否等于null:没关系，如果是null，你将分配null，这正是你想要的。

if (node.key == key) {
if (prev != null) {
prev.next = node.next;
} else {
nodes[hash] = node.next;
}
size--;
}

Answer 2

检查节点是错误的。下一个不等于空。你不应该关心下一个元素，从删除的元素的下一个元素将永远不会被引用。HashMap的源代码为:

if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;

"p"是接近你的"prev"。HashMap将值赋给该哈希中的第一个元素。