给定一个有冲突的哈希表，假设使用链表，通用哈希表实现将导致桶内的查找在 O(n) 中运行。
如果我们将链表切换为二叉搜索树，我们会下降到 O(log n)。这是我们能做的最好的，还是这个用例有更好的数据结构？
对桶本身使用哈希表会使查找时间为 O(1)，但这需要对哈希函数进行巧妙的修改。
问问题
175 次
3 回答
1
在您的解决方案中，插入时间与查找时间之间存在权衡。（保持桶排序）
如果您想保持每个桶排序，您将使用二分搜索获得 O(log n) 查找时间。但是，当您插入一个新元素时，您必须将他放在正确的位置，以便对存储桶继续进行排序 - 放置新元素的 O(log n) 搜索时间。
因此，在您的解决方案中，插入和查找的总复杂度为 O(log n)。（与在最坏情况下使用 O(n) 进行查找和插入 O(1) 的传统解决方案相反）
编辑 ：
如果选择使用排序桶，当然不能再使用 LinkedList。您可以切换到任何其他合适的数据结构。
于 2012-08-09T15:05:42.740 回答
1
众所周知，完美散列可以实现在构造散列函数时已知的一组有限键的无冲突 O(1) 散列。Wikipedia 文章提到了将这些想法应用于动态键集的几种方法，例如动态完美散列和布谷鸟散列，您可能会感兴趣。
于 2012-08-09T16:23:05.970 回答
0
你几乎已经回答了你自己的问题。由于哈希表只是其他数据结构的数组，因此您的查找时间仅取决于辅助数据结构的查找时间以及您的哈希函数如何在存储桶中分配项目。
于 2012-08-09T14:39:23.037 回答