@hitmanx 别人不知道，我代码里很多这种“缝合数组”。

原因就是在长度增加同时，能避免旧数组失效，这特性对我挺重要的。

@est “除了故意构造，真实世界不存在 md5 或者 sha1 冲突的两个天然的文件。”

第一，存 MD5 值太大了，但很多人理解不了，我只能以常见的 MD5 来举例。基本上 java/linux 的 hash 函数，都不可能选用 MD5 算法.

第二，生日悖论实验告诉我们，千万不要小看数据量上去后，潜在冲突的概率。编程不能靠直觉，要靠公式。

@documentzhangx66 说了存原数据不现实。

硬盘文件对比的情况下，只能算一次文件 hash ，而且无论数据量多少，必须保证算出来的文件 hash 之间没有冲突。这就意味着需要预处理。

预处理的结果就是一组 bitmap 数据集合。有了这个集合的辅助，数学函数定义就失效了，你让我怎么回复嘛。

@013231 "用新的散列算法算一遍不是比逐字節對比更慢嗎？"

还是那句话，使用场景不一样。你比对两块硬盘上所有文件是否有内容重复，比对 hash 是最简单直接的方法。

把两块硬盘硬凑一起，挨个字节对比，有点不现实。

@mrgeneral “因为算法变了，这个时候 sha1(A)=sha1(C) 又冲突了怎么办？”

漏斗过滤有个特性，第一层元素最多冲突最多。

往后每下一层的元素数量，都要远远少于上一层的。

只要元素变少了，冲突的概率就自然会下降很多。

@Mystery0 "况且多个小数组怎么拼起来？用指针链起来？"

用二维指针就可以，比如 int** array 就能把数组缝合起来。或者更简单的形式，用 vector<int*>这种。

你面向硬件编程，把大数组切分成小数组是必然的。操作系统是有 4k 之类内存区块概念的，分配的数组不能太大，不能太小，性能才最好。

@XiLingHost "Talk is cheap. Show me the code"

建个和所有元素相等长度的 bitset 。
查询时，bit 为 1 就用 MD5, bit 为 0 就用 SHA1 。那么简单的原理，上 CODE 没必要吧。

@duke807 如果遍历本地硬盘所有文件，py 的 dict 肯定不能保证没有哈希冲突，我这个就可以。

@newtype0092 保存结果就仅仅是 bitmap 里的一个 bit 而已，代表着需要用第几层 hash 算法。基本不占多少存储空间。

@cxtrinityy 应用场景不一样，java 的 hashmap 冲突后，会进一步对比原始数据。
我这种完美 hash ，保证没冲突，就自然不需要保存原始数据了。

我说一下使用场景，比如用户上传海量的图片，你单用 md5 或者 sha1 ，都不能保证完美无冲突。
有冲突的话，只能挨个字节对比两张图片是否一模一样，效率是很低的。
这时候，引入砂砾过滤层，如果 md5 有冲突，就把 bitmap 设置成 1 ，那么 hash 算法就会切换到 sha1 。还冲突，就再升一层变成 sha256 ，直到完全无冲突。

@XiLingHost "所以你的查找需要用原始数据来查原始数据......?"

这里的 bitmap 相当于 AI 网络的训练数据，对于可预测的原始数据，是最精确的。

如果没有事先插入元素的话，map 是查不到 key 的。

@oneisall8955 查找算法和插入一样的，先用多层 bitmap 前置过滤一次，有可能会计算多次 hash 函数。

计算后得到不冲突的沙砾层数，这时候对应的 map ，在当前层内查找 key ，就是无冲突的。

@msaionyc

“需要重新申请空间，原来的 delete 掉。”， 旧空间也可以不删除的，多个子数组拼成一个大数组就可以不用删掉了。

“数组必须要提前申请内存空间，没用满时等于空了的部分是浪费了的。”
这句话也不对，操作系统对于应用程序申请了，但没有实际使用的内存，是不会真实分配的。只有第一次赋值或者初始化时，才会分配物理内存。

总的来说，还是链表占用内存更多。一个 next 指针需要 8 字节，对比一个 1M 大小的数组，链表比数组要整整多出 8M 额外内存。

@msaionyc 内存空间利用率具体指什么？没太搞懂，按理说数组比链表要节约内存。

链表你还要多一个 next 指针才行。

不加班就没有压力了。

加班很晚，状态不好的时候，写的代码大概率是需要返工的。

还不如先吃饱，睡好。在白天状态好的时候，听听背景歌曲，静下心，慢慢堆代码。

@msaionyc “我一直认为，发表这种“xxx 过时”，“a 不如 b”这种话题应该非常慎重，尤其是技术方面”

以前是面向对象编程，现在时代变了，是面向硬件编程。

举个例子，有个叫 Odin 的新编程语言（ http://odin-lang.org/），这个就是为了优化硬件，而诞生的编程语言，所谓的 Data-Oriented Language 。

你可以照本宣科，表示大学书本数据结构里，链表 O(1)插入性能好。可真实高性能编程中，SoA （ array of structures ）的地位，要远高于 AoS 。你说为什么，就是因为 SoA 设计成面向 CPU 编程，有更好缓存亲和性，自然就有更好的性能。

@msaionyc "这时如果是在增删条件比较多的情况下难道也要用数组替换链表吗？"

不回复一些楼，又不是代表我持反对意见。

我只想讨论大概率使用场景。你如果写一个只有中间 insert 的对比场景，那肯定是链表比数组更占优势。

链表在数据结构里地位，和数组一样重要，我没怀疑这点。发帖的主要目的，只是想说明在现代 CPU 硬件设计上，对链表不友好，对数组更友好。相同场景下，优先考虑数组，仅此而已。

@northernlights0 "比如要通过线性表实现一个队列，有大量的 push_back, pop_front 操作，就肯定是链表占优"

可以分而治之的，把一个超级大链表，转换成 N 个固定大小的数组集合。只对小数组进行局部操作，感觉也不会太慢。

理论上大家都知道链表插入快，而实际上 CPU 设计的高速缓存，天然就对数组有极强的亲和性。

而且在大部分情况下，查询的操作频率，要远远高于插入和删除。