unordered_map真的无序吗？

Question

我对'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并覆盖等号检查.)

或者不同的是:当我遍历它们时,我可以假设密钥列表按其哈希值排序吗？

Answer 1

在回答您编辑过的问题时,这两个片段根本不相同.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复杂性的操作意味着那些内部实现

Answer 2

"无序"并不意味着实现中某处没有线性序列.它意味着"你不能假设这些元素的顺序".

例如,人们通常认为条目将以与它们放入的顺序相同的顺序出现在哈希映射中.但它们不会,因为条目是无序的.

至于"按其哈希值排序":哈希值通常取自整个整数范围,但哈希映射中没有2**32个槽.通过将散列值的模数设为模数,散列值的范围将减少到插槽的数量.此外,当您向哈希映射添加条目时,它可能会更改大小以适应新值.这可能导致重新放置所有先前的条目,从而更改其顺序.

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