c++ unordered_map 碰撞处理,调整大小和重新散列

标签 c++ c++11 hash hashmap unordered-map

我还没有阅读 C++ 标准,但这就是我觉得 c++ 的 unordered_map 应该如何工作。

  • 在堆中分配一个内存块。
  • 对于每个 put 请求,对对象进行哈希处理并将其映射到此内存中的空间
  • 在此过程中,通过链接或开放寻址来处理冲突。

我很惊讶我找不到太多关于 unordered_map 如何处理内存的信息。是否有 unordered_map 分配的特定初始内存大小。如果假设我们分配了 50 个 int 内存并最终插入了 5000 个整数会怎样?

这会发生很多冲突,所以我相信应该有一种类似于重新散列和重新调整大小的算法,以在达到一定水平的碰撞阈值后减少碰撞次数。由于它们是作为成员函数显式提供给类的,因此我假设它们也在内部使用。有这样的机制吗?

最佳答案

With every put request, hash the object and map it to a space in this memory

很遗憾,这并不完全正确。您指的是 开放寻址封闭散列 数据结构,这不是 unordered_map 的指定方式。

每个 unordered_map 实现都将一个链表存储到存储桶数组中的外部节点。这意味着插入一个项目将始终分配至少一次(新节点),如果不是两次(调整存储桶数组的大小,然后是新节点)。

不,这根本不是为最常见的用途实现 HashMap 的最有效方法。不幸的是,unordered_map 规范中的一个小“疏忽”几乎都需要这种行为。要求的行为是元素的迭代器在插入或删除其他元素时必须保持有效。因为插入可能会导致桶数组增长(重新分配),所以一般不可能有一个迭代器直接指向桶数组并满足稳定性保证。

unordered_map 如果您将昂贵的复制项目存储为您的键或值,则它是一种更好的数据结构。这是有道理的,因为它的总体设计是从 Boost 的预移动语义设计中提炼出来的。

Chandler Carruth (Google) 在他的 CppCon '14 演讲中提到了这个问题 "Efficiency with Algorithms, Performance with Data Structures" .

关于c++ unordered_map 碰撞处理,调整大小和重新散列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31098123/

相关文章:

c++ - 与 asio::async_read 一起使用的正确模式是什么?

c++ - 如何强制编译器显示隐式构造函数

ruby - 减少哈希值

php - PHP 的 libsodium 不工作

python - 如何使用 Python 计算文件系统目录的哈希值?

C++:错误:无效使用限定名

c++ - 为什么 std::bitset<5>{}[0] 不是 constexpr?

c++ - C++模板特化成员函数的定义

c++ - 如何用 Cython 包装 C++ 类?

c++ - 我该如何创建一个类,以对对象进行类型删除,直到调用了一个函数,而没有事先指定可能的函数列表?