 |
panelattaV2EX 第 329425 号会员，加入于 2018-07-16 11:34:28 +08:00 |
panelatta 最近回复了
340 天前 回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap（上图附代码) |
@3dwelcome 说明你没看懂呗，要查数据的话两次 hash 都是已知的，直接 O(1)。
还是多学学习吧，有空找 perfect hash function 的英文网页 yy ，不如买本算导从头学起。
还是多学学习吧，有空找 perfect hash function 的英文网页 yy ，不如买本算导从头学起。
340 天前 回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap（上图附代码) |
别乱想了，我直接按你的思路帮你整个比你这个好得多的：
搞两层哈希表，第一层随便用什么 hash 函数都行，我们给他安排 k 个桶，对任意第 0 <= i < k 我们都给它安排一个独立的第二层哈希表；对于第 i 个桶里的所有 key ，我们从一个确定范围的函数空间 V 里随机选择一个 hash 函数，保证它能对这个桶里的所有 key 是完美 hash （比如对 key 是整数的情况，随机取 a, b 和素数 p 就能构造一个 hash 函数 f(x) = (ax + b) % p ），然后这个桶直接记录上这个 hash 函数就行了；这样你的 dataset seedset 都不用了，还不用在这又臭又长地选种子，不比你这个好多了？
而且你的加盐就“完美”的说法还只是瞎想，我这个直接给你选一个完美函数，一次随机不行再来一次，不比你这个直接？
口嗨谁不会啊？
搞两层哈希表，第一层随便用什么 hash 函数都行，我们给他安排 k 个桶，对任意第 0 <= i < k 我们都给它安排一个独立的第二层哈希表；对于第 i 个桶里的所有 key ，我们从一个确定范围的函数空间 V 里随机选择一个 hash 函数，保证它能对这个桶里的所有 key 是完美 hash （比如对 key 是整数的情况，随机取 a, b 和素数 p 就能构造一个 hash 函数 f(x) = (ax + b) % p ），然后这个桶直接记录上这个 hash 函数就行了；这样你的 dataset seedset 都不用了，还不用在这又臭又长地选种子，不比你这个好多了？
而且你的加盐就“完美”的说法还只是瞎想，我这个直接给你选一个完美函数，一次随机不行再来一次，不比你这个直接？
口嗨谁不会啊？
Select Language