unordered_map真的无序吗？

StackOverflow https://stackoverflow.com/questions/3176621

  •  02-10-2019
  •  | 
  •  

题

我对“ unordered_map”的名称感到非常困惑。该名称表明根本没有订购钥匙。但是我一直认为它们是按其哈希价值订购的。还是这是错误的（因为名称意味着他们没有被订购）？

或说明它：这是

typedef map<K, V, HashComp<K> > HashMap;

和

template<typename T>
struct HashComp {
    bool operator<(const T& v1, const T& v2) const {
        return hash<T>()(v1) < hash<T>()(v2);
    }
};

与

typedef unordered_map<K, V> HashMap;

？ （好的，不完全是，STL会在这里抱怨，因为可能有键K1，K2，而K1 <k2也不是K2 <k1。您将需要使用 multimap 并覆盖同等检查。）

还是再次有所不同：当我迭代它们时，我可以假设密钥列表是按其哈希价值订购的？

有帮助吗？

解决方案

在回答您编辑的问题时，没有这两个片段根本不是等效的。 std::map 将节点存储在树结构中， unordered_map 将它们存储在标签*中。

密钥不是按其“哈希值”顺序存储的，因为它们不存储在 任何订单. 。相反，它们存储在“桶”中，每个存储桶对应于一系列哈希值。基本上，实施是这样的：

function add_value(object key, object value) {
   int hash = key.getHash();

   int bucket_index = hash % NUM_BUCKETS;
   if (buckets[bucket_index] == null) {
       buckets[bucket_index] = new linked_list();
   }
   buckets[bucket_index].add(new key_value(key, value));
}

function get_value(object key) {
   int hash = key.getHash();

   int bucket_index = hash % NUM_BUCKETS;
   if (buckets[bucket_index] == null) {
       return null;
   }

   foreach(key_value kv in buckets[bucket_index]) {
       if (kv.key == key) {
           return kv.value;
       }
   }
}

显然，这是一个严肃的简化，真实的实施将更加先进（例如，支持调整大小 buckets 数组，也许使用树结构而不是存储桶的链接列表，依此类推），但这应该使您无法以任何特定的顺序恢复值。看 维基百科 了解更多信息。


*从技术上讲，内部实施 std::map 和 unordered_map 是实施定义的，但是标准需要某些大型操作的复杂性 暗示 那些内部实现

其他提示

“无序”并不意味着实施中某处没有线性序列。这意味着“您不能对这些元素的顺序承担任何意见”。

例如，人们经常认为条目将以与他们的同一顺序相同的顺序出现。但是它们没有，因为条目是无序的。

至于“按其哈希值排序”：哈希值通常取自整个整数范围，但是哈希地图没有2 ** 32个插槽。哈希值的范围将通过将其模拟插槽数减少到插槽数。此外，当您将条目添加到哈希地图中时，它可能会更改大小以适应新值。这可能会导致所有先前的条目重新定位，从而改变其顺序。

在无序的数据结构中，您不能对条目的顺序进行任何假设。

顾名思义，unordered_map建议的是，C ++ 0x标准未指定订购。 UNOREREDED_MAP的明显订购将取决于实际实施方便的方便。

如果您想一个类比，请查看您选择的RDBMS。

如果执行查询时未通过子句指定订单，则结果将“无序”返回 - 也就是说，按照数据库的感觉如何。该订单未指定，系统可以自由“订购”它们，但是它喜欢以获得最佳性能。

你说的对， unordered_map 实际上是订购的。请注意，大多数当前实施（PRE TR1）称 hash_map.

IBM C/C ++编译器 文档 评论说 如果您具有最佳哈希功能，则在查找，插入和去除任意元素期间执行的操作数不取决于序列中的元素数量, ，所以这意味着该订单不是那么无序...

现在，这是什么意思 哈希订购？由于应该是不可预测的，因此，根据定义，您不能对地图中元素的顺序进行任何假设。这就是为什么它在TR1中重命名的原因：旧名称暗示了订单。现在我们知道实际使用了订单，但是您可以无视它，因为它是不可预测的。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top