unordered_map 真的是无序的吗?

2022-01-08 00:00:00 hashmap c++ unordered-map

我对unordered_map"这个名字感到很困惑.顾名思义，键根本没有排序.但我一直认为它们是按哈希值排序的.还是说错了(因为名字暗示它们不是有序的)?

I am very confused by the name 'unordered_map'. The name suggests that the keys are not ordered at all. But I always thought they are ordered by their hash value. Or is that wrong (because the name implies that they are not ordered)?

或者换个说法:这是这个

Or to put it different: Is this

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 multimap 并覆盖相等检查.)

? (OK, not exactly, STL will complain here because there may be keys k1,k2 and neither k1 < k2 nor k2 < k1. You would need to use multimap and overwrite the equal-check.)

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

Or again differently: When I iterate through them, can I assume that the key-list is ordered by their hash value?

推荐答案

在回答您编辑的问题时，这两个片段根本不相等.std::map 将节点存储在树结构中，unordered_map 将它们存储在哈希表中*.

In answer to your edited question, no those two snippets are not equivalent at all. std::map stores nodes in a tree structure, unordered_map stores them in a hashtable*.

键不按其哈希值"的顺序存储，因为它们根本不按任何顺序存储.相反，它们存储在桶"中，其中每个桶对应于一系列哈希值.基本上，实现是这样的:

Keys are not stored in order of their "hash value" because they're not stored in any order at all. They are instead stored in "buckets" where each bucket corresponds to a range of hash values. Basically, the implementation goes like this:

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 数组的大小，可能使用树结构而不是链表作为存储桶，等等)，但这应该可以让您了解如何无法以任何特定顺序取回值.请参阅维基百科了解更多信息.

Obviously that's a serious simplification and real implementation would be much more advanced (for example, supporting resizing the buckets array, maybe using a tree structure instead of linked list for the buckets, and so on), but that should give an idea of how you can't get back the values in any particular order. See wikipedia for more information.


* 从技术上讲，std::map 和 unordered_map 的内部实现是实现定义的，但标准要求一定的 Big-O 复杂度来实现 暗示那些内部实现

* Technically, the internal implementation of std::map and unordered_map are implementation-defined, but the standard requires certain Big-O complexity for operations that implies those internal implementations

相关文章