什么散列方法在标准无序容器中实现？

Question

由于语言标准很少要求实现方法,我想知道C++标准库实现(libc ++,libstdc ++和dinkumware)使用的真实世界哈希方法是什么.

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

• 哈希与链接
• 通过除法/乘法进行哈希处理
• 通用哈希
• 完美散列(静态,动态)
• 使用开放寻址进行散列(线性/二次探测或双重散列)
• Robin-Hood哈希
• 布隆过滤器
• 杜鹃哈希

知道为什么选择特定方法而不是其他方法也是一件好事.

Answer 1

• libstdc ++:链接,只有两个表的大小,默认(如果它甚至是可配置的)重新加载的加载阈值是1.0,桶都是单独的分配.过时了.我不知道现状.
• Rust:Robin Hood,rehashing的默认负载阈值是0.9(开放寻址太多,BTW)
• Go:表格插槽指向5个(7？)插槽的"垃圾箱",不确定如果垃圾箱已满会发生什么,AFAIR它以vector/ ArrayList方式增长
• Java:链接,只有两个表的大小,默认负载阈值是0.75(可配置),桶(称为条目)都是单独的分配.在Java的最新版本中,超过某个阈值,链被更改为二叉搜索树.
• C#:chaining,buckets是从一个扁平的桶结构阵列中分配的.如果此数组已满,则以vector/ ArrayList方式重新进行(我认为是表格).
• Python:开放式寻址,具有自己独特的冲突解决方案(不是很幸运,恕我直言),只有两个表的大小,重新加载的负载阈值是0.666 ..(好).但是,插槽数据在单独的结构数组中(如在C#中),即哈希表操作触摸至少两个不同的随机存储器位置(在表和插槽数据的数组中)

如果描述中遗漏了一些点,并不意味着它们不存在,这意味着我不知道/记住细节.