c++ - 如何提高具有 100 万个元素和 997 个桶的哈希表的性能？

Question

这是一道面试题。

假设表中有100万个元素和997桶无序列表。进一步假设哈希函数以相等的概率分布键(即每个桶有 1000 个元素)。

找到不在表中的元素的最坏情况时间是多少？找到表中的一个？您如何改进这一点？

我的解决方案:查找不在表中和在表中的元素的最坏情况时间都是 O(1000)。 1000 是未排序列表的长度。

改进它:(0) 直截了当，增加桶数 > 100 万。(1) 每个桶都有一个第二个哈希表，它使用不同的哈希函数为第二个表计算哈希值。它将是 O(1)(2) 每个桶中都有一棵二叉搜索树。它将是 O(lg n)。

是否可以在空间和时间之间做出权衡。将两者保持在合理范围内。

有什么更好的主意吗？谢谢 !

Answer 1

最简单和最明显的改进是将哈希表中的桶数增加到大约 120 万——至少假设您的哈希函数可以生成该范围内的数字(通常会这样)。