构建一个完美无冲突的 hashmap。

[3dwelcome]

首先，hashmap 是把一个很长的字符串，散列成固定长度。由于原始数据是无限长，而散列值长度基本是固定的，所以无法避免 hash 冲突。

但是，我们可以通过设计一个前置过滤函数，让一个 hashmap 变成一组 hashmap.

类似砂石过滤里的多层滤网原理。

第一层是粗砂砾，也就是计算每个元素，如果 hash 函数并无冲突，就保留在第一层。其余元素自动流到第二层。
第二层是中砂砾，元素被过滤一次，数量减少了。用第二个 hash 函数来过滤，明显会减少冲突。还有冲突，就流到第三层。
第三层是细砂砾，以此类推，直到所有元素被处理完成。

这样就可以避免 hashmap 出现碰撞的情况了。当然真实场景里，并不需要一组 hashmap ，可以优化到多层 bitmap 数据+一个 hashmap 来保存和查询结果。

[3dwelcome]

@XiLingHost "Talk is cheap. Show me the code"

建个和所有元素相等长度的 bitset 。
查询时，bit 为 1 就用 MD5, bit 为 0 就用 SHA1 。那么简单的原理，上 CODE 没必要吧。

[GeruzoniAnsasu]

来，我特意在 CSDN 上找的：

[chaoschick]

@3dwelcome 有冲突的概率太低了，耗时可以接受

[dqzcwxb]

无冲 hash ×
多重 hash √

[013231]

@3dwelcome 用新的散列算法算一遍不是比逐字節對比更慢嗎？

[mrgeneral]

呃，看起来就是二次 hash ，只不过换了存储空间，但是二次冲突怎么解？

假设第一层是 md5：md5(A)=md5(B)，冲突了。

所以 A 和 B 要放在第二层 sha1 ，因为算法变了，这个时候 sha1(A)=sha1(C) 又冲突了怎么办？

继续往下？下一层算法又不一样了，和其他元素又有冲突可能性。

[LaTero]

存在单射 f:X->Y 意味着 cardX≦cardY ，对有限集来说就是 Y 的元素个数至少要与 X 相等，那这样为何不直接用原数据作 key?
另外如楼上所说，散列再算一遍一般是比逐字节比对要慢的。

[3dwelcome]

@mrgeneral “因为算法变了，这个时候 sha1(A)=sha1(C) 又冲突了怎么办？”

漏斗过滤有个特性，第一层元素最多冲突最多。

往后每下一层的元素数量，都要远远少于上一层的。

只要元素变少了，冲突的概率就自然会下降很多。

[hbdh5]

有太多槽不知道该怎么吐

[3dwelcome]

@013231 "用新的散列算法算一遍不是比逐字節對比更慢嗎？"

还是那句话，使用场景不一样。你比对两块硬盘上所有文件是否有内容重复，比对 hash 是最简单直接的方法。

把两块硬盘硬凑一起，挨个字节对比，有点不现实。

[keepMyselfClam]

建议了解一下 Hash Array Mapped Trie

[interim]

...

[est]

> 我说一下使用场景，比如用户上传海量的图片，你单用 md5 或者 sha1 ，都不能保证完美无冲突。

赌 5 毛钱你既没有海量图片的经验，也没有 md5 冲突的经验。

实际上，由于图片编码格式的原因，自然产生的 .jpg .webp .gif .png 压根不可能一模一样 md5 或者 sha1 。除非你去搞 appending attack 。

除了故意构造，真实世界不存在 md5 或者 sha1 冲突的两个天然的文件。

[Buges]

来个 poc ，附上对比标准库实现的 benchmark ，不然很难判断你的思路是否可行。

[documentzhangx66]

1. 27 楼已经给出 Hash 不可能无冲突的数学定义，楼主没回复，我估计楼主看不懂。

2. 计科本科大一的数据结构书籍，已经给出了 * 多 * 种 * Hash 冲突方法，22 楼贴了一部分方法。楼主的方法，其实就是其中一种，而且只是其中一种。注意，这只是本科大一的知识。

计算机基础理论已经发展了一百多年，建议楼主多看书。

[3dwelcome]

@documentzhangx66 说了存原数据不现实。

硬盘文件对比的情况下，只能算一次文件 hash ，而且无论数据量多少，必须保证算出来的文件 hash 之间没有冲突。这就意味着需要预处理。

预处理的结果就是一组 bitmap 数据集合。有了这个集合的辅助，数学函数定义就失效了，你让我怎么回复嘛。

[3dwelcome]

@est “除了故意构造，真实世界不存在 md5 或者 sha1 冲突的两个天然的文件。”

第一，存 MD5 值太大了，但很多人理解不了，我只能以常见的 MD5 来举例。基本上 java/linux 的 hash 函数，都不可能选用 MD5 算法.

第二，生日悖论实验告诉我们，千万不要小看数据量上去后，潜在冲突的概率。编程不能靠直觉，要靠公式。

[Mirage09]

学而不思则罔，思而不学则殆

另外 op 你知道你下这种“完美”的结论是需要数学证明的么，要不只能叫猜想

[mingl0280]

……OP 你最好去补一下数学。

[documentzhangx66]

@3dwelcome

你说的 bitmap 是什么？