哈希表：为什么它定义了less而不是equal_to？

Question

使用Visual Studio 2010的C++。一个关于为什么用户定义的hash_map特征实际上需要完全排序的问题。

我有一个简单的结构，比如说FOO，它只有一些整数。我想要使用hash_map来存储FOO的结构，hash_map是一个哈希表，其键是无序的。我只需要快速搜索它的相关值，所以这是一个正确的选择：hash_map<FOO，int32_t>。

然而，我需要实现自己的哈希函数和一些比较函数来处理FOO。这里是hash_map的定义，取自MSDN：

template <
   class Key, 
   class Type, 
   class Traits=hash_compare<Key, less<Key> >, 
   class Allocator=allocator<pair <const Key, Type> > 
>
class hash_map

结果发现我需要实现hash_compare函数对象：

template<class Key, class Traits = less<Key> >
   class hash_compare
   {
   Traits comp;
public:
   const size_t bucket_size = 4;
   const size_t min_buckets = 8;
   hash_compare( );
   hash_compare( Traits pred );
   size_t operator( )( const Key& _Key ) const; // This is a hash function
   bool operator( )(                            // This is an ordering function
      const Key& _Key1,
      const Key& _Key2
   ) const;
   };

以下是对 MSDN 中 bool operatod() 的详细描述：

对于序列中任何类型为 Key 的值 _Key1，如果它在序列中位于 _Key2 之前并且具有相同的哈希值（哈希函数返回的值），则 hash_comp(_Key2, _Key1) 为 false。该函数必须对类型为 Key 的值施加完全排序。

由 hash_compare 提供的函数返回 comp(_Key2, _Key1)，其中 comp 是您在构造对象 hash_comp 时可以指定的类型 Traits 的存储对象。对于默认的 Traits 参数类型 less，排序键永远不会减小其值。

编写 FOO 的 hash_compare 类非常容易。这个问题不是要求您如何实现一个类。然而，我不太明白为什么它们将默认的特征参数设置为 less 并要求完全排序。

hash_map 是一种无序数据结构。因此，我认为只需要 equal_to 或 not_equal_to 而不是 less 或 greater 就足够了。但是，MSDN 的描述明确说明键是有序的，这让我感到困惑。

我是否误解了 hash_map 的定义？为什么 STL 的 hash_map 实际上要求其键有序？

- minjang

Answer 1

你看到的 hash_map 是一个微软扩展，从VS2003开始使用，现在实际上已经在 Visual C++ 的 stdext 中，它不是STL的一部分。

std::unordered_map 是STL官方版本的关联容器，可以通过可哈希的键访问值 - 它的谓词是相等性，正如你所期望的那样。

template<class Key,
    class Ty,
    class Hash = std::hash<Key>,
    class Pred = std::equal_to<Key>,
    class Alloc = std::allocator<std::pair<const Key, Ty> > >
    class unordered_map;

- Steve Townsend

Answer 2

任何类型为Key的值_Key1在序列中出现在_Key2之前并且具有相同的哈希值（由哈希函数返回的值）时，hash_comp(_Key2, _Key1)为false。该函数必须对类型为Key的值强制实施一个完全排序。

具有相同哈希值的键的完全排序保证了散列到同一桶的键的完全排序。

这为在特定桶内搜索键提供了更高效的实现，例如Θ(log n)二分搜索是可能的。如果没有这样的保证排序，最坏情况（许多不同的键都在同一个桶中，因为它们都散列到相同的值）是Θ(n)。

- Matthew Slattery

---

我认为这种完全排序对搜索没有帮助。原因如下：

1. 哈希函数应该是均匀的，而且在负载因子小于1的情况下，大多数情况下一个哈希槽只有一个元素。也就是说，不需要二进制搜索。
2. 很明显，它会减缓插入速度。

- Chang

@Chang，除非您事先知道所有可能的键，否则无法保证每个插槽只有一个元素 - 实际上，一种DOS攻击利用哈希函数的知识故意产生冲突。而且，很明显这不会减缓插入速度。 - Mark Ransom

Answer 3

hash_map的确切要求因实现而异，其中一些要求（如您所见）并不太合理。这就是为什么他们决定在TR1和/或C++0x中不包括hash_map（或hash_*）的部分原因。相反，他们有unordered_[multi](map|set)，它只需要equal_key，而不需要operator<。

底线：除非您有真正杰出的理由，否则请使用unordered_map而不是hash_map。

- Jerry Coffin

---

+1 对于一个有趣的历史课来说很赞，但我觉得它并没有完全回答问题... - Mark Ransom

谢谢！是的，我应该使用unordered_map。我想知道hash_map相对于map和unordered_map有哪些独特的特性。 - minjang

@minjang：map是有序的（通常实现为平衡树），因此支持查找范围内的项目等操作。unordered_map提供O(1)的插入/删除/查找。hash_map类似于unordered_map，但没有规范可遵循，因此不同版本具有不同的功能、要求等。 - Jerry Coffin