这是一个创建于 948 天前的主题，其中的信息可能已经有所发展或是发生改变。
继上篇，上文的 5bit 占位算法，平均查一次需要计算 5 次哈希函数，效率不行。
我在想，既然数据库用户密码哈希都能加盐，那么 hashmap 优化也是可以加的，同一个 key ，加了不同的盐后，计算出的哈希值是完全不一样的，既可以避免冲突，也能提升查找效率。
具体算法还是很简单，以查找一个英文字典举例：
1. 分配一个比数据量要大一点的桶数组。
2. 依次遍历原始字符串，把当前字符串 hash 后的结果，保存到对应的桶 ID 里。
3. 如果目标桶被占用了，那么换一个盐或者种子 ID ，一直到找到空余的桶。
4. 依次处理完所有数据。
这样就构建结束，由于加了盐，那么查找 key 的时候，也需要同时把 key 对应的种子 ID 也附带传进去。
我用 VS2022 写了一点点性能测试代码，对一个字典查找 8 千万次，在 release 下编译。
如下图所示，由于完美哈希没有一个冲突，查找效率明显要比标准的 stl 好很多。
我在想，既然数据库用户密码哈希都能加盐，那么 hashmap 优化也是可以加的，同一个 key ，加了不同的盐后，计算出的哈希值是完全不一样的，既可以避免冲突，也能提升查找效率。
具体算法还是很简单，以查找一个英文字典举例：
1. 分配一个比数据量要大一点的桶数组。
2. 依次遍历原始字符串，把当前字符串 hash 后的结果，保存到对应的桶 ID 里。
3. 如果目标桶被占用了，那么换一个盐或者种子 ID ，一直到找到空余的桶。
4. 依次处理完所有数据。
这样就构建结束，由于加了盐，那么查找 key 的时候，也需要同时把 key 对应的种子 ID 也附带传进去。
我用 VS2022 写了一点点性能测试代码，对一个字典查找 8 千万次，在 release 下编译。
如下图所示，由于完美哈希没有一个冲突，查找效率明显要比标准的 stl 好很多。
第 1 条附言 · 2022-04-20 17:06:01 +08:00
贴一下代码
vector<string> keydata; // 从文件里读取的字符串集合
int elemsize = keydata.size(); // 字符串集合总大小
int seedsize = elemsize * 1.6180339887498948482;// 种子大小，使用黄金分割率；太大会多占用空间，太少会增加计算耗时，也有可能没有完美解。
vector<int> seedset; // 种子空间是否被占用
vector<int> dataset; // 对应原始的字符串ID
vector<int> keyseed; // 和key对应的种子seed
seedset.resize(seedsize, 0); // resize同时并初始化为0
dataset.resize(seedsize, 0);
keyseed.resize(elemsize, 0);
// 构建算法: 查找空余的桶，如果已经被占用，则循环查找，一直到找到空位为止。
for (i=0;i<elemsize;i++)
{
for (int s=0;;s++)
{
uint hashval = crc32(s, (const byte*)keydata[i], keydata[i].size()) % seedsize;
if (seedset[hashval] == 0)
{
seedset[hashval] = 1; // 声明此桶被占用
dataset[hashval] = i; // 字符串id号会重排
keyseed[i] = s; // 保存seed种子
break;
}
}
}
// 查找测试
int id = 50;
uint hashval = crc32(keyseed[id], (const byte*)keydata[id], keydata[id].size()) % seedsize;
int findid = dataset[hashval];
以上查找代码有两点优化空间
第一是% seedsize取余数可以改成 & seedmask。 第二是crc函数不快，hash函数可以换成更快的。
这个是图片上vs2022的hashmap对比测试代码 http://www.dooccn.com/cpp/#id/b493ff0ca2ba66c061a59b8aa1f78dbe
 |
1
NeroKamin 2022-04-20 18:20:00 +08:00
看起来不就是开放地址法吗
|
 |
2
3dwelcome OP |
|
3
3dwelcome OP 回帖的时候又灵光一闪，可以不用暴力循环 9 万次。
hash 函数分两类，一种安全 hash ，比如 MD5 和 SHA1 。另外一类是非安全 hash ，比如 hashmap 里用的字符串 hash 。非安全哈希，可以根据 hash 的结果，去人为构建 hash 前的结果。所谓的 hash 碰撞攻击法。 于是，我确信我发现一种美妙的证法，免去暴力循环查找，可惜这里的空白处太小，写不下。 |
 |
4
mrgeneral 2022-04-20 19:46:34 +08:00  1
> 同一个 key ，加了不同的盐后，计算出的哈希值是完全不一样的，既可以避免冲突
呃，hash 冲突是对不同的关键字可能得到同一散列地址，加盐一样冲突，只不过概率小而已。 |
 |
5
Co1a 2022-04-20 19:52:02 +08:00
看了第一个帖子，感觉和我看的 cuckoo filter 论文有点类似？
|
|
6
3dwelcome OP @mrgeneral
“呃，hash 冲突是对不同的关键字可能得到同一散列地址，加盐一样冲突，只不过概率小而已。” 昨天我也许和你一样的想法，现在我已经不那么想了。 加了盐后，就相当哈希于一个被设计修改过的 MD5 文件，想要发生碰撞或者不想发生碰撞，都是人为可控的。并不完全依赖概率。 |
 |
7
keith1126 2022-04-20 20:19:45 +08:00
你这个的本质是，对于哈希冲突，额外记录了一些信息，用于加速查找。
类似地，就好比是直接记录下每个元素在哈希桶中的位置，查找的时候直接跳到那个位置，可以确保真正意义上的 O(1)，而非均摊的 O(1)。 那么，代价是什么呢？就是你额外用了 keyseed 这个数组来存所谓的 salt 。一是额外的空间消耗，但更主要的是，对于更加通用的数据类型，当你没法用一个 `vector<int>` 来存 salt 的时候，你该怎么存？比如，如果 key 的空间无限大，你这个 hashmap 如何模拟 std::map<string, int>？ |
|
8
keith1126 2022-04-20 20:21:51 +08:00
@keith1126 #7
总结一下，你这个的优化点在于，在建立哈希表之前，你已经预知了所有的 key ，所以可以把每个 key 对应的 salt 存在 vector<int> 里面，自然就可以避免所谓的冲突。但这并不现实。 |
|
9
keith1126 2022-04-20 20:28:57 +08:00 4
@keith1126 #8
如果还说的不够明显的话，你既然都用 keyseed 来存 salt 了，你直接用 keyseed 来存每个元素在 dataset 中位置岂不是更直接？查找的时候直接 dataset[keyseed[i]] 不是更快？还要啥哈希 🤣 |
|
10
3dwelcome OP @keith1126 "在建立哈希表之前，你已经预知了所有的 key"
这种情况很常见的，比如搜索一本牛津英文字典，动态加入英文单词是很罕见的情况，大部分都是直接查询。 "如果 key 的空间无限大。...自然就可以避免所谓的冲突。但这并不现实。" 我猜你是指如果 KEY 是文件，处理 500 万个 500G 文件，哈希后肯定会发生冲突。这种也可以避免的，有一些 HASH 函数，拥有 incrementally 特型，也就是随着处理文件长度的增加，HASHVAL 大小也会同步增加。盐也可以同步递增。 但这又是一个延伸的话题，可惜这里的空白处太小，写不下。 |
|
12
3dwelcome OP @keith1126 "直接用 keyseed 来存每个元素在 dataset 中位置岂不是更直接？查找的时候直接 dataset[keyseed[i]] 不是更快？"
这里 keyseed 用数组保存，只是方便大家能看懂代码。最终是 mix 到原 key 里面的。 用的时候，直接用修改后的 key 来查，没有所谓的 ID 号。 |
 |
13
muzuiget 2022-04-20 20:52:47 +08:00 2
hash 版本的永动机，用脚趾头都知道，表示如果 hash 的表示范围为 N ，如果原始数据有 N + 1 种情形，那必定产生一次碰撞。
你给原文加了 salt ，就产生了一个新原文，问题依然还是那个问题，碰撞还是会碰撞。 |
|
14
3dwelcome OP @muzuiget "表示如果 hash 的表示范围为 N ，如果原始数据有 N + 1 种情形，那必定产生一次碰撞。"
你这说法不成立，hash 的表示范围肯定比原始数据要大。hash function 是个广泛的概念，并不是指某些特定函数。 比如 MD5 装不下 500 万个文件，那么换成 SHA256 也许就可以。总有更大结果的 hash 函数，这种通用函数叫 incrementally hash function 。 |
|
15
muzuiget 2022-04-20 21:19:40 +08:00
@3dwelcome “hash 的表示范围肯定比原始数据要大……那么换成 SHA256 也许就可以。”
你增大了 hash 值表示范围了，那我原始数据样本量一样可以增大，我的原始数据可以取值 SHA256 的表示范围，再加一个 SHA512 长度的值，保证让你至少碰撞一次。 两者可以互相这么增大下去，最终结果 hash 值和原始值表示范围一样了。 也就是，一个原始数据的无碰撞 hash 值就是它自己本身，但这还叫算是 hash 吗？ |
|
16
3dwelcome OP @muzuiget "我的原始数据可以取值 SHA256 的表示范围，再加一个 SHA512 长度的值，保证让你至少碰撞一次。"
并不是的，完美哈希是预处理，也就是一切数据，都是在可控范围内。 碰撞的概率不仅仅是和 KEY 大小有关系，和数量也有关系。你哪怕一个 KEY 是几百 G 的文件，只要文件总数量没上去，用 MD5 照样可以完美表达。 |
|
17
muzuiget 2022-04-20 21:43:16 +08:00 3
唉，概念理解都不在频道上。
|
|
18
3dwelcome OP @muzuiget
我知道你指的是范围，可是预处理就意味着我的 hash 值表示范围，永远可以比你数据提供的最大范围还要大。 你要问怎么可能，这就是 incrementally hash function 的属性。一个可增变哈希函数，是可以被针对性构造的，你想要表示多大的范围都可以，并不是 MD5 那种定死截断类函数。 现实中，往往数据范围都是极其有限的。盐（种子）的加入，也能人为去避免碰撞，能发生碰撞的，就不叫完美哈希了。 |
 |
19
kiwi95 2022-04-20 21:56:03 +08:00 via Android 7
在计算机编程领域，如果你没有深厚的理论知识就觉得自己发现了不得了的东西，一般都是你自己理解错了。因为数学理论的发展已经远远远远远超过一般程序员的理解范围了，很难存在这么明显的理论漏洞
|
 |
20
LeeReamond 2022-04-20 22:03:26 +08:00
我觉得一楼对比效率的图意义不大，毕竟 hashmap 实现的上细节也很丰富，不可一概而论。看了 LZ 之前两个帖子，应该就是传统算法遇到 hash 碰撞则按链表方式保存，二级搜索采用逐个对比，lz 觉得二级搜索可以再加一层 hash ，以此类推。不过从普遍情况讲，google 开源 cityhash 已经是十多年前的事了，哈希发展到 2022 年，快速哈希算法本身效率和碰撞率都很低，普遍应用场景中碰撞本身是少数，所以二级索引中使用全文读生成二级哈希效率会比直接位对比快吗？我看不尽然，举例中使用的 md5 和 sha1 之类的成本极高的算法更不现实了，生产中也没见过这么用的。
再一个如果是从数理逻辑上针对无穷输入的情况设计普遍适用模块，逐位对比当然是永远不会出 bug 的，但是多层哈希法无法保证一定不会出现某对数据所有哈希值相同的情况，哈希算法需要人为设计是有限的，数据是无限的 ，完美看起来反倒没有现在通用方案完美。 |
|
21
3dwelcome OP 这样说吧，任意两个文件在 MD5 计算后，碰撞的概率是 1.47*10-29 次方。
由于完美哈希导入了盐这个属性，那么新的碰撞概率就是绝对的 0 ，这就是“完美”的含义。 |
 |
22
wdhwg001 2022-04-20 22:05:07 +08:00 13
一般来说，我们对于这种症状，孔子是比较委婉的，他说思而不学则殆。
现代人是比较不委婉的，比如我一般把这种奇思妙想称为民间科学家。 并且，我有点在意的是，这种情况持续多久了？医生怎么说？ |
 |
23
leimao 2022-04-20 22:07:04 +08:00 via iPhone
楼主的算法只能用于特殊场景。请不要和 Hashmap 相比。
|
|
24
3dwelcome OP @LeeReamond "毕竟 hashmap 实现的上细节也很丰富"
我查了一下，好象 stl 是用链表加红黑树结构来处理碰撞的情况，速度肯定不慢。 发这个帖子，也就是觉得无碰撞的字符串哈希很有意思，"完美哈希"这个词在我看来，很雅致。 晚期强迫症患者的救星。 |
|
26
leimao 2022-04-20 22:12:02 +08:00 via iPhone 2
我这么跟你说吧，要是我的内存可以无限大，我都不需要 Hash ，key value 直接做内存地址。你这个算法怎么跟我的比？
|
 |
27
binux 2022-04-20 22:14:20 +08:00 via Android
你查找的时候都知道 keyseed[id] ，结果的 id 都已经知道了还查询什么劲啊，直接 dataset[id] 岂不更快。
|
|
28
leimao 2022-04-20 22:16:29 +08:00 via iPhone
“完美”这两个字需要数学来支撑，而且很多时候数学告诉你没法完美。你这个内存就用的比 Hashmap 多，哪里来的完美？而且这么跟你说吧，你无法通过换种子或者换 Hash 函数来保证新的 Hashed value 和之前的没有冲突，数学上不支持的话咱还是低调一点。
|
|
29
binux 2022-04-20 22:18:12 +08:00 via Android
@3dwelcome 你怎么把 keyseed mix 到原 key 里？ 你查询的时候谁帮你 mix ？比如说一个字典，文章还不能直接写英文单词了？还得 mix 你的 keyseed ？
既然你可以 mix keyseed ，你干嘛不直接 mix dataset 呢？ |
|
30
3dwelcome OP @vacua "0 要拿理论推导啊，加个盐就成 0 了，没有概率学公式的完美一律是伪科学"
可能你不信，但是"完美"这点，我确实是有依据的。 很多人觉得 hash 只是散列作用，不确定散列后数据是否发生碰撞，也不清楚内部原理。但是我发现，一些特定 hash 函数，只要处理的数据在表达范围内，仅仅只是 reorder ，重排序了数据顺序，并不会对数据范围造成损伤。 换言之，也就是主楼代码里那个 seed 或者说盐，是 100%存在完美解的。 |
|
31
3dwelcome OP @binux "比如说一个字典，文章还不能直接写英文单词了？"
不 mix 也可以，那就和普通的完美哈希算法一样，做成 lookup table 保存在内部呗。 我是觉得 seed 和 key 绑定在一起，用起来更方便顺手。比如编译进程序内部字符串资源查找，肯定不需要用户输入。 |
|
32
leimao 2022-04-20 22:23:59 +08:00 via iPhone 1
请还是直接用我的 key value 直接做地址的算法吧
|
|
33
3dwelcome OP @leimao "而且这么跟你说吧，你无法通过换种子或者换 Hash 函数来保证新的 Hashed value 和之前的没有冲突，数学上不支持的话咱还是低调一点。"
我发现你们对 hash 函数的运行机制都是一知半解。实在不行我就再发一贴，这样下去，都快变成连续剧了。 你可以看一下这篇文章： https://www.jandrewrogers.com/2019/02/12/fast-perfect-hashing/ |
|
34
binux 2022-04-20 22:35:31 +08:00 via Android 3
@3dwelcome 你都有 lookup table 了，还要你这个 hashmap 干嘛？用户输入不带 seed ，key => seed 的过程不就是一个查找的过程，怎么你还要用另一个“完美无冲突”hashmap 解决吗？
这就好像你发明一个永动机，需要一个电扇吹一样。 |
 |
35
panelatta 2022-04-20 22:37:38 +08:00
别乱想了，我直接按你的思路帮你整个比你这个好得多的：
搞两层哈希表，第一层随便用什么 hash 函数都行，我们给他安排 k 个桶，对任意第 0 <= i < k 我们都给它安排一个独立的第二层哈希表；对于第 i 个桶里的所有 key ，我们从一个确定范围的函数空间 V 里随机选择一个 hash 函数，保证它能对这个桶里的所有 key 是完美 hash （比如对 key 是整数的情况，随机取 a, b 和素数 p 就能构造一个 hash 函数 f(x) = (ax + b) % p ），然后这个桶直接记录上这个 hash 函数就行了；这样你的 dataset seedset 都不用了，还不用在这又臭又长地选种子，不比你这个好多了？ 而且你的加盐就“完美”的说法还只是瞎想，我这个直接给你选一个完美函数，一次随机不行再来一次，不比你这个直接？ 口嗨谁不会啊？ |
|
36
3dwelcome OP @binux "你都有 lookup table 了，还要你这个 hashmap 干嘛？"
市面上有很多的 perfect hash 算法，各种各样，所有无一例外，都是需要附加额外 lookup table 作为算法数据支撑。 这就是所谓的预处理，如果预处理不产生辅助数据，那就变成 hashmap 这种实时算法了。 |
|
37
3dwelcome OP @panelatta "口嗨谁不会啊？"
你这算法性能不够的，查询性能也是一个很重要的指标。 上个贴所以弃贴，又重新开了一个，就是因为 5bit 的算法查询性能拉跨。 要超越 stl 的 hashmap ，是一件很困难并值得骄傲的事情。所以我才又发帖。 |
|
38
leimao 2022-04-20 22:53:22 +08:00
@3dwelcome 咱啥也别说好吧。Hashmap 本来就不需要理解 specific 的 hash 算法。我告诉你我的 key value 直接做地址也是一个 perfect hash function 。
|
|
41
binux 2022-04-20 22:55:45 +08:00 via Android
|
|
42
panelatta 2022-04-20 22:56:35 +08:00
@3dwelcome 说明你没看懂呗，要查数据的话两次 hash 都是已知的，直接 O(1)。
还是多学学习吧，有空找 perfect hash function 的英文网页 yy ，不如买本算导从头学起。 |
|
43
leimao 2022-04-20 22:57:09 +08:00
我觉得这个帖子的标题非常夸张且误导人，我们不应该继续跟进。
|
|
44
leimao 2022-04-20 22:58:59 +08:00
这让我想起来做 Deep Learning 的人有很多就是光换种子，然后拿个数据集做测试，发现用某个种子能够超越被外界认可的 SOTA 算法，然后出来吹了一番。
|
|
45
3dwelcome OP @leimao "发现用某个种子能够超越被外界认可的 SOTA 算法，然后出来吹了一番。"
我也没想着吹，这个帖子的算法和上个帖子的，都是一拍脑袋，就能想出来的超简单方法。 只是上个帖子里，大家都觉得我在吹牛，这才不得已发一点代码，作为对比测试。 要不然光吃瓜群众的口水，都能把给我淹没了。 |
 |
46
Vitor 2022-04-20 23:07:11 +08:00
我觉得 8L9L 已经把问题说的很清楚了
|
 |
47
icyalala 2022-04-20 23:12:11 +08:00
你是想要这个吗: Perfect Hash Function Generator
https://www.gnu.org/software/gperf/manual/gperf.html |
|
48
icyalala 2022-04-20 23:28:48 +08:00
如果你目标只是 Perfect Hash ，那上面这类工具已经有很长时间了。
如果你更关心性能，那可以看看前几年的 Google swisstables 或者 Facebook 的 F14 Hash Table ，甚至只用开放地址+Robin Hood hashing 性能就足够比 unordered_map 高很多了。 |
 |
49
dqzcwxb 2022-04-20 23:35:41 +08:00
当初你出来我是没有签字同意的
|
 |
50
XiLingHost 2022-04-20 23:39:14 +08:00
发了一点代码，大家发现真的是在吹牛
|
 |
51
documentzhangx66 2022-04-20 23:43:42 +08:00
1.哈哈哈哈哈哈，我认真看了一下楼主两篇帖子，以及他贴出来的国外大佬的文章，以及维基百科的词条...
我突然发现，楼主说的 hash ，与我们常用的 hash ，根本就不是一回事... |
|
52
documentzhangx66 2022-04-20 23:43:58 +08:00
2.我们所说的常用 hash ，比如 MD5 、SHA1 等，是把一个数量未知可有限可无限、每个元素长度也未知且可有限可无限的集合，映射成数量已知、每条元素长度也是固定大小的集合，这样必然会有冲突。
拿 MD5 举例： md5( 123456 ) = 827ccb0eea8a706c4c34a16891f84e7b md5( aabbccddeeffgghh ) = 12e95c254d1c532e0d55e765731d8f89 md5( 啊啊啊啊啊啊啊啊啊啊呸 ) = 0fffbe633a0e4060545775e84788d648 左侧包含元素 123456 的集合，元素数量可能只有 10 个，也可能是无限数量。 而右侧包含元素 827ccb0eea8a706c4c34a16891f84e7b 的 MD5 结果集合，按照 MD5 的定义，元素数量最多只能是 2 的 128 次方个，而且每个元素的长度是固定的 128bit ，或 32 个 16 进制。 |
|
53
documentzhangx66 2022-04-20 23:44:43 +08:00 1
3.但楼主所说的完美 Hash：
https://en.维基百科.org/维基 /Perfect_hash_function 是把已知元素数量（无论是否数量为无限个）、已知每个元素的集合，映射成一个元素数量比率差不多的序列，当这个序列总体长度达到数学证明的最小约为 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 啊啊啊啊啊啊啊啊啊啊呸 ..... ...... |
|
54
documentzhangx66 2022-04-20 23:45:01 +08:00 2
现在的情况是，已知右边列的内容，已知左右两列肯定有一种对应关系，但不知道左边的具体值。现在需要通过一个算法，从右侧字符串，计算出左侧 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 不是单射！ |
|
55
documentzhangx66 2022-04-20 23:51:29 +08:00
另外，楼主发明的这玩意，我并不关心，因为工程中如果出现这种情况，我直接用 Oracle 整一张自增 ID 主键的表，一 一对应就行了，或者直接对 Content 集合来个 gzip -9 。
还要去找半天楼主说的这种单射函数？ 吃饱撑的？游戏不好玩吗？？ |
 |
57
Mutoo 2022-04-21 09:49:46 +08:00
有点像布隆过滤器
|
|
58
3dwelcome OP @vacua "有依据就拿出来啊“
主楼的代码就是依据，你可以试试，用 seed 递增，看看 crc32 后的结果，会不会产生相互冲突。 一个随机数生成器，产生结果不可预测，值有可能会重复。 但 hash 不一样，只要输入值不超出表达范围，是可以进行逆向 hash 的还原操作。 |
 |
59
iosx 2022-04-21 11:01:04 +08:00
哈希不可避免冲突的，但可以让一个桶里放多个元素，也就是增大桶深。比如交换芯片 FDB 表设计有用双桶设计。4K 个表，桶身为 2 ，可以存 8K 条 FDB 。
|
|
60
iosx 2022-04-21 11:05:40 +08:00
补充下，还有些交换芯片，会有一个副表。专门用来存储冲突的数据，一般很小，比如 256 或 1K 大小，顺序遍历即可。
|
 |
61
zlbruce 2022-04-21 11:14:31 +08:00
如果你要和 hashmap 做对比：
1. 请用你的 hashmap 统计一下某篇文章的词频 2. 请告诉我这些字符串中有没有 3dwelcome 字符串 为什么计算机的民科比较少，就是因为代码一出来，就现行了。 |
|
62
zlbruce 2022-04-21 11:17:09 +08:00
另外要比对性能也需要对等的来对比：用 unordered_map 查询时输入是什么，用你的 hashmap 就应该输入是什么。
|
 |
63
yangyaofei 2022-04-21 11:22:56 +08:00
@documentzhangx66 #55 也不能这么说, 谁初中的时候不中二一下. 比如声称看懂了相对论这种. 到了能看懂洛伦兹变换什么的的年纪, 再真的看一下当年的论文(甚至仅仅是狭义的), 也不基本上会闭嘴了...
天才 7 岁能看懂, 但是天才不会来这儿发帖, 而是直接顶刊顶会发一波,<无冲突完美哈希>, 怎么着也是 ACM 顶会发一波, 或者 SCI 一区发一篇(承认格局有点小), 要是复杂度还是哈希的复杂度的话, 图灵奖不也可以么☺️ |
|
64
3dwelcome OP @zlbruce “用 unordered_map 查询时输入是什么，用你的 hashmap 就应该输入是什么。”
你是指多了一个 seed 参数？这算法一开始，seed 是保存在内部的桶里。后来我觉得反正都预处理了，没必要把辅助数据隐藏那么深，就直接提取到最外面了。 seed 和 key 一一对应，这是设计原则。不论 seed 是封装到类内部，或者暴露在外层，都是同一个意思。 |
|
66
3dwelcome OP 1
|
 |
67
VYSE 2022-04-21 12:44:38 +08:00
@3dwelcome #60 unordered_map 查询是 key(假设 string)获取 value, 你算法查询不光 key 还要 key 对应的 seed(代码里 keyseed[id]), 而根据 key(string)查 id 还得每次到 keydata 里数组遍历查询? 性能测试时候包含数组反查 id 了么?
|
|
68
3dwelcome OP @VYSE 肯定包含数组反查了，这点不会取巧的。
况且这个测试数据还是很保守的，激进的话，连数组反查都不需要。dataset 本质上就是对于原始 key 顺序的重新排序。同样可以通过预处理，把 dataset 消灭。 查询性能只是算法一部分，无冲突才是亮点。可以完美避免链表操作。 |
|
69
VYSE 2022-04-21 13:12:40 +08:00
@3dwelcome #64 既然每次查询你得从 keydata 数组反查 key 得到所在的 id 索引, 再建一个相同顺序的 valuedata 的 vector, 同一 id 直接拿 value 不就行了? 何必做 hashmap?
|
|
70
3dwelcome OP |
|
72
3dwelcome OP @binux "不，你没有。你绝对写不出一个 find(string) 函数。"
不，我可以。这是一回事情，稍稍改一下构建算法，把 seed 放到桶内，完全可行。 具体算法如下： 1. 先 hash 一次 key ，得到桶的 ID 2. 如果目标桶被占用了，在桶上标记一次，表示这个桶是需要 seed 来辅助计算免冲突的。同时换个 seed 尝试，重新一次 hash ，直到找到空余桶。 3. 重复第二步骤，处理完所有 key 。 |
|
73
3dwelcome OP 查询的时候，算法也是一样。
1. 用先 hash 一次 key ，得到桶的 ID 2. 根据桶的 ID ，得到 key 对应的 seed ，再次用 seed hash 一次，结果就能免冲突。 就是 seed 保存在桶内部，还是和 KEY 一起保存在外部的问题。我个人是完全偏向保存到外部的，预处理数据最终都是要存盘的。 |
 |
75
tool2d 2022-04-21 14:30:15 +08:00
@binux 微软的 hashmap 也不是万能的，字符串 hash 算法是开源的，那就意味着 hashmap 是可以被人为构造攻击的。
当一大堆 hash 碰撞挤在一堆，微软的 hashmap 就会退化到链表和红黑树，性能急剧下降。 完美哈希就没这个情况，完美解决了碰撞问题。 |
|
77
NeroKamin 2022-04-21 15:04:30 +08:00
@documentzhangx66 看了你的我才明白 OP 的想法
|
 |
78
chanchan 2022-04-21 15:31:18 +08:00
"不要误导吃瓜群众，有 13 个小孩，一年就必定有 13 个月份。完美哈希里，桶的大小，是根据数据总量提前分配的。"
根据总量提前分配,那理想情况下准备一个数组就好了,也不需要什么 hash |
Select Language