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

[3dwelcome]

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

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

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

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

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

[wd]

....

[casparchen]

...

[blindpirate]

......

[oneisall8955]

请问 map.get(key)怎么实现？

[PureWhiteWu]

STFC

[XiLingHost]

根据鸽笼原理，要让无限长的原始数据的 hash 无冲突，你的 hash 算法的结果空间就必须是无限大的，那么这还有什么 hash 的意义吗

[3dwelcome]

@oneisall8955 查找算法和插入一样的，先用多层 bitmap 前置过滤一次，有可能会计算多次 hash 函数。

计算后得到不冲突的沙砾层数，这时候对应的 map ，在当前层内查找 key ，就是无冲突的。

[XiLingHost]

@3dwelcome 所以你的查找需要用原始数据来查原始数据......?

[3dwelcome]

@XiLingHost "所以你的查找需要用原始数据来查原始数据......?"

这里的 bitmap 相当于 AI 网络的训练数据，对于可预测的原始数据，是最精确的。

如果没有事先插入元素的话，map 是查不到 key 的。

[cxtrinityy]

嗯, 你这不能叫完美 hash 吧?
我没记错的话, java 的 hashmap 不就是这样么, 相同 hash 会放到一个数组里而已, 而不是新建一个 hashmap

[3dwelcome]

我说一下使用场景，比如用户上传海量的图片，你单用 md5 或者 sha1 ，都不能保证完美无冲突。
有冲突的话，只能挨个字节对比两张图片是否一模一样，效率是很低的。
这时候，引入砂砾过滤层，如果 md5 有冲突，就把 bitmap 设置成 1 ，那么 hash 算法就会切换到 sha1 。还冲突，就再升一层变成 sha256 ，直到完全无冲突。

[3dwelcome]

@cxtrinityy 应用场景不一样，java 的 hashmap 冲突后，会进一步对比原始数据。
我这种完美 hash ，保证没冲突，就自然不需要保存原始数据了。

[newtype0092]

"这时候，引入砂砾过滤层，如果 md5 有冲突，就把 bitmap 设置成 1 ，那么 hash 算法就会切换到 sha1 。还冲突，就再升一层变成 sha256 ，直到完全无冲突。"
也就是你的每个文件都要保存所有 hash 算法的结果，才能让后来比较的文件碰撞时可以不断“升级”算法，比较高一层的 hash 结果。。。

[duke807]

建立 op 看一下 python 的 dict 實現

[3dwelcome]

@newtype0092 保存结果就仅仅是 bitmap 里的一个 bit 而已，代表着需要用第几层 hash 算法。基本不占多少存储空间。

[3dwelcome]

@duke807 如果遍历本地硬盘所有文件，py 的 dict 肯定不能保证没有哈希冲突，我这个就可以。

[onehao28]

.....

[XiLingHost]

要不你搞个 PoC 出来给我们看看吧
Talk is cheap. Show me the code

[icyalala]

......
Perfect Hashing 是个已有概念，但和你描述的东西没有任何关系

[creedowl]

第一眼还以为是布隆过滤器。。
就 OP 说的比较图片（文件）冲突的场景，我了解到有一种方法是保存整个文件的 hash 和其中部分分块的 hash （阿里云盘）