许多来源称
但如果负载因子很低,使用开放地址法会造成巨大的内存浪费,因为我必须在内存中分配Bucket_number * sizeof(Record)字节,即使大多数桶不包含记录。
所以我的问题是,LLVM选择开放地址法而不是分离链接的原因是什么?仅仅因为通过缓存局部性获得速度优势吗?
谢谢:)
编辑:C++11标准对
另一个问题:
顺便问一下,
llvm::StringMap
中使用的哈希冲突处理方法开放地址法不稳定。当负载因子较高时(这是可以想象的),开放地址法被认为比链接法差。但如果负载因子很低,使用开放地址法会造成巨大的内存浪费,因为我必须在内存中分配Bucket_number * sizeof(Record)字节,即使大多数桶不包含记录。
所以我的问题是,LLVM选择开放地址法而不是分离链接的原因是什么?仅仅因为通过缓存局部性获得速度优势吗?
谢谢:)
编辑:C++11标准对
std::unordered_set
和std::unordered_map
的要求意味着使用链式方法处理哈希冲突,而不是开放地址法。为什么LLVM选择了一种无法满足C++标准的哈希冲突处理方法?是否有任何特殊用例需要使用llvm::StringMap来保证这种偏离?(编辑:此幻灯片将LLVM的几种数据结构与STL的相应结构进行了性能比较)另一个问题:
顺便问一下,
llvm::StringMap
如何保证在增长时不会重新计算键的哈希值?
手册中说:
哈希表增长时不会重新计算已存在于表中的字符串的哈希值。
unordered_map
或set
。它并不试图满足特定std
容器的要求... - Yakk - Adam Nevraumont