问题标签 [hash-function]

问题

对于所有成员数据类型都已经具有良好的 std::hash 特化的用户定义类型，在 std::unordered_map 或 std::unordered_set 的第三个模板参数中使用 std::hash 的好的特化是什么？

对于这个问题，我将“好”定义为易于实现和理解、相当有效且不太可能产生哈希表冲突。良好的定义不包括任何关于安全的陈述。

Google 的现状

目前，两个 StackOverflow 问题是 Google 搜索“std hash specialization”的第一名。

第一个，如何为无序容器中的用户定义类型专门化 std::hash::operator()？, 解决打开 std 命名空间和添加模板特化是否合法。

第二，How to special std::hash for type from other library基本上解决了同样的问题。

这就留下了当前的问题。鉴于 C++ 标准库的实现为标准库中的基本类型和类型定义了散列函数，那么将 std::hash 专门用于用户定义类型的简单而有效的方法是什么？有没有一种组合标准库实现提供的散列函数的好方法？

（感谢 dyp 编辑。） StackOverflow 上的另一个问题解决了如何组合一对哈希函数。

其他谷歌结果没有更多帮助。

Dobbs 博士的这篇文章指出，两个令人满意的散列的异或将产生一个新的令人满意的散列。

这篇文章似乎是从知识上讲的，暗示了很多东西，但细节却很轻。它与 Dobbs 博士在第一个示例中的简短评论中的文章相矛盾，他说使用 XOR 组合散列函数会导致生成的散列函数很弱。

因为 XOR 应用于任何两个相等的值会导致 0，所以我可以看到为什么 XOR 本身很弱。

元问题

一个合理的答案解释为什么这个问题是无效的并且一般不能回答也是受欢迎的。

I'd like to have an unordered_map with a struct, that I'd like to use as the key, of multiple std::set< std::string >.

I see that a custom hash function is required and that a string can have std::hash applied; however, I cannot determine what should be returned to satisfy the purpose of the hash function of these sets for an unordered_map.

How should a custom hash function return?

我必须实现这个哈希函数

“h(k)=((A*k)*mod(2^32))rsh(32-r)”。

其中 rsh(32-r) 是右移一个数字。我怎样才能做到这一点。我很困惑，因为我不知道它会右移多少次？我的PDF中也没有提到它。还有表格大小=m=2^r。因此 r=logm。**必须使用此哈希函数。

我正在构建一个哈希表，其中的键是一个电话号码（这里有一些）：

条目数将为 200、2000、20000 和 2000000，并且条目是唯一的。

关于桌子的大小，我正在关注这个答案。

char我将电话号码存储为's数组。我注意到所有的数字都以 69 开头，所以我可以在散列函数中跳过它们。

我的尝试是取数字的总和并对哈希表中的单元格数进行取模，但（在纸面上）这似乎是一个坏函数，因为有很多冲突。

我应该如何修改我的哈希函数以获得更好的结果（更少的冲突）？

正如这个问题的评论中所建议的，我将其用作哈希函数：

atol()但是，我所有的电话号码都得到了相同的结果！我删除了前两位数字（在我的情况下，它们对于所有数字都是相同的）并得到不同的结果（当然检测到碰撞......）。

为什么会这样？

检查这个的输出：

只是一些例子：

元问题：如果可以建议更好的方法来获得更好的哈希函数，我仍然愿意更改我的代码。

编辑：

strtol()给出相同的结果。

我迷失在我一直在研究的这个话题上。在我的课堂上，我们正在实现自己的哈希集类。因此，我们有一个底层数据结构，如向量或数组，并使用散列函数来快速确定元素是否在集合中。那是我不遵循的部分。哈希函数将如何用于此确定？

我正在通过模板创建一个 HashTable 类。虽然，在处理字符串或任何数字数据类型（更多 - 所以只是整数）时，我似乎无法找到保持模板性质的方法。只要 HashKey 是字符串类型，这就是我拥有的代码。

有没有办法让它使用类似的东西工作

这里有什么帮助吗？

参考论文Bundle Min Hashing for Logo Recognition：

假设我们有包 {2,5,18,444,678} 和 {2,5,79,368,841}，词汇量为 1M。如果我们每个包只有 1 个草图，那么我们是否只需要 1 个散列函数，它将 1M 整数确定性地散列为 [0,1] 中均匀分布的值。每次调用的散列函数必须有固定的种子。对于 4 幅草图，我们只需要具有 4 个种子的相同散列函数。想法是否正确？

或者我们可以从集合（捆绑）中随机选择一个数字作为最小哈希词，因为它们代表集合的随机排列？

论文中需要实现散列函数的任何参考？

MurmurHash3 可以完成这项工作吗？

我知道我可以通过这样的 for 循环（参见代码），我也可以以相同的方式添加到数组中，但有没有更快的方法。我不想使用任何其他 java API，因为我想练习数组。使用散列函数可以让我更快地存储变量，然后更快地找到某个单词吗？

编辑：问题是当使用 10,000+ 字时，延迟增加大于 1ms

谢谢 ：）

我正在寻找一个整数数组的哈希函数，每个数组包含大约 17 个整数。HashMap 中有大约 1000 个项目，我希望计算尽可能快。

我现在对这么多可供选择的哈希函数感到困惑，我注意到它们中的大多数都是为具有不同字符的字符串而设计的。那么有没有专为只有数字的字符串设计的哈希函数呢？

谢谢你的耐心！