std::unordered_map如何存储和比较它的key，实现元素的无序快速访问？

Question

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

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

最后一个问题是为什么 unordered_map 没有得到比较模板参数就像地图一样？ 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 的大多数实现是 hash tables. In hash tables the entries are not simply sorted, but rather divided into buckets. The ordered map might be implemented as a tree instead, as suggested by for example this website。

您选择哪个集合不仅仅取决于密钥的类型。在不同情况下，两者在功能、内存使用和效率方面各有优缺点。但是我会说，在一般情况下，如果您绝对不需要有序键，unordered_map 是更好的选择，因为不保证顺序可以让实现更自由地高效地实现事物（哈希表通常有 O(1)查找性能）。此外，在大多数其他编程语言中，默认映射类型不保证顺序，因此它似乎是一个常见的选择。

unordered_map使用的散列类型被指定为size_t，它只是一个整数，所以它可以只使用标准的整数运算来与散列进行比较和计算。

Answer 2

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

unordered_map 并不比 map 快，因为一对一比较哈希比一对一比较任意对象更快。它更快，因为它根本不需要比较。这就是为什么它不需要 compare 模板参数。

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

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

由于散列值应该是均匀分布的，不同的对象通常会有不同的索引，所以这样做通常对你有利。但是，hash(key) % N 仍然有可能是两个对象的同一事物。在这种情况下，哈希 table 需要处理冲突：有多种策略，但所有策略通常都在落入同一哈希桶 [=38 中的键内进行线性搜索=]（因此，散列 table 也需要包含密钥，而不仅仅是密钥的散列）。这就是为什么哈希的最坏情况访问时间 table 是 O(n) 的原因，它突出了拥有良好哈希函数的重要性。

在某些情况下，这可能是更喜欢 map 而不是 unordered_map 的原因，因为 map (O(log n)) 的访问性能非常预测table.

此外，随着散列中占用的桶数 table 增加，发生冲突的机会也会增加。通常，由于这个原因，哈希 tables 的桶数将多于元素，这意味着它的效率是 "wasting" space。

std::unordered_map如何存储和比较它的key，实现元素的无序快速访问？

How does std::unordered_map store and compare its keys to achieve fast access to elements without ordering?

c++

hash

dictionary

unordered-map