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

都是少见多怪。

我写过，加起来没几行代码。

V2 贴代码会乱，我就贴图片了。

https://i.imgur.com/GQ2vqxD.jpg

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

原理是很简单啊。

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

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

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

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

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

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

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

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

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

@justrand 哈哈，我发过几乎一样的回帖。

https://i.imgur.com/vnRtO8x.jpg

只要技术不断在积累，就不能算是平庸。

怕就怕躺在舒适圈不肯出来，慢慢被新技术淘汰。

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

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

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

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

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

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

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

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

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

第一，代码会随着时间的推移，变得越来越乱。这和架构选择没有必然关系，和新需求的不断加入，有直接关系。我称之为代码熵增。

第二，减少熵增最佳实践，就是定期重构。

@lifanxi “你似乎有个误解，认为 std::vector 可以通过拼接串联小数组的方式来进行优化”

不以长短论英雄。缝合小数组(deque)也是数组里的一个分支。

13cm 和 18cm 哪个更强？不好说的。

链表还有一个最大的问题，是不好维护。你数组还能设个越界报错，新手链表用不好，指针就在天上乱飞。

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

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

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

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

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

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

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

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

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

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

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

不理解是什么意思。

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

@timpaik
@binux

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


@documentzhangx66

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

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

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