@mingl0280 然而\r 并不会把旧数据给清掉。还要加上清除控制符。

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

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

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

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

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

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

@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 一个元素，算法比这个复杂很多。