hashmap - hashmap 和探测 - AVAILABLE 和 null？

Question

在线性探测中，有一个称为特殊值的值AVAILABLE，它会在删除项目时被替换。

当您插入一个键时，您会寻找一个空单元格（这只是意味着该单元格是null？）或包含的一个，AVAILABLE我不明白的是，如果空单元格意味着null而不是具有特殊值AVAILABLE，为什么不只是制作细胞null？

与使用相比有什么优势AVAILABLE？

Answer 1

在封闭散列（开放寻址）中，一个值被查找为：

1. 计算密钥哈希并从中确定“完美”的桶；
2. 如果bucket被占用并且key与查找的key相同，则返回value；
3. 如果桶未被占用，则以失败中止查找；
4. 转到下一个桶（使用线性探测只是增加桶索引）和步骤 2。

现在，假设您开始在桶 5 中查找并仅在桶 8 中找到您的密钥。如果擦除过程现在将桶 6 标记为未占用，由于步骤 3，您将永远无法到达桶 8。因此，我们需要一个特殊值将存储桶标记为“已占用”，但仍可插入。这可能是您的源术语AVAILABLE，并且null根本没有被占用。

编辑：顺便说一句，使用线性探测可以（相当）有效地摆脱这个特殊AVAILABLE值，但这会使擦除变得相当复杂。