V2EX › 3dwelcome 的所有回复 › 第 13 页 / 共 155 页

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

1 ... 9 10 11 12 13 14 15 16 17 18 ... 155

❮

❯

2022 年 4 月 19 日

回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap。

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

不理解是什么意思。

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

2022 年 4 月 19 日

回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap。

@timpaik
@binux

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

@documentzhangx66

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

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

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

2022 年 4 月 19 日

回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap。

@documentzhangx66

"你说的 bitmap 是什么？"

就是 https://en.wikipedia.org/wiki/Bitmap 里的标准定义，a bitmap is a mapping from some domain to bits.

@xenme
"相同的一个文件，op 经过了 n 层 hash 之后还是没找到区别，最后死循环挂了"

不会的，只要 hash 算法把数据打散到足够随机分布，冲突概率是能用公式计算出来的。参见 https://en.wikipedia.org/wiki/Birthday_problem

2022 年 4 月 18 日

回复了 3dwelcome 创建的主题 › 算法 › 链表快还是数组快？

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

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

2022 年 4 月 18 日

回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap。

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

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

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

2022 年 4 月 18 日

回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap。

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

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

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

2022 年 4 月 18 日

回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap。

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

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

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

2022 年 4 月 18 日

回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap。

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

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

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

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

2022 年 4 月 18 日

回复了 3dwelcome 创建的主题 › 算法 › 链表快还是数组快？

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

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

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

2022 年 4 月 18 日

回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap。

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

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

2022 年 4 月 18 日

回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap。

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

2022 年 4 月 18 日

回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap。

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

2022 年 4 月 18 日

回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap。

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

2022 年 4 月 18 日

回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap。

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

2022 年 4 月 18 日

回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap。

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

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

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

2022 年 4 月 18 日

回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap。

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

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

2022 年 4 月 18 日

回复了 3dwelcome 创建的主题 › 算法 › 链表快还是数组快？

@msaionyc

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

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

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

2022 年 4 月 18 日

回复了 3dwelcome 创建的主题 › 算法 › 链表快还是数组快？

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

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

2022 年 4 月 18 日

回复了 MTMT 创建的主题 › 问与答 › 大家怎么面对工作压力

不加班就没有压力了。

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

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

2022 年 4 月 18 日

回复了 3dwelcome 创建的主题 › 算法 › 链表快还是数组快？

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

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

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

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

1 ... 9 10 11 12 13 14 15 16 17 18 ... 155

❮

❯