这是一个创建于 936 天前的主题，其中的信息可能已经有所发展或是发生改变。
首先，hashmap 是把一个很长的字符串，散列成固定长度。由于原始数据是无限长，而散列值长度基本是固定的，所以无法避免 hash 冲突。
但是，我们可以通过设计一个前置过滤函数，让一个 hashmap 变成一组 hashmap.
类似砂石过滤里的多层滤网原理。
第一层是粗砂砾，也就是计算每个元素，如果 hash 函数并无冲突，就保留在第一层。其余元素自动流到第二层。
第二层是中砂砾，元素被过滤一次，数量减少了。用第二个 hash 函数来过滤，明显会减少冲突。还有冲突，就流到第三层。
第三层是细砂砾，以此类推，直到所有元素被处理完成。
这样就可以避免 hashmap 出现碰撞的情况了。当然真实场景里，并不需要一组 hashmap ，可以优化到多层 bitmap 数据+一个 hashmap 来保存和查询结果。
但是，我们可以通过设计一个前置过滤函数，让一个 hashmap 变成一组 hashmap.
类似砂石过滤里的多层滤网原理。
第一层是粗砂砾，也就是计算每个元素，如果 hash 函数并无冲突，就保留在第一层。其余元素自动流到第二层。
第二层是中砂砾，元素被过滤一次，数量减少了。用第二个 hash 函数来过滤，明显会减少冲突。还有冲突，就流到第三层。
第三层是细砂砾，以此类推，直到所有元素被处理完成。
这样就可以避免 hashmap 出现碰撞的情况了。当然真实场景里，并不需要一组 hashmap ，可以优化到多层 bitmap 数据+一个 hashmap 来保存和查询结果。
 |
1
wd 2022-04-18 18:02:10 +08:00 via iPhone
....
|
 |
2
casparchen 2022-04-18 18:20:07 +08:00 via iPhone
...
|
 |
3
blindpirate 2022-04-18 18:21:36 +08:00
......
|
 |
4
oneisall8955 2022-04-18 18:24:33 +08:00 via Android
请问 map.get(key)怎么实现？
|
 |
5
PureWhiteWu 2022-04-18 18:26:48 +08:00
STFC
|
 |
6
XiLingHost 2022-04-18 18:28:03 +08:00
根据鸽笼原理，要让无限长的原始数据的 hash 无冲突，你的 hash 算法的结果空间就必须是无限大的，那么这还有什么 hash 的意义吗
|
 |
7
3dwelcome OP @oneisall8955 查找算法和插入一样的，先用多层 bitmap 前置过滤一次，有可能会计算多次 hash 函数。
计算后得到不冲突的沙砾层数，这时候对应的 map ，在当前层内查找 key ，就是无冲突的。 |
|
8
XiLingHost 2022-04-18 18:31:57 +08:00
@3dwelcome 所以你的查找需要用原始数据来查原始数据......?
|
|
9
3dwelcome OP @XiLingHost "所以你的查找需要用原始数据来查原始数据......?"
这里的 bitmap 相当于 AI 网络的训练数据，对于可预测的原始数据，是最精确的。 如果没有事先插入元素的话，map 是查不到 key 的。 |
 |
10
cxtrinityy 2022-04-18 19:17:19 +08:00
嗯, 你这不能叫完美 hash 吧?
我没记错的话, java 的 hashmap 不就是这样么, 相同 hash 会放到一个数组里而已, 而不是新建一个 hashmap |
|
11
3dwelcome OP 我说一下使用场景，比如用户上传海量的图片，你单用 md5 或者 sha1 ，都不能保证完美无冲突。
有冲突的话，只能挨个字节对比两张图片是否一模一样，效率是很低的。 这时候，引入砂砾过滤层，如果 md5 有冲突，就把 bitmap 设置成 1 ，那么 hash 算法就会切换到 sha1 。还冲突，就再升一层变成 sha256 ，直到完全无冲突。 |
|
12
3dwelcome OP @cxtrinityy 应用场景不一样，java 的 hashmap 冲突后，会进一步对比原始数据。
我这种完美 hash ，保证没冲突，就自然不需要保存原始数据了。 |
 |
13
newtype0092 2022-04-18 20:23:17 +08:00
"这时候，引入砂砾过滤层，如果 md5 有冲突，就把 bitmap 设置成 1 ，那么 hash 算法就会切换到 sha1 。还冲突，就再升一层变成 sha256 ，直到完全无冲突。"
也就是你的每个文件都要保存所有 hash 算法的结果，才能让后来比较的文件碰撞时可以不断“升级”算法，比较高一层的 hash 结果。。。 |
 |
14
duke807 2022-04-18 20:28:12 +08:00 via Android
建立 op 看一下 python 的 dict 實現
|
|
15
3dwelcome OP @newtype0092 保存结果就仅仅是 bitmap 里的一个 bit 而已，代表着需要用第几层 hash 算法。基本不占多少存储空间。
|
|
16
3dwelcome OP @duke807 如果遍历本地硬盘所有文件，py 的 dict 肯定不能保证没有哈希冲突，我这个就可以。
|
 |
17
onehao28 2022-04-18 21:18:00 +08:00
.....
|
|
18
XiLingHost 2022-04-18 21:35:39 +08:00
要不你搞个 PoC 出来给我们看看吧
Talk is cheap. Show me the code |
 |
19
icyalala 2022-04-18 21:44:13 +08:00
......
Perfect Hashing 是个已有概念，但和你描述的东西没有任何关系 |
 |
20
creedowl 2022-04-18 21:49:39 +08:00
第一眼还以为是布隆过滤器。。
就 OP 说的比较图片（文件）冲突的场景，我了解到有一种方法是保存整个文件的 hash 和其中部分分块的 hash （阿里云盘） |
|
21
3dwelcome OP @XiLingHost "Talk is cheap. Show me the code"
建个和所有元素相等长度的 bitset 。 查询时，bit 为 1 就用 MD5, bit 为 0 就用 SHA1 。那么简单的原理，上 CODE 没必要吧。 |
 |
22
GeruzoniAnsasu 2022-04-18 22:04:02 +08:00  1
来，我特意在 CSDN 上找的：
 |
 |
23
chaoschick 2022-04-18 22:05:51 +08:00 via Android
@3dwelcome 有冲突的概率太低了，耗时可以接受
|
 |
24
dqzcwxb 2022-04-18 22:19:07 +08:00 1
无冲 hash ×
多重 hash √ |
 |
26
mrgeneral 2022-04-18 22:36:51 +08:00
呃，看起来就是二次 hash ，只不过换了存储空间，但是二次冲突怎么解？
假设第一层是 md5：md5(A)=md5(B)，冲突了。 所以 A 和 B 要放在第二层 sha1 ，因为算法变了，这个时候 sha1(A)=sha1(C) 又冲突了怎么办？ 继续往下？下一层算法又不一样了，和其他元素又有冲突可能性。 |
 |
27
LaTero 2022-04-18 22:44:32 +08:00 via Android
存在单射 f:X->Y 意味着 cardX≦cardY ，对有限集来说就是 Y 的元素个数至少要与 X 相等，那这样为何不直接用原数据作 key?
另外如楼上所说，散列再算一遍一般是比逐字节比对要慢的。 |
|
28
3dwelcome OP @mrgeneral “因为算法变了，这个时候 sha1(A)=sha1(C) 又冲突了怎么办？”
漏斗过滤有个特性，第一层元素最多冲突最多。 往后每下一层的元素数量，都要远远少于上一层的。 只要元素变少了，冲突的概率就自然会下降很多。 |
 |
29
hbdh5 2022-04-18 22:47:57 +08:00
有太多槽不知道该怎么吐
|
|
30
3dwelcome OP @013231 "用新的散列算法算一遍不是比逐字節對比更慢嗎？"
还是那句话，使用场景不一样。你比对两块硬盘上所有文件是否有内容重复，比对 hash 是最简单直接的方法。 把两块硬盘硬凑一起，挨个字节对比，有点不现实。 |
 |
31
keepMyselfClam 2022-04-18 23:03:16 +08:00
建议了解一下 Hash Array Mapped Trie
|
 |
32
interim 2022-04-18 23:11:56 +08:00
...
|
 |
33
est 2022-04-18 23:14:18 +08:00
> 我说一下使用场景，比如用户上传海量的图片，你单用 md5 或者 sha1 ，都不能保证完美无冲突。
赌 5 毛钱你既没有海量图片的经验，也没有 md5 冲突的经验。 实际上，由于图片编码格式的原因，自然产生的 .jpg .webp .gif .png 压根不可能一模一样 md5 或者 sha1 。除非你去搞 appending attack 。 除了故意构造，真实世界不存在 md5 或者 sha1 冲突的两个天然的文件。 |
 |
34
Buges 2022-04-18 23:16:36 +08:00 via Android
来个 poc ，附上对比标准库实现的 benchmark ，不然很难判断你的思路是否可行。
|
 |
35
documentzhangx66 2022-04-18 23:18:12 +08:00
1. 27 楼已经给出 Hash 不可能无冲突的数学定义，楼主没回复，我估计楼主看不懂。
2. 计科本科大一的数据结构书籍，已经给出了 * 多 * 种 * Hash 冲突方法，22 楼贴了一部分方法。楼主的方法，其实就是其中一种，而且只是其中一种。注意，这只是本科大一的知识。 计算机基础理论已经发展了一百多年，建议楼主多看书。 |
|
36
3dwelcome OP @documentzhangx66 说了存原数据不现实。
硬盘文件对比的情况下，只能算一次文件 hash ，而且无论数据量多少，必须保证算出来的文件 hash 之间没有冲突。这就意味着需要预处理。 预处理的结果就是一组 bitmap 数据集合。有了这个集合的辅助，数学函数定义就失效了，你让我怎么回复嘛。 |
|
37
3dwelcome OP @est “除了故意构造，真实世界不存在 md5 或者 sha1 冲突的两个天然的文件。”
第一，存 MD5 值太大了，但很多人理解不了，我只能以常见的 MD5 来举例。基本上 java/linux 的 hash 函数，都不可能选用 MD5 算法. 第二，生日悖论实验告诉我们，千万不要小看数据量上去后，潜在冲突的概率。编程不能靠直觉，要靠公式。 |
 |
38
Mirage09 2022-04-18 23:41:56 +08:00 via iPhone 1
学而不思则罔，思而不学则殆
另外 op 你知道你下这种“完美”的结论是需要数学证明的么，要不只能叫猜想 |
 |
39
mingl0280 2022-04-18 23:44:51 +08:00
……OP 你最好去补一下数学。
|
|
40
documentzhangx66 2022-04-19 00:01:27 +08:00
|
 |
41
xenme 2022-04-19 00:01:37 +08:00 via iPhone
相同的一个文件，op 经过了 n 层 hash 之后还是没找到区别，最后死循环挂了
|
 |
42
jeesk 2022-04-19 00:03:56 +08:00 via Android
要不用用谷歌的算法？ 记得谷歌好像有 hash 优化的算法
|
|
43
3dwelcome OP @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 |
 |
45
timpaik 2022-04-19 00:37:43 +08:00 via Android
我有一个 A 文件的 hash ，你给我了 B 文件，但它俩 hash 相同。那么它俩是一个东西呢 还是应该继续 hash ？（假设我原本只有 A 这一个文件）
|
|
46
documentzhangx66 2022-04-19 00:53:30 +08:00
|
|
47
3dwelcome OP @timpaik
@binux 这个没办法，这个算法的大前提就是数据预处理。只有 A 和 B 集合都是已知的，才能进行 bitmap 构建。 @documentzhangx66 “你怎么用 bitmap ？” 每一次 hash 函数一次过后，生成结果都是一个个桶，每层会限定桶的大小，对结果取模。 然后 bitset 数组，每个 bit 偏移对应的就是桶 ID 号。bit 内容 1 和 0 ，表示当前层的 hash 算法里，有没有两个元素 hash 后占用同一个桶，也就是当前层有没有内部冲突。 如果没有冲突就直接返回，说明当前层 hash 函数结果，对于本元素是唯一值。 |
 |
48
XhstormR02 2022-04-19 01:07:54 +08:00 via Android
@3dwelcome show me ur code
|
|
51
3dwelcome OP @binux "所以你这个 hashmap 是只写不读的？"
不理解是什么意思。 既然预处理 hash 没有冲突，那确实可以不用保存原始文件，可以用来大数据快速查找，用法和实时添加数据的普通 hashmap 不太一样。 |
 |
52
rpman 2022-04-19 01:27:13 +08:00 2
又是我最喜欢的计算机民科环节
|
|
53
3dwelcome OP |
 |
54
binux 2022-04-19 01:38:16 +08:00 via Android 1
@3dwelcome 那查询的时候 hash 匹配上了，你怎么知道它是匹配还是冲突？
别告诉我查询数据集也是预处理过的啊，那样你干嘛还要解决数据冲突？预处理出来一个不冲突的 hash 算法不就行了。 |
|
55
3dwelcome OP @binux 可是完美 hash 的定义，就是数据预处理啊。
参见 https://en.bitcoinwiki.org/wiki/Perfect_hash_function ，国外大佬最优能达到 2bit 一个元素，算法比这个复杂很多。 |
 |
56
aima 2022-04-19 01:51:40 +08:00 via iPhone
@3dwelcome 那就不算 hashmap 算法了吧？所以其实是个利用 hashmap 的搜索算法？如果已知数据了那可用的算法应该不少吧 当然这个感觉也是可行的。都预处理了那干啥都可以了
|
|
57
binux 2022-04-19 02:07:08 +08:00
@3dwelcome perfect hash function 可没这要求，只有 In addition, if the keys are not the data and if it is known that queried keys will be valid, then the keys do not need to be stored in the lookup table, saving space.
https://en.wikipedia.org/wiki/Perfect_hash_function 就算你规定查询总是有效的，你这算法既不新，性能也不好啊。 |
|
58
3dwelcome OP 这段话的意思，是特指另外一个利用 lookup table 的完美哈希算法，是这类算法的鼻祖。
可是作者主页上提到，这类算法已经被时代所淘汰了，自己都不推荐用。 wiki 应该是很久没更新了。 我这里提到的算法，效率也没太大问题，多几个 bit 占用，原理应该是最简单最容易理解的。 |
 |
59
t1xLM63evRKUbpMh 2022-04-19 02:53:58 +08:00
|
 |
60
Xs0ul 2022-04-19 04:09:13 +08:00 1
试图总结一下楼主的算法，看看整理的对不对：
前提：需要查询的集合是有限并且已知的 算法： 1. 取某种 hash 算法 A ，对整个查询集应用一次这个 hash 算法 A 。假设这个 A 算法可能产生的值有 1000 种，那么需要一个对应大小的 bitmap ，用来记录每个 hash 在这个给定的查询集合上是否冲突。 2. 在 hash 算法合适的情况下，会有少量的冲突，这时候再取 hash 算法 B ，重复步骤 1 并产生一个新的 bitmap 3. 如此不停的重复直到无冲突 查询： 对某个 input X ，先应用 hash 算法 A ，查看对应的 bitmap A 是否有冲突，没有则可以直接用 hash map A ；否则再用 hash 算法 B ，查看对应的 bitmap B ，以此类推 |
 |
61
yulon 2022-04-19 09:14:38 +08:00
你连 HashMap 的实际应用经验都没有，不管用什么算法都要存原数据，不然遍历的时候要怎么办
|
 |
62
season8 2022-04-19 09:28:16 +08:00
1. 数据集必须是已知的，因为要预处理。
2. 数据集必须是固定上限的，因为不能插入（无法判断冲突数据是否是原数据），可以查询和删除。 3. 数据必须是去重的，有重复数据，必定重复 hash 比起标题所说，更像是如何使用 hashmap 去对 “已知有限的去重数据” 建立 “唯一索引”。 |
 |
63
qgymib 2022-04-19 09:33:37 +08:00
思来想去，楼主的问题应该在于计算机理论基础知识与数学概率这两项的基础没有学好。之所以不存在完美 hash 的推论很简单：
1. 无论多少层 hash 函数，只要是摘要算法，其结果一定是存在长度上限的 2. hash 碰撞概率计算公式为（ n 为元素个数，d 为取值空间）: ``` p(n,d) = 1 - e ^ ( (-n(n-1)) / (2d)) ``` 如上两个条件严格证明了在摘要算法中，永远不可能存在完美 hash 函数（楼主的多层 hash 算法本质上也是一个 hash 摘要算法）。 |
|
64
3dwelcome OP @season8
"2. 数据集必须是固定上限的，因为不能插入（无法判断冲突数据是否是原数据），可以查询和删除。" 插入和查询操作极为相似，虽然没存原始数据，资源 ID 号还是保留着，可以依次找回原始数据。 新插入情况，基本上平均计算 5 次 hash ，就能把新元素顺利插入 bitmap 里。 "3. 数据必须是去重的，有重复数据，必定重复 hash" 这要看具体情况。原数据长度是不受不限制的，只有 hash function 后的 hash value 才有长度限制这一说法。可以针对原数据属性，自己构造一个变长结果的 hash function 。这样只要原始数据不重复，hash value 就能保证不重复。 对于完全一致的原始数据，肯定没有保存两份的必要。 |
|
65
3dwelcome OP @qgymib 你忽略了一个重要前提，元素数量上限是固定的。只要数量固定，hash function 足够散列，碰撞概率就能固定，就有完美 hash 。
|
 |
66
yeyuefeng 2022-04-19 10:10:21 +08:00
有意思，但不可取
|
 |
67
luwill 2022-04-19 10:24:41 +08:00
给答出 bloom filter 的同学一点掌声👏👏👏
|
 |
68
jabari 2022-04-19 11:16:27 +08:00 1
这是个很朴素的想法, 简称民科, 并且也不新颖, 也没有严格的证明.
|
 |
69
zmal 2022-04-19 11:16:31 +08:00 1
多少有点民科的味道了。
hashmap 本意是用来解决数组和链表的访问效率问题。有冲突就 hash ，算法更复杂不说，相比链表法效率低多少？ hash 算法相比的 equal 效率降低多少？ 理论会存在 N 层 hash 后依然会冲突的 key ，你怎么解决？继续 hash 变成无限递归爆栈吗？ |
|
70
3dwelcome OP @luwill bloom filter 通常用一个 bit 位表示多种可能性，这里一个 bit 就只表示一个含义 = 当前层 hash 元素有没有冲突。没有其他的可能性了。
@zmal "理论会存在 N 层 hash 后依然会冲突的 key ，你怎么解决？" 这里的 hash function 是预处理函数，不是你理解的通常意义上，MD5 之类的强制截断函数。 举个例子，处理最大 256 个字节的 string 数据，只需要 256bit hash value 表示就可以。但是处理无数个 2G 的文件，用 sha256 都不一定能保证无冲突。所以预处理的 hash function ，计算后的长度是动态的，是根据分析原始数据后，才确认的长度。 而且每往下一层，元素数量指数级递减，冲突概率也会递减。并不会出现你说的无限循环。最下层桶里就几个元素，又怎么可能发生冲突。 |
|
71
zmal 2022-04-19 11:44:57 +08:00
“而且每往下一层，元素数量指数级递减，冲突概率也会递减。并不会出现你说的无限循环”
哈？哈？哈？冲突概率递减会变成数学意义上的 0 吗？无限趋近于 0 是 0 吗？只要不为 0 就还要考虑冲突。 计算机底层都是数学，你看到的经典数据结构都是发了论文经过严格论证的。 思而不学则殆。 莫回复我，看着糟心。 |
|
73
3dwelcome OP |
 |
74
yangyaofei 2022-04-19 13:03:00 +08:00
这很民科, 概念都不对,补补数据结构和什么叫哈希吧.......
|
 |
75
secondwtq 2022-04-19 13:08:36 +08:00
隔壁还有个 NIO 的，你们能不能一个一个来，V 站 Trending 都快不够用了 ...
|
|
76
mingl0280 2022-04-19 13:14:36 +08:00 1
别回这个楼主了，就一民科，让它去看数学它又不肯去……
|
 |
77
cs8425 2022-04-19 13:16:49 +08:00 1
插个眼看楼主表演
之前把 wasm 当唯一的神 无视应用场合跟局限就知道有多少料了... |
|
78
3dwelcome OP @yangyaofei 书本上是没有完美哈希，wiki 上有的。
我来普及一下知识吧，最初的形式完美 hash ，就是单纯指设计一个 hash function ，让产生的 hash value 完全不冲突。参见 http://burtleburtle.net/bob/hash/perfect.html 但是这个算法有个很大问题，就是同时要附加一个巨大的 lookup table ，很占空间。于是有人发明出类似的改版，类似我这种，多几个 bit 来替换查找表。最终效果差别不大，预计算量能降低很多。 最后原始作者主页也不维护了，久而久之，perfect hash 就从最初的一个函数，演化成了一整套算法。 实际应用的话，最常见的就是编译里 constexp 优化了，能保证字符串 hash 后，int value 不重复不冲突。 |
|
79
3dwelcome OP @mingl0280 "让它去看数学它又不肯去……"
数学上 MD5 就是会截断的。完美 hash 应用里，hash value 是可以随着数据量，无限长的。也就是两者 hash value 必须保证不冲突。 两者概念都不一样，是你们自己搞混了。 |
|
80
cs8425 2022-04-19 13:22:14 +08:00
楼主一直说算法很简单怎没人听懂
要求 show 个 code 又不要 真的很简单的话 花一点时间弄个 code demo/benchmark 让大家见识一下不就好了 怎偏偏一直不弄呢? |
 |
82
learningman 2022-04-19 14:10:55 +08:00 3
我超，计算机民科。
|
|
83
3dwelcome OP |
|
84
learningman 2022-04-19 15:21:23 +08:00
@3dwelcome 大哥你搜永动机也一大堆结果。
你这玩意儿意味着每加一个值到 map 里，hash 函数都可能要重新设计一下。数学上有意义，工程上没有。 |
|
85
binux 2022-04-19 15:46:58 +08:00 via Android
@3dwelcome minimal perfect hashing 和 perfect hashing 又是一个不同的问题。。
而且 perfect hashing 是加了限制条件的，和工程中用的 hashmap 又不是一样的问题。 即使针对 perfect hash 问题，你在主楼里也没说清楚问题描述。然后你的算法也不新，很多人随随便便都能想到。再者你也没有对算法进行抽象，不简练，你自己都没搞清楚这个算法的关键在哪。最后你不会用正确的工具描述分析这个算法，你没能拿出 code ，也无法分析时空复杂度。 我是没看出来这帖的目的是什么，被教育吗？ |
|
86
3dwelcome OP @learningman 知道 GCC 这个编译软件吗？他就在用，github 镜像里你能搜到相关的完美哈希代码。
最常见场景，就是把已知一组字符串，映射成不重复的整型 ID 。类似 constexp ，编译器静态预处理字符串哈希，要比运行时动态处理哈希冲突，执行效率要高太多。 说工程上没有用，只不过你们平时写业务太多，没遇到罢了。 |
|
87
3dwelcome OP @binux "描述分析这个算法，你没能拿出 code ，也无法分析时空复杂度。"
我自己写代码分析了，每个 key 平均占用 5bit 就是分析结果。 代码也懒得贴，除了你们一小部分人相信外。大部分人都以为我是在吹牛。 |
 |
88
DCELL 2022-04-19 16:08:02 +08:00 1
贴个 benchmark ，或者 贴下专利；
如果没有，去写； “代码也懒得贴” 我就当你放屁了哦。 |
 |
89
xuanbg 2022-04-19 16:11:17 +08:00
hash 冲突理论上是不可避免的，但在实际的 hash map 中，由于数据是有限的，所以冲突也是有限的。只需要留出一定的空间用于对应冲突就行了。你要问预留空间真不够了怎么办？那就崩掉好了呀，还不允许崩溃了吗？崩掉后改代码，通过参数增加预留空间就好，根本没必要搞这么复杂的呀。
|
|
90
yangyaofei 2022-04-19 16:48:50 +08:00
如果"完美哈希" 存在, 我觉得我这个也是完美哈希:
``` python global hash_table = list() def put(obj ) -> int: for(i, o in enumerate(hash_table)): if o == obj: return i hash_table.append(obj) return size(hash_table) ``` 只要不 pop, 空间效率历史最高! |
|
91
yangyaofei 2022-04-19 16:50:50 +08:00
|
|
92
learningman 2022-04-19 16:53:53 +08:00
@3dwelcome 那是确定有限的集合啊，你工程上能找到这么个确定有限的玩意儿？
都有限了用啥 map ，常量不好吗 |
 |
93
unicorn1390 2022-04-19 17:58:24 +08:00
@3dwelcome 代码也懒得贴 -----> "我确信我发现一种美妙的证法，可惜这里的空白处太小，写不下"
|
|
95
luwill 2022-04-19 22:12:15 +08:00
@3dwelcome 思想是一样的。 为什么不直接用 bloom filter 拦截呢？
bloom filter + hashmap ？ |
|
96
Xs0ul 2022-04-19 22:29:00 +08:00
像之前有人回复的，这个更像利用了 hash 的搜索算法。并且，这样的算法想要有实用性，得证明碰撞的概率够低，并且不同的 hash 算法碰撞还得足够独立的，不然就会多次冲突导致要添加很多层 bitmap 。
所以比较重要的部分是，如何选择 hash 的算法，而不是楼主描述的这个过程。举个例子，对于给定的查询集合，比如一堆文件，可以生成一堆 hash 函数：h(x), h(x+1), h(x+2)...，来试验怎么样的组合能在最少的次数完成这个多重 hash map 的构造。同时，hash 函数的值域越大，碰撞概率越低，但对应的 bitmap 需要的空间也越大，这里如何选择也是需要研究的。要有实用性，这些选择都应该能自动完成，但楼主提到的部分并没有讨论这些问题 |
|
98
documentzhangx66 2022-04-20 23:46:28 +08:00 1
1.哈哈哈哈哈哈，我认真看了一下楼主两篇帖子，以及他贴出来的国外大佬的文章，以及维基百科的词条...
我突然发现，楼主说的 hash ，与我们常用的 hash ，根本就不是一回事... 2.我们所说的常用 hash ，比如 MD5 、SHA1 等，是把一个数量未知可有限可无限、每个元素长度也未知且可有限可无限的集合，映射成数量已知、每条元素长度也是固定大小的集合，这样必然会有冲突。 拿 MD5 举例： md5( 123456 ) = 827ccb0eea8a706c4c34a16891f84e7b md5( aabbccddeeffgghh ) = 12e95c254d1c532e0d55e765731d8f89 md5( 啊啊啊啊啊啊啊啊啊啊呸 ) = 0fffbe633a0e4060545775e84788d648 左侧包含元素 123456 的集合，元素数量可能只有 10 个，也可能是无限数量。 而右侧包含元素 827ccb0eea8a706c4c34a16891f84e7b 的 MD5 结果集合，按照 MD5 的定义，元素数量最多只能是 2 的 128 次方个，而且每个元素的长度是固定的 128bit ，或 32 个 16 进制。 3.但楼主所说的完美 Hash： https //en.维基百科.org/维基 /Perfect_hash_function 上面这个 URL 触发了网站屏蔽，所以只能以这种形式发出来，大家应该都懂真实 URL 吧？ 是把已知元素数量（无论是否数量为无限个）、已知每个元素的集合，映射成一个元素数量比率差不多的序列，当这个序列总体长度达到数学证明的最小约为 1.44 Bit per key 时，就是最小完美 Hash （文中的 Minimal perfect hash function ），但目前已知算法，只能达到 1.56 Bit per key 。 举个例子，以下的一张表 Table ，由 2 列 组成。第一列是从 1 开始自增且唯一的主键，第二列是长度与内容都看上去像是随机，但其实是已知的字符串集合： ID （ Key ） Content 1 123456 2 aabbccddeeffgghh 3 啊啊啊啊啊啊啊啊啊啊呸 ..... ...... 现在的情况是，已知右边列的内容，已知左右两列肯定有一种对应关系，但不知道左边的具体值。现在需要通过一个算法，从右侧字符串，计算出左侧 ID： 123456 -> Minimal_perfect_hash_function( x ) -> 1 aabbccddeeffgghh -> Minimal_perfect_hash_function( x ) -> 2 啊啊啊啊啊啊啊啊啊啊呸 -> Minimal_perfect_hash_function( x ) -> 3 这特喵的就是楼主想说的东西。 Minimal_perfect_hash_function 与 我们常见的 MD5 、SHA1 这类哈希，根本是不同的东西，只是名称中都包含了 HASH ，于是大家先入为主地，以为楼主在说 MD5 、SHA1 之类的主流哈希算法。楼主这种其实更像是根据 value 反推 ID key 的 index 查找算法。 最关键的一点是，楼主说的这种 Minimal_perfect_hash_function ，当第二列 Content 的长度是无限时，计算出来的 ID 列的结果集的长度也是无限的！而 MD5 、SHA1 ，就算 MD5( x )，x 集合是无限的，但计算出来后，结果集的长度是有限的。这就是最大的区别。 Perfect_hash_function 是单射， MD5 、sha1 不是单射！ |
|
99
documentzhangx66 2022-04-20 23:51:13 +08:00
另外，楼主发明的这玩意，我并不关心，因为工程中如果出现这种情况，我直接用 Oracle 整一张自增 ID 主键的表，一 一对应就行了，或者直接对 Content 集合来个 gzip -9 。
还要去找半天楼主说的这种单射函数？ 吃饱撑的？游戏不好玩吗？ |
Select Language