标准无序容器中实现了什么样的哈希方法？ [英] What hashing method is implemented in standard unordered containers?

问题描述

由于语言标准很少使用实现方法，我想知道C ++标准库实现（libc ++，libstdc ++和dinkumware）使用的现实世界哈希方法是什么。

如果不清楚，我希望答案是这样的方法：

• 哈希链接


• 按分区/乘法进行哈希


• 通用散列


• 完美散列（静态，动态） / li>
  
• 使用开放式寻址进行散列（线性/二次探测或双重散列）


• Robin-Hood散列


• 布鲁姆过滤器


• 杜鹃哈希

选择其他人也是一件好事。

解决方案

• libstdc ++：链接，只有两个表的大小，默认（如果它甚至是可配置的）重新加载的加载阈值是1.0，桶都是单独的分配。过期。我不知道现在的情况。


• Rust：Robin Hood，重新加载的默认加载阈值是0.9（打开寻址的BTW太多了）

Go：表格槽指向5（7？）槽的bins，不知道如果bin已满，AFAIR将在向量 / 方法

• Java：链接，只有两个表的大小，默认的加载阈值是0.75（可配置），桶所谓的条目）都是单独的分配。在最新版本的Java中，高于某个阈值，链条被更改为二叉搜索树。


• C＃：链接，桶是从平面数组的桶结构分配的。如果这个数组已经满了，那么在向量 / ArrayList 方式中重新抛出（与表相对应的表）。


• Python：打开寻址，具有自己独特的冲突解决方案（不是很幸运，IMHO），只有两个表的大小，重新加载的加载阈值是0.666 .. ）。但是，在一个单独的结构数组中的插槽数据（如C＃中），i。 e。哈希表操作触及至少两个不同的随机存储器位置（在表格和插槽数据阵列中）

如果某些点错过在描述中，并不意味着它们不存在，这意味着我不知道/记住细节。

Since language standards rarely mandate implementation methods, I'd like to know what is the real world hashing method used by C++ standard library implementations (libc++, libstdc++ and dinkumware).

In case it's not clear, I expect the answer to be a method like these :

• Hashing with chaining
• Hashing by Division / Multiplication
• Universal hashing
• Perfect hashing (static, dynamic)
• Hashing with open addressing (linear/quadratic probing or double hashing)
• Robin-Hood hashing
• Bloom Filters
• Cuckoo hashing

Knowing why a particular method was chosen over the others would be a good thing as well.

解决方案

• libstdc++: Chaining, only power-of-two table size, default (if it is even configurable) load threshold for rehashing is 1.0, buckets are all separate allocations. Outdated. I don't know current state of things.
• Rust: Robin Hood, default load threshold for rehashing is 0.9 (too much for open addressing, BTW)
• Go: table slots point to "bins" of 5(7?) slots, not sure what happens if bin is full, AFAIR it is growing in a vector/ArrayList manner
• Java: chaining, only power-of-two table size, default load threshold is 0.75 (configurable), buckets (called entries) are all separate allocations. In recent versions of Java, above a certain threshold, chains are changed to binary search trees.
• C#: chaining, buckets are allocated from a flat array of bucket structures. If this array is full, it is rehashed (with the table, I suppose) in a vector/ArrayList manner.
• Python: open addressing, with own unique collision-resolution scheme (not very fortunate, IMHO), only power-of-two table sizes, load threshold for rehashing is 0.666.. (good). However, slot data in a separate array of structures (like in C#), i. e. hash table operations touch at least two different random memory locations (in the table and in the array of slot data)

If some points missed in descriptions, it doesn't mean they are absent, it means I don't know/remember details.

这篇关于标准无序容器中实现了什么样的哈希方法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！