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

[3dwelcome]

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

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

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

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

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

[3dwelcome]

@cs8425 “楼主一直说算法很简单怎没人听懂”

原理是很简单啊。

不懂是因为很多人压根就没想听懂。

[learningman]

我超，计算机民科。

[3dwelcome]

@learningman 民什么哦，你网上搜搜 no collisions perfect hash 一大堆结果。

都是少见多怪。

[learningman]

@3dwelcome 大哥你搜永动机也一大堆结果。
你这玩意儿意味着每加一个值到 map 里，hash 函数都可能要重新设计一下。数学上有意义，工程上没有。

[binux]

@3dwelcome minimal perfect hashing 和 perfect hashing 又是一个不同的问题。。
而且 perfect hashing 是加了限制条件的，和工程中用的 hashmap 又不是一样的问题。

即使针对 perfect hash 问题，你在主楼里也没说清楚问题描述。然后你的算法也不新，很多人随随便便都能想到。再者你也没有对算法进行抽象，不简练，你自己都没搞清楚这个算法的关键在哪。最后你不会用正确的工具描述分析这个算法，你没能拿出 code ，也无法分析时空复杂度。

我是没看出来这帖的目的是什么，被教育吗？

[3dwelcome]

@learningman 知道 GCC 这个编译软件吗？他就在用，github 镜像里你能搜到相关的完美哈希代码。

最常见场景，就是把已知一组字符串，映射成不重复的整型 ID 。类似 constexp ，编译器静态预处理字符串哈希，要比运行时动态处理哈希冲突，执行效率要高太多。

说工程上没有用，只不过你们平时写业务太多，没遇到罢了。

[3dwelcome]

@binux "描述分析这个算法，你没能拿出 code ，也无法分析时空复杂度。"

我自己写代码分析了，每个 key 平均占用 5bit 就是分析结果。

代码也懒得贴，除了你们一小部分人相信外。大部分人都以为我是在吹牛。

[DCELL]

贴个 benchmark ，或者 贴下专利；
如果没有，去写；
“代码也懒得贴” 我就当你放屁了哦。

[xuanbg]

hash 冲突理论上是不可避免的，但在实际的 hash map 中，由于数据是有限的，所以冲突也是有限的。只需要留出一定的空间用于对应冲突就行了。你要问预留空间真不够了怎么办？那就崩掉好了呀，还不允许崩溃了吗？崩掉后改代码，通过参数增加预留空间就好，根本没必要搞这么复杂的呀。

[yangyaofei]

如果"完美哈希" 存在, 我觉得我这个也是完美哈希:


``` python
global hash_table = list()
def put(obj ) -> int:
for(i, o in enumerate(hash_table)):
if o == obj:
return i
hash_table.append(obj)
return size(hash_table)
```

只要不 pop, 空间效率历史最高!

[yangyaofei]

不是说好了可以 markdown 的么.....

https://gist.github.com/yangyaofei/0d5e6a1170467e518d832334eddaa8b9

[learningman]

@3dwelcome 那是确定有限的集合啊，你工程上能找到这么个确定有限的玩意儿？
都有限了用啥 map ，常量不好吗

[unicorn1390]

@3dwelcome 代码也懒得贴 -----> "我确信我发现一种美妙的证法，可惜这里的空白处太小，写不下"

[ColinZeb]

@3dwelcome 认为你吹牛
1 是你逻辑不自洽
2 是你没贴代码
贴了代码说你吹牛不是不攻自破了吗

[luwill]

@3dwelcome 思想是一样的。 为什么不直接用 bloom filter 拦截呢？
bloom filter + hashmap ？

[Xs0ul]

像之前有人回复的，这个更像利用了 hash 的搜索算法。并且，这样的算法想要有实用性，得证明碰撞的概率够低，并且不同的 hash 算法碰撞还得足够独立的，不然就会多次冲突导致要添加很多层 bitmap 。

所以比较重要的部分是，如何选择 hash 的算法，而不是楼主描述的这个过程。举个例子，对于给定的查询集合，比如一堆文件，可以生成一堆 hash 函数：h(x), h(x+1), h(x+2)...，来试验怎么样的组合能在最少的次数完成这个多重 hash map 的构造。同时，hash 函数的值域越大，碰撞概率越低，但对应的 bitmap 需要的空间也越大，这里如何选择也是需要研究的。要有实用性，这些选择都应该能自动完成，但楼主提到的部分并没有讨论这些问题

[binux]

@3dwelcome 你有这个工夫，代码发出来不就完了

[documentzhangx66]

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

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


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

拿 MD5 举例：

md5( 123456 ) = 827ccb0eea8a706c4c34a16891f84e7b

md5( aabbccddeeffgghh ) = 12e95c254d1c532e0d55e765731d8f89

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

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

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


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

https //en.维基百科.org/维基 /Perfect_hash_function
上面这个 URL 触发了网站屏蔽，所以只能以这种形式发出来，大家应该都懂真实 URL 吧？

是把已知元素数量（无论是否数量为无限个）、已知每个元素的集合，映射成一个元素数量比率差不多的序列，当这个序列总体长度达到数学证明的最小约为 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 啊啊啊啊啊啊啊啊啊啊呸
..... ......

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

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

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