use*_*288 5 c++ hash hashtable hashmap data-structures
这是一个面试问题.
假设表中有100万个元素和997个无序列表桶.进一步假设散列函数以相等的概率分配密钥(即,每个桶具有1000个元素).
查找表中没有的元素的最坏情况是什么时候？要找到表中的一个？你怎么能改善这个？
我的解决方案:查找不在表和表中的元素的最坏情况时间都是O(1000).1000是未排序列表的长度.
改进它:(0)直截了当,增加桶数> 100万.(1)每个桶包含第二个哈希表,它使用不同的哈希函数来计算第二个表的哈希值.它将是O(1)(2)每个桶包含一个二叉搜索树.它将是O(lg n).
是否有可能在空间和时间之间进行权衡.将它们保持在合理的范围内.
有更好的想法吗？谢谢 !
| 归档时间： |
|
| 查看次数： |
2364 次 |
| 最近记录： |