极客观点
项目管理
HarmonyOS
基于哈希表的容器是非常快的关联数组（例如 unordered_map ， unordered_set ）。
它们的性能高度依赖于用于为每个条目创建索引的散列函数。随着哈希表的增长，元素会一次又一次地重新哈希。
指针是简单类型，基本上是唯一标识对象的 4⁄8 字节值。问题在于，由于几个 LSB 为零，因此使用哈希函数作为结果的地址效率不高。
例子：
struct MyVoidPointerHash {
size_t operator()(const void* val) const {
return (size_t)val;
}
};
更快的实现是丢失一些位：
struct MyVoidPointerHash2 {
size_t operator()(const void* val) const {
return ((size_t)val) >> 3; // 3 on 64 bit, 1 on 32 bit
}
};
后者在使用散列集和映射的大型应用程序上产生了 10-20% 的性能提升，其中包含数以万计的元素，这些元素经常被构建和清除。
有人可以为散列指针提供更好的方案吗？
该功能需要是：
- 快速地！并且必须很好地内联。
- 提供合理的分配，允许罕见的冲突。
更新 - 基准测试结果
我运行了两组测试，一组用于 int* 和一个大小为 4KB 的类指针。结果非常有趣。
我使用 std::unordered_set 用于所有测试，数据大小为 16MB，在单个 new 调用中分配。第一个算法运行了两次，以确保缓存尽可能热并且 CPU 全速运行。
设置：VS2013 (x64)、i7-2600、Windows 8.1 x64。
- VS2013默认哈希函数
- 哈希1：
return (size_t)(val); - 哈希2：
return '(size_t)(val) >> 3; - 哈希3（@BasileStarynkevitch）：
uintptr_t ad = (uintptr_t)val; return (size_t)((13 * ad) ^ (ad >> 15)); - 哈希4（@Roddy）：
uintptr_t ad = (uintptr_t)val; return (size_t)(ad ^ (ad >> 16)); - 哈希5（@egur）：
代码：
template<typename Tval>
struct MyTemplatePointerHash1 {
size_t operator()(const Tval* val) const {
static const size_t shift = (size_t)log2(1 + sizeof(Tval));
return (size_t)(val) >> shift;
}
};
测试 1 - int* ：
- VS2013 默认耗时 1292ms
- Hash1 耗时 742ms
- Hash2 耗时 343ms
- Hash3 耗时 1008ms
- Hash4 耗时 629ms
- Hash5 耗时 350 毫秒
测试 1 - 4K_class* ：
- VS2013 默认耗时 0.423ms
- Hash1 耗时 23.889 毫秒
- Hash2 耗时 6.331ms
- Hash3 耗时 0.366ms
- Hash4 耗时 0.390ms
- Hash5 耗时 0.290ms
更新2：
到目前为止，获胜者是模板化哈希 (Hash5) 函数。各种块大小的最佳速度性能水平。
更新 3： 为基线添加了默认哈希函数。事实证明它远非最佳。
原文由 egur 发布，翻译遵循 CC BY-SA 4.0 许可协议
让这个问题搁置一段时间后，我将发布迄今为止我最好的指针哈希函数：
它对各种块大小都具有高性能。
如果有人有更好的功能，我会改变接受的答案。