unordered_map是否真的无序？ [英] Is the unordered_map really unordered?

问题描述

我非常困惑于'unordered_map'这个名字。该名称暗示密钥根本没有排序。但我一直认为他们是按他们的散列值排序的。或者是错的（因为名字意味着它们没有被订购）？

或者说不同：这是

  typedef map< K，V，HashComp< K> > HashMap的; 
  

with

 模板< typename T> 
 struct HashComp {
 bool operator<（const T& v1，const T& v2）const {
 return hash< T>（）（v1）散列< T>（）（V2）; 
} 
}; 
  

与

相同

  typedef unordered_map< K，V> HashMap的; 
  

？ （OK，不完全是，STL会在这里抱怨，因为可能有键k1，k2，k1 multimap 和覆盖相等检查。）

或者再次改变：当我遍历它们时，我可以假设key-list是按其散列值排序的吗？

解决方案

在回答你所编辑的问题时，没有那两个片段是完全不相同的。 std :: map 将节点存储在树结构中， unordered_map 将它们存储在散列表*中。

密钥不是按照它们的散列值存储的，因为它们没有以任何顺序存储 。它们被存储在桶中，其中每个桶对应于一系列散​​列值。基本上，实现如下所示：

  function add_value（object key，object value）{
 int hash = key .getHash（）; 
 
 int bucket_index = hash％NUM_BUCKETS; 
 if（bucket [bucket_index] == null）{
 bucket [bucket_index] = new linked_list（）; 
} 
 bucket [bucket_index] .add（new key_value（key，value））; 
 
 
函数get_value（object key）{
 int hash = key.getHash（）; 
 
 int bucket_index = hash％NUM_BUCKETS; 
 if（bucket [bucket_index] == null）{
 return null; 
 
 
 foreach（key_value kv桶[bucket_index]）{
 if（kv.key == key）{
 return kv.value; 
} 
} 
} 
  

显然这是一个严重的简化，真正的实现将更加先进（例如，支持调整大小存储桶数组，也许使用树结构而不是链接列表来存储存储桶等等），但是应该说明你如何不能以任何特定的顺序取回价值。有关更多信息，请参见 wikipedia 。

std :: map 和 unordered_map 是实现定义的，但是标准需要某些Big-O复杂性，用于那些暗示那些内部实现的操作。

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;

with

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

the same as

typedef unordered_map<K, V> HashMap;

? (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?

解决方案

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;
       }
   }
}

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.

* 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

这篇关于unordered_map是否真的无序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！