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

[3dwelcome]

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

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

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

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

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

[xenme]

相同的一个文件，op 经过了 n 层 hash 之后还是没找到区别，最后死循环挂了

[jeesk]

要不用用谷歌的算法？ 记得谷歌好像有 hash 优化的算法

[3dwelcome]

@documentzhangx66

"你说的 bitmap 是什么？"

就是 https://en.wikipedia.org/wiki/Bitmap 里的标准定义，a bitmap is a mapping from some domain to bits.


@xenme
"相同的一个文件，op 经过了 n 层 hash 之后还是没找到区别，最后死循环挂了"

不会的，只要 hash 算法把数据打散到足够随机分布，冲突概率是能用公式计算出来的。参见 https://en.wikipedia.org/wiki/Birthday_problem

[binux]

@3dwelcome 你不存原数据，怎么知道冲突的时候，其实数据就真的是一样的？

[timpaik]

我有一个 A 文件的 hash ，你给我了 B 文件，但它俩 hash 相同。那么它俩是一个东西呢 还是应该继续 hash ？（假设我原本只有 A 这一个文件）

[documentzhangx66]

@3dwelcome

你怎么用 bitmap ？

[3dwelcome]

@timpaik
@binux

这个没办法，这个算法的大前提就是数据预处理。只有 A 和 B 集合都是已知的，才能进行 bitmap 构建。


@documentzhangx66

“你怎么用 bitmap ？”
每一次 hash 函数一次过后，生成结果都是一个个桶，每层会限定桶的大小，对结果取模。

然后 bitset 数组，每个 bit 偏移对应的就是桶 ID 号。bit 内容 1 和 0 ，表示当前层的 hash 算法里，有没有两个元素 hash 后占用同一个桶，也就是当前层有没有内部冲突。

如果没有冲突就直接返回，说明当前层 hash 函数结果，对于本元素是唯一值。

[XhstormR02]

@3dwelcome show me ur code

[binux]

@3dwelcome 所以你这个 hashmap 是只写不读的？

[aima]

@binux 哇确实 一针见血

[3dwelcome]

@binux "所以你这个 hashmap 是只写不读的？"

不理解是什么意思。

既然预处理 hash 没有冲突，那确实可以不用保存原始文件，可以用来大数据快速查找，用法和实时添加数据的普通 hashmap 不太一样。

[rpman]

又是我最喜欢的计算机民科环节

[3dwelcome]

@rpman "又是我最喜欢的计算机民科环节"

我这个算法实测下来每元素额外占用 5bit ，能做到完美无冲突。国外大佬的算法能优化到每元素 3bit 左右。

[binux]

@3dwelcome 那查询的时候 hash 匹配上了，你怎么知道它是匹配还是冲突？
别告诉我查询数据集也是预处理过的啊，那样你干嘛还要解决数据冲突？预处理出来一个不冲突的 hash 算法不就行了。

[3dwelcome]

@binux 可是完美 hash 的定义，就是数据预处理啊。

参见 https://en.bitcoinwiki.org/wiki/Perfect_hash_function ，国外大佬最优能达到 2bit 一个元素，算法比这个复杂很多。

[aima]

@3dwelcome 那就不算 hashmap 算法了吧？所以其实是个利用 hashmap 的搜索算法？如果已知数据了那可用的算法应该不少吧 当然这个感觉也是可行的。都预处理了那干啥都可以了

[binux]

@3dwelcome perfect hash function 可没这要求，只有 In addition, if the keys are not the data and if it is known that queried keys will be valid, then the keys do not need to be stored in the lookup table, saving space.
https://en.wikipedia.org/wiki/Perfect_hash_function

就算你规定查询总是有效的，你这算法既不新，性能也不好啊。

[3dwelcome]

这段话的意思，是特指另外一个利用 lookup table 的完美哈希算法，是这类算法的鼻祖。
可是作者主页上提到，这类算法已经被时代所淘汰了，自己都不推荐用。
wiki 应该是很久没更新了。
我这里提到的算法，效率也没太大问题，多几个 bit 占用，原理应该是最简单最容易理解的。

[t1xLM63evRKUbpMh]

话不多，就给你一个链接 https://sortingsearching.com/2020/05/26/static-hashing.html.

当然这是 static case.

[Xs0ul]

试图总结一下楼主的算法，看看整理的对不对：
前提：需要查询的集合是有限并且已知的
算法：
1. 取某种 hash 算法 A ，对整个查询集应用一次这个 hash 算法 A 。假设这个 A 算法可能产生的值有 1000 种，那么需要一个对应大小的 bitmap ，用来记录每个 hash 在这个给定的查询集合上是否冲突。
2. 在 hash 算法合适的情况下，会有少量的冲突，这时候再取 hash 算法 B ，重复步骤 1 并产生一个新的 bitmap
3. 如此不停的重复直到无冲突

查询：
对某个 input X ，先应用 hash 算法 A ，查看对应的 bitmap A 是否有冲突，没有则可以直接用 hash map A ；否则再用 hash 算法 B ，查看对应的 bitmap B ，以此类推