如何确定双哈希表的哈希表何时已满？

Question

我正在实现一个使用双散列的散列表。但是，我的插入（元素）方法有问题。它现在基本上做了以下事情：

1. 检查数组中的计算位置是否为空。如果是这样，插入元素，我们完成
2. 如果位置被另一个元素阻塞，我们计算新的散列值并从1开始（递归）。

问题是，该算法从不检测散列表何时已满。我可以跟踪访问位置的数量，并将该数字与数组大小进行比较以解决此问题。

但是，有没有更好的方法来做到这一点。比如，是否有可能从我的双重哈希的深度推导出数组必须已满（数学）？

Answer 1

我想你应该已经在跟踪表中用于任何size()函数的元素数量，所以你可以比较元素的数量和桶的数量来确定表的丰满度。如果你没有记录大小，那么你应该简单地通过增加和减少插入计数器并删除操作来开始。

保持跟踪的大小是几乎所有哈希表实现的东西，以避免O（n）成本为size()调用。

以上是假设您不允许每个标准哈希表（根据您的描述情况）的每个存储桶中有多个元素。