哈希表:将存储桶标记为空的最好方法是什么？

Question

遇到了一个恼人的问题--我需要一些方法来判断我试图填充的存储桶是否是空的(这些存储桶存储为键值对的值类型结构数组)。

如果我保留一个键值来标记为空，那么这将意味着一些不幸地偶然发现该散列值的数据永远无法访问。另一方面，在KVP结构中包含一个布尔值会将结构的大小从16增加到24 (这是一种浪费，而且我现在内存很紧张)。有没有人想出一个好的解决方案？

Answer 1

这是一个与冲突一样固有的哈希表问题。一个相关的问题是处理从哈希表中删除，同样，在冲突的上下文中。没有不涉及性能折衷的解决方案，因此哈希表实现具有非法的特定键是很常见的。

到目前为止，最直接的解决方案是只使用特殊情况，即您用来表示空的键值。也就是说，如果用户试图存储键值0，则只需将其放入一个特殊的数组中即可。

真正差劲的只使用指针的哈希表通常不会有这个问题，因为你总能找到调用者不能传入的指针值(比如指向你拥有的对象的指针)。显然，使用链表或数组元素的哈希表也没有这个问题，但这会带来巨大的性能损失。

您可能会找到一些巧妙的方法，通过使用多个元素在表本身中对其进行编码。唯一更好的方法是，如果它以某种方式与删除的元素处理或其他东西统一起来，那么它将是免费的，或者比检查一些单独的列表更快。