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

[3dwelcome]

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

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

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

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

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



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

[NeroKamin]

看起来不就是开放地址法吗

[3dwelcome]

@NeroKamin “看起来不就是开放地址法吗”

是递归暴力查找法，比如要给一万个字符串都分配一个 0 ～ 10000 的不重复整数 ID 。基本上需要循环 9 万次，才能找到完美哈希结果。

[3dwelcome]

回帖的时候又灵光一闪，可以不用暴力循环 9 万次。

hash 函数分两类，一种安全 hash ，比如 MD5 和 SHA1 。另外一类是非安全 hash ，比如 hashmap 里用的字符串 hash 。非安全哈希，可以根据 hash 的结果，去人为构建 hash 前的结果。所谓的 hash 碰撞攻击法。

于是，我确信我发现一种美妙的证法，免去暴力循环查找，可惜这里的空白处太小，写不下。

[mrgeneral]

> 同一个 key ，加了不同的盐后，计算出的哈希值是完全不一样的，既可以避免冲突

呃，hash 冲突是对不同的关键字可能得到同一散列地址，加盐一样冲突，只不过概率小而已。

[Co1a]

看了第一个帖子，感觉和我看的 cuckoo filter 论文有点类似？

[3dwelcome]

@mrgeneral
“呃，hash 冲突是对不同的关键字可能得到同一散列地址，加盐一样冲突，只不过概率小而已。”

昨天我也许和你一样的想法，现在我已经不那么想了。

加了盐后，就相当哈希于一个被设计修改过的 MD5 文件，想要发生碰撞或者不想发生碰撞，都是人为可控的。并不完全依赖概率。

[keith1126]

你这个的本质是，对于哈希冲突，额外记录了一些信息，用于加速查找。

类似地，就好比是直接记录下每个元素在哈希桶中的位置，查找的时候直接跳到那个位置，可以确保真正意义上的 O(1)，而非均摊的 O(1)。

那么，代价是什么呢？就是你额外用了 keyseed 这个数组来存所谓的 salt 。一是额外的空间消耗，但更主要的是，对于更加通用的数据类型，当你没法用一个 `vector<int>` 来存 salt 的时候，你该怎么存？比如，如果 key 的空间无限大，你这个 hashmap 如何模拟 std::map<string, int>？

[keith1126]

@keith1126 #7

总结一下，你这个的优化点在于，在建立哈希表之前，你已经预知了所有的 key ，所以可以把每个 key 对应的 salt 存在 vector<int> 里面，自然就可以避免所谓的冲突。但这并不现实。

[keith1126]

@keith1126 #8

如果还说的不够明显的话，你既然都用 keyseed 来存 salt 了，你直接用 keyseed 来存每个元素在 dataset 中位置岂不是更直接？查找的时候直接 dataset[keyseed[i]] 不是更快？还要啥哈希 🤣

[3dwelcome]

@keith1126 "在建立哈希表之前，你已经预知了所有的 key"

这种情况很常见的，比如搜索一本牛津英文字典，动态加入英文单词是很罕见的情况，大部分都是直接查询。

"如果 key 的空间无限大。...自然就可以避免所谓的冲突。但这并不现实。"

我猜你是指如果 KEY 是文件，处理 500 万个 500G 文件，哈希后肯定会发生冲突。这种也可以避免的，有一些 HASH 函数，拥有 incrementally 特型，也就是随着处理文件长度的增加，HASHVAL 大小也会同步增加。盐也可以同步递增。

但这又是一个延伸的话题，可惜这里的空白处太小，写不下。

[keith1126]

@3dwelcome #10

不想继续回复了，直接看 #8 吧

[3dwelcome]

@keith1126 "直接用 keyseed 来存每个元素在 dataset 中位置岂不是更直接？查找的时候直接 dataset[keyseed[i]] 不是更快？"

这里 keyseed 用数组保存，只是方便大家能看懂代码。最终是 mix 到原 key 里面的。

用的时候，直接用修改后的 key 来查，没有所谓的 ID 号。

[muzuiget]

hash 版本的永动机，用脚趾头都知道，表示如果 hash 的表示范围为 N ，如果原始数据有 N + 1 种情形，那必定产生一次碰撞。

你给原文加了 salt ，就产生了一个新原文，问题依然还是那个问题，碰撞还是会碰撞。

[3dwelcome]

@muzuiget "表示如果 hash 的表示范围为 N ，如果原始数据有 N + 1 种情形，那必定产生一次碰撞。"

你这说法不成立，hash 的表示范围肯定比原始数据要大。hash function 是个广泛的概念，并不是指某些特定函数。

比如 MD5 装不下 500 万个文件，那么换成 SHA256 也许就可以。总有更大结果的 hash 函数，这种通用函数叫 incrementally hash function 。

[muzuiget]

@3dwelcome “hash 的表示范围肯定比原始数据要大……那么换成 SHA256 也许就可以。”

你增大了 hash 值表示范围了，那我原始数据样本量一样可以增大，我的原始数据可以取值 SHA256 的表示范围，再加一个 SHA512 长度的值，保证让你至少碰撞一次。

两者可以互相这么增大下去，最终结果 hash 值和原始值表示范围一样了。

也就是，一个原始数据的无碰撞 hash 值就是它自己本身，但这还叫算是 hash 吗？

[3dwelcome]

@muzuiget "我的原始数据可以取值 SHA256 的表示范围，再加一个 SHA512 长度的值，保证让你至少碰撞一次。"

并不是的，完美哈希是预处理，也就是一切数据，都是在可控范围内。

碰撞的概率不仅仅是和 KEY 大小有关系，和数量也有关系。你哪怕一个 KEY 是几百 G 的文件，只要文件总数量没上去，用 MD5 照样可以完美表达。

[muzuiget]

唉，概念理解都不在频道上。

[3dwelcome]

@muzuiget

我知道你指的是范围，可是预处理就意味着我的 hash 值表示范围，永远可以比你数据提供的最大范围还要大。

你要问怎么可能，这就是 incrementally hash function 的属性。一个可增变哈希函数，是可以被针对性构造的，你想要表示多大的范围都可以，并不是 MD5 那种定死截断类函数。

现实中，往往数据范围都是极其有限的。盐（种子）的加入，也能人为去避免碰撞，能发生碰撞的，就不叫完美哈希了。

[kiwi95]

在计算机编程领域，如果你没有深厚的理论知识就觉得自己发现了不得了的东西，一般都是你自己理解错了。因为数学理论的发展已经远远远远远超过一般程序员的理解范围了，很难存在这么明显的理论漏洞

[LeeReamond]

我觉得一楼对比效率的图意义不大，毕竟 hashmap 实现的上细节也很丰富，不可一概而论。看了 LZ 之前两个帖子，应该就是传统算法遇到 hash 碰撞则按链表方式保存，二级搜索采用逐个对比，lz 觉得二级搜索可以再加一层 hash ，以此类推。不过从普遍情况讲，google 开源 cityhash 已经是十多年前的事了，哈希发展到 2022 年，快速哈希算法本身效率和碰撞率都很低，普遍应用场景中碰撞本身是少数，所以二级索引中使用全文读生成二级哈希效率会比直接位对比快吗？我看不尽然，举例中使用的 md5 和 sha1 之类的成本极高的算法更不现实了，生产中也没见过这么用的。

再一个如果是从数理逻辑上针对无穷输入的情况设计普遍适用模块，逐位对比当然是永远不会出 bug 的，但是多层哈希法无法保证一定不会出现某对数据所有哈希值相同的情况，哈希算法需要人为设计是有限的，数据是无限的 ，完美看起来反倒没有现在通用方案完美。