哈希表中的Tombstone

Question

我正在为哈希表编写一个类。哈希表是我编写的一个名为HashVariable的类中的一个对象数组。HashVariable只有两个属性，一个名称和一个整数值。我知道如果我从表中删除一个项目，我将不得不用一个“墓碑”来替换它，但我不确定我应该使用什么作为墓碑。

我真的没有尝试太多，因为我不确定我能做什么。我可以尝试将一个字符强制转换为HashVariable并将其插入到数组中，但我不能这样强制转换它。

Answer 1

有许多方法可以做到这一点，这取决于您的表中允许存储的内容。

• 如果您的表不允许使用null对象，那么您可以使用null对象来标记空闲的插槽，然后根据插槽为空的原因让相关的整数采用不同的值(例如，0表示“从未填满”，1表示“墓碑”等)。
• 如果您的表允许使用null对象，则可以将null作为键，并将null与哈希表的其余部分分开存储(例如，具有对应于D9是否是键的类的专用字段，并且，如果是，则与其关联的值是什么)。如果您的表不允许使用负键，那么您可以使用负键来标记空槽(可能，例如，-1表示"this slot is empty“，-2表示"this is
• ”，然后您可以在布尔值的并行数组中添加布尔值(或作为位向量的整数数组，哪个更节省空间)为了标记哪些槽是空的，哪些槽是tombstones.
• If的，您可以让每个表槽成为一个指针，指向一个表示该槽信息的对象。您可以有一些基类类型(比如HashSlot)和两个子类(比如Tombstone和Entry)，其中Tombstone只是标记一个逻辑删除槽，而Entry实际上存储键/值对。

这并不是一个详尽的选项列表。如你所知，这里有很多你可以使用的策略！看看其中哪一个看起来最适合您的特定设置。

希望这能有所帮助！

Answer 2

由于" HashVariable“是您编写的类，因此您可以使用一个布尔变量将HashVariable标记为tombstone (除了具有名称和值之外)。有关示例实现，请看一下here。