哈希表链表中项目的删除时间
Deletion time of items in a hashtables linked list
我目前正在阅读 CLRS 书籍并查看哈希表是如何定义的，在谈论开放式哈希和使用链接来解决冲突时，有一段文字如下：
If the hash table supports deletion, then its linked lists should be doubly linked
so that we can delete an item quickly. If the lists were only singly linked, then to
delete element x, we would first have to find x in the list T[h(x.key)] so that we
could update the next attribute of x’s predecessor. With singly linked lists, both
deletion and searching would have the same asymptotic running times.)
我不明白的是为什么会这样（或者更具体地说是怎样），这是不是一个关于为什么在知道元素是时从链表中删除的问题如果它是双向链表会更快，我想我应该说清楚...
这与实际知道位置的方式有关，因此双向链表可以产生这种差异，因为查看散列删除伪代码（下方）密钥用于生成散列，从而导致可以找到链接列表的正确数组索引，但是如何准确地将其转换为项目链接列表中的实际位置？
CHAINED-HASH-DELETE(T, x)
1 delete x from the list T[h(x.key)]
在我看来，散列键只指向链表，所以无论哪种情况，仍需要搜索列表以找到当前被删除的实际值？
我确定有一个简单的答案，但我不太清楚！
It looks to me like hashing the key leads to the linked list only, so in either case the list would still need to be searched to find the actual value currently being deleted?
没错，当有人要求 erase(key) 时，双重 linked 列表没有任何好处，因为即使遍历单 linked 列表也很容易擦除.
不过，像（伪代码）这样的代码还是很常见的...
if (iterator i = hash_table.find(key)) {
do_something_with(*i);
if (should_erase(*i))
erase(i);
}
这里，迭代器i可以是指向双重link链表中节点的指针，所以每次解引用操作*i访问element/value与该节点关联的不必重复哈希 table 存储桶查找或双重 linked 列表搜索的任何部分。
如果它随后决定 erase(i)，则迭代器会识别要擦除的节点，而无需再次搜索。
如果你只使用单linked列表，那么为了erase(iterator)避免重新搜索，它需要存储指向前一个元素的下一个指针的指针（实际上是GCC 的 C++ 散列 table 容器做什么）。如果它只存储它（以保持迭代器更小），那么要访问迭代器逻辑寻址的元素，它必须首先查找前一个元素的下一个指针，然后跟随它到逻辑寻址的节点：这不是超级高效。如果它存储逻辑寻址元素的地址和前一个元素（或者更具体地说是它的下一个指针），那么迭代器就会变成更大的对象，同时也会有潜在的内存使用和性能影响。尽管如此，您仍在为列表中的每个 link 保存一个“上一个”指针，并且元素数量多于迭代器数量的可能性更大。
我目前正在阅读 CLRS 书籍并查看哈希表是如何定义的，在谈论开放式哈希和使用链接来解决冲突时，有一段文字如下：
If the hash table supports deletion, then its linked lists should be doubly linked
so that we can delete an item quickly. If the lists were only singly linked, then to
delete element x, we would first have to find x in the list T[h(x.key)] so that we
could update the next attribute of x’s predecessor. With singly linked lists, both
deletion and searching would have the same asymptotic running times.)
我不明白的是为什么会这样（或者更具体地说是怎样），这是不是一个关于为什么在知道元素是时从链表中删除的问题如果它是双向链表会更快，我想我应该说清楚...
这与实际知道位置的方式有关，因此双向链表可以产生这种差异，因为查看散列删除伪代码（下方）密钥用于生成散列，从而导致可以找到链接列表的正确数组索引，但是如何准确地将其转换为项目链接列表中的实际位置？
CHAINED-HASH-DELETE(T, x)
1 delete x from the list T[h(x.key)]
在我看来，散列键只指向链表，所以无论哪种情况，仍需要搜索列表以找到当前被删除的实际值？
我确定有一个简单的答案，但我不太清楚！
It looks to me like hashing the key leads to the linked list only, so in either case the list would still need to be searched to find the actual value currently being deleted?
没错，当有人要求 erase(key) 时，双重 linked 列表没有任何好处，因为即使遍历单 linked 列表也很容易擦除.
不过，像（伪代码）这样的代码还是很常见的...
if (iterator i = hash_table.find(key)) {
do_something_with(*i);
if (should_erase(*i))
erase(i);
}
这里，迭代器i可以是指向双重link链表中节点的指针，所以每次解引用操作*i访问element/value与该节点关联的不必重复哈希 table 存储桶查找或双重 linked 列表搜索的任何部分。
如果它随后决定 erase(i)，则迭代器会识别要擦除的节点，而无需再次搜索。
如果你只使用单linked列表，那么为了erase(iterator)避免重新搜索，它需要存储指向前一个元素的下一个指针的指针（实际上是GCC 的 C++ 散列 table 容器做什么）。如果它只存储它（以保持迭代器更小），那么要访问迭代器逻辑寻址的元素，它必须首先查找前一个元素的下一个指针，然后跟随它到逻辑寻址的节点：这不是超级高效。如果它存储逻辑寻址元素的地址和前一个元素（或者更具体地说是它的下一个指针），那么迭代器就会变成更大的对象，同时也会有潜在的内存使用和性能影响。尽管如此，您仍在为列表中的每个 link 保存一个“上一个”指针，并且元素数量多于迭代器数量的可能性更大。