unordered_map真的是无序的吗？

发布于 2024-09-08 07:59:29 字数 646 浏览 6 评论 0原文

我对“unordered_map”这个名字感到非常困惑。顾名思义，这些键根本没有排序。但我一直认为它们是按哈希值排序的。或者这是错误的（因为名字暗示它们没有排序）？

或者换句话说： 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 < k2 也没有 k2 < k1。您需要使用 multimap 并覆盖相等检查。）

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

原文

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?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

可遇━不可求 2024-09-15 07:59:30

在回答您编辑的问题时，这两个片段根本不相等。 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;
       }
   }
}

显然，这是一个严重的简化，真正的实现会更高级（例如，支持调整存储桶数组的大小，可能使用树结构而不是存储桶的链表），等等），但这应该让您了解如何无法以任何特定顺序取回值。有关详细信息，请参阅维基百科。

* 从技术上讲，std::map 和 unordered_map 的内部实现是实现定义的，但标准要求操作具有一定的 Big-O 复杂性意味着那些内部实现

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

回复收藏 0 原文