scala – 生成k个成对独立的散列函数

发布时间：2020-12-16 08:57:09 所属栏目：安全来源：网络整理

导读：我正在尝试在 Scala中实现 Count-Min Sketch算法,因此我需要生成k个成对独立的散列函数. 这是一个比以前编程的更低级别,除了Algorithms类之外我对哈希函数知之甚少,所以我的问题是：如何生成这些k成对独立哈希函数？我应该使用像MD5或MurmurHash这样的哈希

我正在尝试在 Scala中实现 Count-Min Sketch算法,因此我需要生成k个成对独立的散列函数.

这是一个比以前编程的更低级别,除了Algorithms类之外我对哈希函数知之甚少,所以我的问题是：如何生成这些k成对独立哈希函数？

我应该使用像MD5或MurmurHash这样的哈希函数吗？我只生成形式为f(x)= ax b(mod p)的k哈希函数,其中p是素数,a和b是随机整数？ (即每个人都学习算法101的universal hashing family)

我看起来更简单而不是原始速度(例如,如果它更容易实现,我将采取5倍的速度).

解决方法

Scala已经实现了MurmurHash(它是scala.util.MurmurHash).它非常快速且非常擅长分配价值.加密哈希是过度的 – 你只需要花费数十或数百倍的时间.只需选择k种不同的种子,因为它几乎是加密的质量,你将得到很多独立的哈希码. (在2.10中,您可能应该切换到使用scala.util.hashing.MurmurHash3;使用情况有所不同,但您仍然可以通过混合执行相同的操作.)

如果您只需要将近似值映射到随机远值,这将起作用;如果你想避免碰撞(即如果A和B碰撞使用散列1它们可能也不会使用散列2碰撞),那么你需要至少再做一步并且不要散列整个对象而是散布它的子组件哈希有机会开始与众不同.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!