std :: unordered_map如何存储和比较其键以实现对元素的快速访问而无需排序？

Question

据我所知，std :: unordered_map用于快速访问元素。这是通过存储和比较密钥哈希而不是密钥本身来实现的。同样，无序意味着其中的元素未排序。但是要快速访问元素，需要对项目进行排序，以便能够使用二进制搜索找到请求的项目。

• 这是否意味着unordered_map中的项目是根据其哈希键进行排序的，而导致unordered_map比映射到访问元素的映射更快的唯一原因是比较哈希值通常比比较键值要快得多？
• 如果是这样，则在unordered_map和map之间进行选择取决于键的类型。我对吗？

• 最后一个问题是为什么unordered_map不能像地图一样获得Compare模板参数？unordered_map如何仅通过相等的运算符比较键哈希？

  template <class Key,
            class T,
            class Compare = less<Key>,
            class Alloc = allocator<pair<const Key,T> >
            > class map;
  
  template <class Key,
            class T,
            class Hash = hash<Key>,
            class Pred = equal_to<Key>,
            class Alloc = allocator< pair<const Key,T> >
            > class unordered_map;
  

Answer 1

快速元素访问确实需要某种形式的排序。Unordered_map之所以这样称呼，是因为在添加或删除元素时，排序可能对人类没有意义，并且可能不会保持稳定。

unordered_map不会比map因为一对一地比较散列要快于一对一地比较任意对象要快。它更快，因为它根本不需要比较。这就是为什么它不需要compare模板参数的原因。

典型的unordered_map实现是哈希表。哈希表通常是键值对的常规数组，它使用巧妙的技巧来帮助您快速找到要查找的元素。

理想的散列函数是均匀分布的：如果要从任何对象中随机选择一个散列，则hash % N某个整数N 的值应大致均匀（假装不存在模偏差的一秒钟）。如果选择N作为键值对数组的大小，则可以hash(key) % size用作数组索引以进行快速查找。

由于哈希值应该是均匀分布的，因此不同的对象通常具有不同的索引，因此这样做通常对您有利。但是，hash(key) % N对于两个对象仍然可能是同一件事。在这种情况下，哈希表需要处理冲突：存在多种策略，但是所有这些策略通常都演变为对属于同一哈希存储桶的键进行线性搜索（因此，哈希表需要包含密钥，而不仅仅是密钥的哈希值）。这就是为什么哈希表的最坏情况下的访问时间为O（n）的原因，并且它突出了具有良好哈希函数的重要性。

在某些情况下，这可能是一个理由，更喜欢map了unordered_map，因为的访问性能map（O（log n）的）是很容易预测。

另外，随着哈希表中占用的存储桶数增加，发生冲突的机会也会增加。通常，由于这个原因，哈希表将具有比元素更多的存储桶，这意味着它在浪费空间以提高效率。