如果您不知道 vs2010 实际上需要总排序，请参阅此内容，因此它需要较少的用户定义。
一个答案说二进制搜索是可能的，但我不这么认为，这是因为
- 哈希函数应该是统一的，并且负载因子最好小于 1，这意味着，在大多数情况下，每个哈希槽一个元素。即不需要二分查找。
- 显然，由于定位合适，它会减慢插入速度。
哈希映射如何从这种设计中受益？我们如何利用这种设计？
谢谢
问问题
98 次
2 回答
1
哈希函数应该是统一的，并且负载因子最好小于 1，这意味着，在大多数情况下，每个哈希槽一个元素。即不需要二分查找。
每个哈希槽最多不会有一个元素。一些存储桶将不得不保留多个密钥。除非输入仅来自预先确定的受限值集（即完美散列），否则散列函数将不得不处理比它可以产生的输出更多的输入。会有碰撞；这在像这个一样通用的实现中是不可避免的。然而，好的散列函数应该产生分布良好的散列，这使得每个散列槽的元素数量保持在较低水平。
显然，它会因为定位合适的位置而减慢插入速度。
假设一个好的散列函数和非退化输入（输入被设计成许多元素产生相同的散列），每个桶总是只有几个键。插入这样的二叉搜索树不会有那么大的成本，而且很少的成本可能会在其他地方带来好处（搜索可能比使用链表的实现更快）。并且在退化输入的情况下，哈希图会退化成二叉搜索树，这比简单的链表要好得多。
于 2012-09-20T14:16:44.023 回答
0
您的问题在实践中基本上是无关紧要的，因为 C++ 现在提供unordered_map使用Equal谓词而不是小于比较器的等。
但是，考虑一个hash_map<string, ...>. 显然， 的值空间string大于 的size_t，因此对于任何散列函数，都会存在具有相同散列值的值，因此被放置在同一个桶中。在哈希表中的所有项目都放在同一个桶中的病态情况下，利用键之间的排序将提高访问、插入和删除的速度。
请注意，在有序列表（或二叉树）上的搜索是 O(log n) 而不是 O(n)。
于 2012-09-20T14:11:53.487 回答