13

我对“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并覆盖相等检查。）

或者再次不同：当我遍历它们时，我可以假设键列表是按它们的哈希值排序的吗？

4

5 回答 5

23

在回答您编辑的问题时，这两个片段根本不相等。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实现定义的，但标准需要一定的 Big-O 复杂性来进行操作，这意味着那些内部实现

于 2010-07-05T00:12:22.603 回答
6

“无序”并不意味着在实现中某处没有线性序列。这意味着“你不能对这些元素的顺序做出任何假设”。

例如，人们经常假设条目将按照它们被放入的顺序从哈希映射中出来。但事实并非如此，因为条目是无序的。

至于“按其哈希值排序”：哈希值一般取自整数的全范围，但哈希映射中没有 2**32 个槽。哈希值的范围将通过取模槽数来减少到槽数。此外，当您向哈希映射添加条目时，它可能会更改大小以适应新值。这可能会导致所有先前的条目被重新放置，从而改变它们的顺序。

在无序数据结构中，您不能假设条目的顺序。

于 2010-07-05T00:04:36.343 回答
2

正如名称 unordered_map 所暗示的，C++0x 标准没有指定排序。unordered_map 的表观顺序将取决于便于实际实现的任何内容。

于 2010-07-05T00:06:41.303 回答
1

如果您想进行类比，请查看您选择的 RDBMS。

如果您在执行查询时没有指定 ORDER BY 子句，则返回的结果是“无序的”——也就是说，按照数据库感觉的任何顺序。没有指定顺序，系统可以随意“订购”它们以获得最佳性能。

于 2010-07-04T23:58:31.770 回答
1

你是对的，unordered_map实际上是哈希排序的。请注意，大多数当前实现（TR1 之前）都将其称为hash_map.

IBM C/C++ 编译器文档指出，如果您有一个最佳散列函数，则在查找、插入和删除任意元素期间执行的操作数不取决于序列中的元素数，因此这意味着订单不是那么无序...

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

于 2010-07-04T23:59:15.170 回答