哈希实验
hashexperiments - 如果您以前从未进行过洗牌,您如何洗牌? 或者,“什么是实现 shuffle 的最疯狂的方法……它确实有效!”
shuffle 算法的标准方法是 Knuth shuffle,但是当向我提出问题时,我从未听说过它并想出了一个......稍微不同的方法。
我知道散列函数应该在随机分布数字方面做得很好,而且对于一个好的散列函数,输入中的单个位翻转平均应该翻转一半的输出位(雪崩特性)。 我知道这一点,因为我一直在优化哈希表,他们依赖于此。
因此,要随机化输入,您可以将输入与随机种子值连接起来,然后插入到哈希表中(只要碰撞解决方案足够智能,可以在数字上方和下方平均分配碰撞)。
这证明尽管听起来很奇怪,但这种方法确实有效并提供了大量的随机性。 它也非常适合并行执行(大部分计算都在散列中,一个好的并发散列表实现应该在并行插入时遇到接近零的锁争用)。
2021-07-13 12:20:25
16KB
Java
1