gpt4 book ai didi

c++ - std::unordered_map 是如何存储和比较其键值以实现无序快速访问元素的?

转载 作者:太空狗 更新时间:2023-10-29 20:20:35 29 4
gpt4 key购买 nike

据我所知,std::unordered_map 用于快速访问元素。这是通过存储和比较 key 哈希而不是 key 本身来实现的。另外,无序意味着其中的元素没有排序。但快速访问元素需要对项目进行排序,以便能够使用二进制搜索找到请求的项目。

  • 这是否意味着 unordered_map 中的项目是根据它们的顺序排序的哈希键和导致 unordered_map 的唯一原因比映射访问元素更快的是比较哈希值是通常比比较键值快得多?
  • 如果是这样,在 unordered_map 和 map 之间进行选择取决于 key 。我说得对吗?
  • 最后一个问题是为什么 unordered_map 没有得到比较模板参数就像 map 一样? unordered_map 如何仅通过相等运算符比较 key 哈希?

    template <class Key,
    class T,
    class Compare = less<Key>,
    class Alloc = allocator<pair<const Key,T> >
    > class map;

    template <class Key,
    class T,
    class Hash = hash<Key>,
    class Pred = equal_to<Key>,
    class Alloc = allocator< pair<const Key,T> >
    > class unordered_map;

最佳答案

快速元素访问确实需要某种形式的排序。 Unordered_map之所以这样称呼,是因为排序对人类来说可能没有意义,并且在您添加或删除元素时可能不会保持稳定。

unordered_map不比 map 快因为一对一比较哈希比一对一比较任意对象更快。它更快,因为它根本不需要比较。这就是为什么它不需要 compare 的原因模板参数。

典型的unordered_map实现是一个哈希表。哈希表主要是键值对的常规数组,它使用巧妙的技巧来帮助您快速找到要查找的元素。

一个理想的散列函数是均匀分布的:如果你要从任何对象中随机选择一个散列,hash % N 的值对于某些整数 N 应该大致一致(假装 modulo bias 不存在)。如果你选择N要成为键值对数组的大小,您可以使用 hash(key) % size作为快速查找的数组索引。

由于散列值应该是均匀分布的,不同的对象通常会有不同的索引,所以这样做通常对您有利。但是,hash(key) % N 仍然有可能对于两个对象来说是一样的。在这种情况下,哈希表需要处理冲突:有多种策略,但所有策略通常都在属于同一哈希桶的键内进行线性搜索(出于这个原因,哈希表也需要包含键,而不仅仅是键的哈希)。这就是为什么哈希表的最坏情况访问时间为 O(n) 的原因,并且它突出了拥有良好哈希函数的重要性。

在某些情况下,这可能是更喜欢 map 的原因在 unordered_map , 作为 map 的访问性能(O(log n)) 是非常可预测的。

另外,随着哈希表中被占用的桶数的增加,发生碰撞的几率也会增加。通常,由于这个原因,哈希表的桶数多于元素数,这意味着它在“浪费”空间以提高效率。

关于c++ - std::unordered_map 是如何存储和比较其键值以实现无序快速访问元素的?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50073376/

29 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com