java - 哈希表中的墓碑

Question

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

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

Answer 1

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

• 如果您的表不允许使用null对象，那么您可以使用null对象来标记空闲的插槽，然后根据插槽为空的原因让关联的整数采用不同的值（例如，0 表示“从未填充” 1 表示“墓碑”等）

• 如果您的表确实允许null对象，您可以将特殊情况null作为键并null与哈希表的其余部分分开存储（例如，具有对应于是否null是键的类的专用字段，如果是，则值是什么与之相关）。然后，您可以使用上述技术标记空表槽。

• 如果您的表不允许使用负键，那么您可以使用负键来标记空槽（例如，-1 表示“此槽为空”，-2 表示“这是一个墓碑”。）

• 如果您的表允许任意键和值，那么您可以添加并行的布尔数组（或用作位向量的整数数组，这更节省空间）来标记哪些槽是空的，哪些槽是墓碑。

• 如果您对间接级别没问题，您可以让每个表槽成为一个指向表示该槽信息的对象的指针。你可以有一些基类类型（比如，HashSlot）和两个子类（比如，Tombstone和Entry），其中Tombstone只标记一个墓碑插槽并Entry实际存储键/值对。

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

希望这可以帮助！

Answer 2

由于“HashVariable”是您编写的类，您可以使用布尔变量将 HashVariable 标记为墓碑（除了具有名称和值）。有关示例实现，请查看此处。