这是一道面试题。
假设表中有100万个元素和997桶无序列表。进一步假设哈希函数以相等的概率分布键(即每个桶有 1000 个元素)。
找到不在表中的元素的最坏情况时间是多少？找到表中的一个？您如何改进这一点？
我的解决方案: 查找不在表中和在表中的元素的最坏情况时间都是 O(1000)。 1000 是未排序列表的长度。
改进它: (0) 直截了当，增加桶数 > 100 万。 (1) 每个桶都有一个第二个哈希表，它使用不同的哈希函数为第二个表计算哈希值。它将是 O(1) (2) 每个桶中都有一棵二叉搜索树。它将是 O(lg n)。
是否可以在空间和时间之间做出权衡。将两者保持在合理范围内。
有什么更好的主意吗？谢谢 !
最佳答案
最简单和最明显的改进是将哈希表中的桶数增加到大约 120 万——至少假设您的哈希函数可以生成该范围内的数字(通常会这样)。
关于c++ - 如何提高具有 100 万个元素和 997 个桶的哈希表的性能？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9156269/