构建一个完美无冲突的 hashmap（上图附代码)

[3dwelcome]

继上篇，上文的 5bit 占位算法，平均查一次需要计算 5 次哈希函数，效率不行。

我在想，既然数据库用户密码哈希都能加盐，那么 hashmap 优化也是可以加的，同一个 key ，加了不同的盐后，计算出的哈希值是完全不一样的，既可以避免冲突，也能提升查找效率。

具体算法还是很简单，以查找一个英文字典举例：

1. 分配一个比数据量要大一点的桶数组。
2. 依次遍历原始字符串，把当前字符串 hash 后的结果，保存到对应的桶 ID 里。
3. 如果目标桶被占用了，那么换一个盐或者种子 ID ，一直到找到空余的桶。
4. 依次处理完所有数据。

这样就构建结束，由于加了盐，那么查找 key 的时候，也需要同时把 key 对应的种子 ID 也附带传进去。



我用 VS2022 写了一点点性能测试代码，对一个字典查找 8 千万次，在 release 下编译。
如下图所示，由于完美哈希没有一个冲突，查找效率明显要比标准的 stl 好很多。

[zlbruce]

如果你要和 hashmap 做对比：
1. 请用你的 hashmap 统计一下某篇文章的词频
2. 请告诉我这些字符串中有没有 3dwelcome 字符串

为什么计算机的民科比较少，就是因为代码一出来，就现行了。

[zlbruce]

另外要比对性能也需要对等的来对比：用 unordered_map 查询时输入是什么，用你的 hashmap 就应该输入是什么。

[yangyaofei]

@documentzhangx66 #55 也不能这么说, 谁初中的时候不中二一下. 比如声称看懂了相对论这种. 到了能看懂洛伦兹变换什么的的年纪, 再真的看一下当年的论文(甚至仅仅是狭义的), 也不基本上会闭嘴了...

天才 7 岁能看懂, 但是天才不会来这儿发帖, 而是直接顶刊顶会发一波,<无冲突完美哈希>, 怎么着也是 ACM 顶会发一波, 或者 SCI 一区发一篇(承认格局有点小), 要是复杂度还是哈希的复杂度的话, 图灵奖不也可以么☺️

[3dwelcome]

@zlbruce “用 unordered_map 查询时输入是什么，用你的 hashmap 就应该输入是什么。”

你是指多了一个 seed 参数？这算法一开始，seed 是保存在内部的桶里。后来我觉得反正都预处理了，没必要把辅助数据隐藏那么深，就直接提取到最外面了。

seed 和 key 一一对应，这是设计原则。不论 seed 是封装到类内部，或者暴露在外层，都是同一个意思。

[szq8014]

@muzuiget 你举例子不太直观，你就说，班里有 13 个小孩，必定有 2 个人出生月份一样，哈哈

[3dwelcome]

@szq8014 不要误导吃瓜群众，有 13 个小孩，一年就必定有 13 个月份。完美哈希里，桶的大小，是根据数据总量提前分配的。

不可能出现 13 个小孩均分 12 月份的情况。

[VYSE]

@3dwelcome #60 unordered_map 查询是 key(假设 string)获取 value, 你算法查询不光 key 还要 key 对应的 seed(代码里 keyseed[id]), 而根据 key(string)查 id 还得每次到 keydata 里数组遍历查询? 性能测试时候包含数组反查 id 了么?

[3dwelcome]

@VYSE 肯定包含数组反查了，这点不会取巧的。
况且这个测试数据还是很保守的，激进的话，连数组反查都不需要。dataset 本质上就是对于原始 key 顺序的重新排序。同样可以通过预处理，把 dataset 消灭。
查询性能只是算法一部分，无冲突才是亮点。可以完美避免链表操作。

[VYSE]

@3dwelcome #64 既然每次查询你得从 keydata 数组反查 key 得到所在的 id 索引, 再建一个相同顺序的 valuedata 的 vector, 同一 id 直接拿 value 不就行了? 何必做 hashmap?

[3dwelcome]

@VYSE 这问题在上面讨论过了。

完美哈希目的不是为了获取 value id ，而是为了设计一个能把 key 转换到无冲突的 hash 函数。

[binux]

@3dwelcome > 肯定包含数组反查了，这点不会取巧的。
不，你没有。你绝对写不出一个 find(string) 函数。

[3dwelcome]

@binux "不，你没有。你绝对写不出一个 find(string) 函数。"

不，我可以。这是一回事情，稍稍改一下构建算法，把 seed 放到桶内，完全可行。

具体算法如下：
1. 先 hash 一次 key ，得到桶的 ID
2. 如果目标桶被占用了，在桶上标记一次，表示这个桶是需要 seed 来辅助计算免冲突的。同时换个 seed 尝试，重新一次 hash ，直到找到空余桶。
3. 重复第二步骤，处理完所有 key 。

[3dwelcome]

查询的时候，算法也是一样。

1. 用先 hash 一次 key ，得到桶的 ID
2. 根据桶的 ID ，得到 key 对应的 seed ，再次用 seed hash 一次，结果就能免冲突。

就是 seed 保存在桶内部，还是和 KEY 一起保存在外部的问题。我个人是完全偏向保存到外部的，预处理数据最终都是要存盘的。

[binux]

@3dwelcome 那你写啊，写完再测一遍性能，我赌比微软的 hashmap 慢。

[tool2d]

@binux 微软的 hashmap 也不是万能的，字符串 hash 算法是开源的，那就意味着 hashmap 是可以被人为构造攻击的。

当一大堆 hash 碰撞挤在一堆，微软的 hashmap 就会退化到链表和红黑树，性能急剧下降。

完美哈希就没这个情况，完美解决了碰撞问题。

[binux]

@tool2d 哪跟哪啊，楼主写的哈希根本就不对，和完美哈希就没关系。

[NeroKamin]

@documentzhangx66 看了你的我才明白 OP 的想法

[chanchan]

"不要误导吃瓜群众，有 13 个小孩，一年就必定有 13 个月份。完美哈希里，桶的大小，是根据数据总量提前分配的。"
根据总量提前分配,那理想情况下准备一个数组就好了,也不需要什么 hash

[vacua]

@3dwelcome 什么时候代码算理论依据了？排序算法、搜索算法的时空复杂度、优缺点不都是通过数学归纳等一系列数学工具来评价？可行性和可验证性是两码事

[3dwelcome]

@binux “那你写啊，写完再测一遍性能，我赌比微软的 hashmap 慢。”

写第三版去除暴力算法的时候，发现还是没办法把 seed 弄到内部。

原因是当两个 key 文件无限长的时候，为了免冲突，内部 hash 算法的结果也会无限延长，这显然不合理。

最理想的是 hash 长度，只和数据总量挂钩。这样就只能用额外 seed 来区分有相同短 hash 结果，但 key 不同的情况了。