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

[3dwelcome]

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

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

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

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

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



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

[3dwelcome]

这样说吧，任意两个文件在 MD5 计算后，碰撞的概率是 1.47*10-29 次方。

由于完美哈希导入了盐这个属性，那么新的碰撞概率就是绝对的 0 ，这就是“完美”的含义。

[wdhwg001]

一般来说，我们对于这种症状，孔子是比较委婉的，他说思而不学则殆。

现代人是比较不委婉的，比如我一般把这种奇思妙想称为民间科学家。

并且，我有点在意的是，这种情况持续多久了？医生怎么说？

[leimao]

楼主的算法只能用于特殊场景。请不要和 Hashmap 相比。

[3dwelcome]

@LeeReamond "毕竟 hashmap 实现的上细节也很丰富"

我查了一下，好象 stl 是用链表加红黑树结构来处理碰撞的情况，速度肯定不慢。

发这个帖子，也就是觉得无碰撞的字符串哈希很有意思，"完美哈希"这个词在我看来，很雅致。

晚期强迫症患者的救星。

[vacua]

@3dwelcome 0 要拿理论推导啊，加个盐就成 0 了，没有概率学公式的完美一律是伪科学

[leimao]

我这么跟你说吧，要是我的内存可以无限大，我都不需要 Hash ，key value 直接做内存地址。你这个算法怎么跟我的比？

[binux]

你查找的时候都知道 keyseed[id] ，结果的 id 都已经知道了还查询什么劲啊，直接 dataset[id] 岂不更快。

[leimao]

“完美”这两个字需要数学来支撑，而且很多时候数学告诉你没法完美。你这个内存就用的比 Hashmap 多，哪里来的完美？而且这么跟你说吧，你无法通过换种子或者换 Hash 函数来保证新的 Hashed value 和之前的没有冲突，数学上不支持的话咱还是低调一点。

[binux]

@3dwelcome 你怎么把 keyseed mix 到原 key 里？ 你查询的时候谁帮你 mix ？比如说一个字典，文章还不能直接写英文单词了？还得 mix 你的 keyseed ？
既然你可以 mix keyseed ，你干嘛不直接 mix dataset 呢？

[3dwelcome]

@vacua "0 要拿理论推导啊，加个盐就成 0 了，没有概率学公式的完美一律是伪科学"

可能你不信，但是"完美"这点，我确实是有依据的。

很多人觉得 hash 只是散列作用，不确定散列后数据是否发生碰撞，也不清楚内部原理。但是我发现，一些特定 hash 函数，只要处理的数据在表达范围内，仅仅只是 reorder ，重排序了数据顺序，并不会对数据范围造成损伤。

换言之，也就是主楼代码里那个 seed 或者说盐，是 100%存在完美解的。

[3dwelcome]

@binux "比如说一个字典，文章还不能直接写英文单词了？"

不 mix 也可以，那就和普通的完美哈希算法一样，做成 lookup table 保存在内部呗。

我是觉得 seed 和 key 绑定在一起，用起来更方便顺手。比如编译进程序内部字符串资源查找，肯定不需要用户输入。

[leimao]

请还是直接用我的 key value 直接做地址的算法吧

[3dwelcome]

@leimao "而且这么跟你说吧，你无法通过换种子或者换 Hash 函数来保证新的 Hashed value 和之前的没有冲突，数学上不支持的话咱还是低调一点。"

我发现你们对 hash 函数的运行机制都是一知半解。实在不行我就再发一贴，这样下去，都快变成连续剧了。

你可以看一下这篇文章： https://www.jandrewrogers.com/2019/02/12/fast-perfect-hashing/

[binux]

@3dwelcome 你都有 lookup table 了，还要你这个 hashmap 干嘛？用户输入不带 seed ，key => seed 的过程不就是一个查找的过程，怎么你还要用另一个“完美无冲突”hashmap 解决吗？
这就好像你发明一个永动机，需要一个电扇吹一样。

[panelatta]

别乱想了，我直接按你的思路帮你整个比你这个好得多的：
搞两层哈希表，第一层随便用什么 hash 函数都行，我们给他安排 k 个桶，对任意第 0 <= i < k 我们都给它安排一个独立的第二层哈希表；对于第 i 个桶里的所有 key ，我们从一个确定范围的函数空间 V 里随机选择一个 hash 函数，保证它能对这个桶里的所有 key 是完美 hash （比如对 key 是整数的情况，随机取 a, b 和素数 p 就能构造一个 hash 函数 f(x) = (ax + b) % p ），然后这个桶直接记录上这个 hash 函数就行了；这样你的 dataset seedset 都不用了，还不用在这又臭又长地选种子，不比你这个好多了？
而且你的加盐就“完美”的说法还只是瞎想，我这个直接给你选一个完美函数，一次随机不行再来一次，不比你这个直接？
口嗨谁不会啊？

[3dwelcome]

@binux "你都有 lookup table 了，还要你这个 hashmap 干嘛？"

市面上有很多的 perfect hash 算法，各种各样，所有无一例外，都是需要附加额外 lookup table 作为算法数据支撑。

这就是所谓的预处理，如果预处理不产生辅助数据，那就变成 hashmap 这种实时算法了。

[3dwelcome]

@panelatta "口嗨谁不会啊？"

你这算法性能不够的，查询性能也是一个很重要的指标。

上个贴所以弃贴，又重新开了一个，就是因为 5bit 的算法查询性能拉跨。

要超越 stl 的 hashmap ，是一件很困难并值得骄傲的事情。所以我才又发帖。

[leimao]

@3dwelcome 咱啥也别说好吧。Hashmap 本来就不需要理解 specific 的 hash 算法。我告诉你我的 key value 直接做地址也是一个 perfect hash function 。

[leimao]

@3dwelcome 你都这么说了，那请你就别和 Hashmap 比。我说了，你们的东西不是一个东西。

[leimao]

@3dwelcome 我帮你联系一下 C++ standard committee 里的人，正好我认识几个。