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

[3dwelcome]

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

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

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

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

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

[yulon]

你连 HashMap 的实际应用经验都没有，不管用什么算法都要存原数据，不然遍历的时候要怎么办

[season8]

1. 数据集必须是已知的，因为要预处理。
2. 数据集必须是固定上限的，因为不能插入（无法判断冲突数据是否是原数据），可以查询和删除。
3. 数据必须是去重的，有重复数据，必定重复 hash

比起标题所说，更像是如何使用 hashmap 去对 “已知有限的去重数据” 建立 “唯一索引”。

[qgymib]

思来想去，楼主的问题应该在于计算机理论基础知识与数学概率这两项的基础没有学好。之所以不存在完美 hash 的推论很简单：
1. 无论多少层 hash 函数，只要是摘要算法，其结果一定是存在长度上限的
2. hash 碰撞概率计算公式为（ n 为元素个数，d 为取值空间）:
```
p(n,d) = 1 - e ^ ( (-n(n-1)) / (2d))
```

如上两个条件严格证明了在摘要算法中，永远不可能存在完美 hash 函数（楼主的多层 hash 算法本质上也是一个 hash 摘要算法）。

[3dwelcome]

@season8
"2. 数据集必须是固定上限的，因为不能插入（无法判断冲突数据是否是原数据），可以查询和删除。"
插入和查询操作极为相似，虽然没存原始数据，资源 ID 号还是保留着，可以依次找回原始数据。

新插入情况，基本上平均计算 5 次 hash ，就能把新元素顺利插入 bitmap 里。

"3. 数据必须是去重的，有重复数据，必定重复 hash"
这要看具体情况。原数据长度是不受不限制的，只有 hash function 后的 hash value 才有长度限制这一说法。可以针对原数据属性，自己构造一个变长结果的 hash function 。这样只要原始数据不重复，hash value 就能保证不重复。

对于完全一致的原始数据，肯定没有保存两份的必要。

[3dwelcome]

@qgymib 你忽略了一个重要前提，元素数量上限是固定的。只要数量固定，hash function 足够散列，碰撞概率就能固定，就有完美 hash 。

[yeyuefeng]

有意思，但不可取

[luwill]

给答出 bloom filter 的同学一点掌声👏👏👏

[jabari]

这是个很朴素的想法, 简称民科, 并且也不新颖, 也没有严格的证明.

[zmal]

多少有点民科的味道了。
hashmap 本意是用来解决数组和链表的访问效率问题。有冲突就 hash ，算法更复杂不说，相比链表法效率低多少？ hash 算法相比的 equal 效率降低多少？
理论会存在 N 层 hash 后依然会冲突的 key ，你怎么解决？继续 hash 变成无限递归爆栈吗？

[3dwelcome]

@luwill bloom filter 通常用一个 bit 位表示多种可能性，这里一个 bit 就只表示一个含义 = 当前层 hash 元素有没有冲突。没有其他的可能性了。

@zmal
"理论会存在 N 层 hash 后依然会冲突的 key ，你怎么解决？"
这里的 hash function 是预处理函数，不是你理解的通常意义上，MD5 之类的强制截断函数。

举个例子，处理最大 256 个字节的 string 数据，只需要 256bit hash value 表示就可以。但是处理无数个 2G 的文件，用 sha256 都不一定能保证无冲突。所以预处理的 hash function ，计算后的长度是动态的，是根据分析原始数据后，才确认的长度。

而且每往下一层，元素数量指数级递减，冲突概率也会递减。并不会出现你说的无限循环。最下层桶里就几个元素，又怎么可能发生冲突。

[zmal]

“而且每往下一层，元素数量指数级递减，冲突概率也会递减。并不会出现你说的无限循环”
哈？哈？哈？冲突概率递减会变成数学意义上的 0 吗？无限趋近于 0 是 0 吗？只要不为 0 就还要考虑冲突。
计算机底层都是数学，你看到的经典数据结构都是发了论文经过严格论证的。
思而不学则殆。
莫回复我，看着糟心。

[3dwelcome]

@zmal 那我说直白点，最底层就是无冲突。

最后筛选后，就几个元素，分一大堆 bucket ，会发生冲突才奇怪。

[3dwelcome]

@jabari "这是个很朴素的想法,"

KISS 才是我追求的。计算机算法里代码复杂化是常态，原理朴素能到让大家能理解，也是很不容易的事情。

何况都这样了，很多人还不理解。

[yangyaofei]

这很民科, 概念都不对,补补数据结构和什么叫哈希吧.......

[secondwtq]

隔壁还有个 NIO 的，你们能不能一个一个来，V 站 Trending 都快不够用了 ...

[mingl0280]

别回这个楼主了，就一民科，让它去看数学它又不肯去……

[cs8425]

插个眼看楼主表演
之前把 wasm 当唯一的神
无视应用场合跟局限就知道有多少料了...

[3dwelcome]

@yangyaofei 书本上是没有完美哈希，wiki 上有的。

我来普及一下知识吧，最初的形式完美 hash ，就是单纯指设计一个 hash function ，让产生的 hash value 完全不冲突。参见 http://burtleburtle.net/bob/hash/perfect.html

但是这个算法有个很大问题，就是同时要附加一个巨大的 lookup table ，很占空间。于是有人发明出类似的改版，类似我这种，多几个 bit 来替换查找表。最终效果差别不大，预计算量能降低很多。

最后原始作者主页也不维护了，久而久之，perfect hash 就从最初的一个函数，演化成了一整套算法。

实际应用的话，最常见的就是编译里 constexp 优化了，能保证字符串 hash 后，int value 不重复不冲突。

[3dwelcome]

@mingl0280 "让它去看数学它又不肯去……"

数学上 MD5 就是会截断的。完美 hash 应用里，hash value 是可以随着数据量，无限长的。也就是两者 hash value 必须保证不冲突。

两者概念都不一样，是你们自己搞混了。

[cs8425]

楼主一直说算法很简单怎没人听懂
要求 show 个 code 又不要
真的很简单的话
花一点时间弄个 code demo/benchmark 让大家见识一下不就好了
怎偏偏一直不弄呢?