我目前正在阅读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)]
在我看来，散列键只会导致链表，所以在任何一种情况下，列表都需要搜索才能找到当前被删除的实际值？
我确信有一个简单的答案，但我就是不清楚！
在我看来，散列键只会导致链表，所以在任何一种情况下，仍然需要搜索列表以找到当前正在删除的实际值？
没错，当有人要求erase(key)时，双链接列表没有任何好处，因为即使在遍历单链表时也很容易擦除。
尽管如此，类似(伪代码(的代码还是很常见的。。。
if (iterator i = hash_table.find(key)) {
do_something_with(*i);
if (should_erase(*i))
erase(i);
}
这里，迭代器i可以是指向双链表中的节点的指针，因此访问与该节点相关联的元素/值的每个解引用操作*i不必重复哈希表桶查找或双链表搜索的任何部分。
如果随后决定为erase(i)，则迭代器识别要擦除的节点，而不需要另一次搜索。
如果只使用单链表，那么对于erase(iterator)，为了避免重新搜索，它需要存储一个指向前一个元素的下一个指针的指针(这实际上是GCC的C++哈希表容器所做的(。如果它只存储它(以使迭代器更小(，那么要访问迭代器逻辑寻址的元素，它必须首先查找上一个元素的下一个指针，然后再查找到逻辑寻址的节点：这不是超高效的。如果它存储了逻辑寻址元素的地址和上一个元素(或者更具体地说是下一个指针(，那么迭代器就会变成更大的对象，这也会对内存使用和性能产生潜在影响。尽管如此，你还是节省了一笔"先前的"；列表中每个链接的指针，并且可能有很多元素而不是很多迭代器。