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

[3dwelcome]

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

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

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

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

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



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

[binux]

@3dwelcome 你可以有额外数据，但不能以 id 为 key 。
否则我只要一个改动，能把你现在的性能翻倍。
查找：findid = id.

[panelatta]

@3dwelcome 说明你没看懂呗，要查数据的话两次 hash 都是已知的，直接 O(1)。
还是多学学习吧，有空找 perfect hash function 的英文网页 yy ，不如买本算导从头学起。

[leimao]

我觉得这个帖子的标题非常夸张且误导人，我们不应该继续跟进。

[leimao]

这让我想起来做 Deep Learning 的人有很多就是光换种子，然后拿个数据集做测试，发现用某个种子能够超越被外界认可的 SOTA 算法，然后出来吹了一番。

[3dwelcome]

@leimao "发现用某个种子能够超越被外界认可的 SOTA 算法，然后出来吹了一番。"

我也没想着吹，这个帖子的算法和上个帖子的，都是一拍脑袋，就能想出来的超简单方法。

只是上个帖子里，大家都觉得我在吹牛，这才不得已发一点代码，作为对比测试。

要不然光吃瓜群众的口水，都能把给我淹没了。

[Vitor]

我觉得 8L9L 已经把问题说的很清楚了

[icyalala]

你是想要这个吗: Perfect Hash Function Generator
https://www.gnu.org/software/gperf/manual/gperf.html

[icyalala]

如果你目标只是 Perfect Hash ，那上面这类工具已经有很长时间了。
如果你更关心性能，那可以看看前几年的 Google swisstables 或者 Facebook 的 F14 Hash Table ，甚至只用开放地址+Robin Hood hashing 性能就足够比 unordered_map 高很多了。

[dqzcwxb]

当初你出来我是没有签字同意的

[XiLingHost]

发了一点代码，大家发现真的是在吹牛

[documentzhangx66]

1.哈哈哈哈哈哈，我认真看了一下楼主两篇帖子，以及他贴出来的国外大佬的文章，以及维基百科的词条...

我突然发现，楼主说的 hash ，与我们常用的 hash ，根本就不是一回事...

[documentzhangx66]

2.我们所说的常用 hash ，比如 MD5 、SHA1 等，是把一个数量未知可有限可无限、每个元素长度也未知且可有限可无限的集合，映射成数量已知、每条元素长度也是固定大小的集合，这样必然会有冲突。

拿 MD5 举例：

md5( 123456 ) = 827ccb0eea8a706c4c34a16891f84e7b

md5( aabbccddeeffgghh ) = 12e95c254d1c532e0d55e765731d8f89

md5( 啊啊啊啊啊啊啊啊啊啊呸 ) = 0fffbe633a0e4060545775e84788d648

左侧包含元素 123456 的集合，元素数量可能只有 10 个，也可能是无限数量。

而右侧包含元素 827ccb0eea8a706c4c34a16891f84e7b 的 MD5 结果集合，按照 MD5 的定义，元素数量最多只能是 2 的 128 次方个，而且每个元素的长度是固定的 128bit ，或 32 个 16 进制。

[documentzhangx66]

3.但楼主所说的完美 Hash：

https://en.维基百科.org/维基 /Perfect_hash_function

是把已知元素数量（无论是否数量为无限个）、已知每个元素的集合，映射成一个元素数量比率差不多的序列，当这个序列总体长度达到数学证明的最小约为 1.44 Bit per key 时，就是最小完美 Hash （文中的 Minimal perfect hash function ），但目前已知算法，只能达到 1.56 Bit per key 。

举个例子，以下的一张表 Table ，由 2 列 组成。第一列是从 1 开始自增且唯一的主键，第二列是长度与内容都看上去像是随机，但其实是已知的字符串集合：

ID （ Key ） Content
1 123456
2 aabbccddeeffgghh
3 啊啊啊啊啊啊啊啊啊啊呸
..... ......

[documentzhangx66]

现在的情况是，已知右边列的内容，已知左右两列肯定有一种对应关系，但不知道左边的具体值。现在需要通过一个算法，从右侧字符串，计算出左侧 ID：

123456 -> Minimal_perfect_hash_function( x ) -> 1

aabbccddeeffgghh -> Minimal_perfect_hash_function( x ) -> 2

啊啊啊啊啊啊啊啊啊啊呸 -> Minimal_perfect_hash_function( x ) -> 3

这特喵的就是楼主想说的东西。

Minimal_perfect_hash_function 与 我们常见的 MD5 、SHA1 这类哈希，根本是不同的东西，只是名称中都包含了 HASH ，于是大家先入为主地，以为楼主在说 MD5 、SHA1 之类的主流哈希算法。楼主这种其实更像是根据 value 反推 ID key 的 index 查找算法。

最关键的一点是，楼主说的这种 Minimal_perfect_hash_function ，当第二列 Content 的长度是无限时，计算出来的 ID 列的结果集的长度也是无限的！而 MD5 、SHA1 ，就算 MD5( x )，x 集合是无限的，但计算出来后，结果集的长度是有限的。这就是最大的区别。

Perfect_hash_function 是单射，

MD5 、sha1 不是单射！

[documentzhangx66]

另外，楼主发明的这玩意，我并不关心，因为工程中如果出现这种情况，我直接用 Oracle 整一张自增 ID 主键的表，一 一对应就行了，或者直接对 Content 集合来个 gzip -9 。

还要去找半天楼主说的这种单射函数？

吃饱撑的？游戏不好玩吗？？

[vacua]

@3dwelcome 有依据就拿出来啊

[Mutoo]

有点像布隆过滤器

[3dwelcome]

@vacua "有依据就拿出来啊“

主楼的代码就是依据，你可以试试，用 seed 递增，看看 crc32 后的结果，会不会产生相互冲突。

一个随机数生成器，产生结果不可预测，值有可能会重复。

但 hash 不一样，只要输入值不超出表达范围，是可以进行逆向 hash 的还原操作。

[iosx]

哈希不可避免冲突的，但可以让一个桶里放多个元素，也就是增大桶深。比如交换芯片 FDB 表设计有用双桶设计。4K 个表，桶身为 2 ，可以存 8K 条 FDB 。

[iosx]

补充下，还有些交换芯片，会有一个副表。专门用来存储冲突的数据，一般很小，比如 256 或 1K 大小，顺序遍历即可。