java - 如何确定具有双重哈希的 Hashtable 何时已满？

Question

我正在实现一个使用双重哈希的哈希表。但是，我的 insert(element) 方法有问题。它现在基本上执行以下操作：

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

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

但是，有没有更简洁的方法来做到这一点。就像，是否有可能从我的双重哈希的深度推断出数组必须是满的（数学上）？

Answer 1

我想您应该已经在跟踪表中用于任何size()函数的元素数量，因此您可以将元素数量与存储桶数量进行比较以确定表的完整性。如果您没有跟踪大小，那么您应该通过增加和减少插入和删除操作中的计数器来开始这样做。

跟踪大小是几乎所有哈希表实现都要做的事情，以避免size()调用的 O(n) 成本。

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