斐波那契Hash
Fibonacci Hashing:
黄金比例数:
2^16 * 0.618033887 ≈ 40503
2^32 黄金比例 ≈ 2654435769
2^64 黄金比例 ≈ 11400714819323198485
斐波那契Hash 可以让数据更加散列,减少HASH冲突,对于32位整数,f(x) = (x * 2654435769) >> 28
在 2^36 范围内是无碰撞的??
对于任意整数范围内的值 [0, LIMIT]:
GOLD_RATIO = (math.sqrt(5) - 1) / 2 # 0.6180339887
hash_id = (id * int(LIMIT * GOLD_RATIO)) % LIMIT
其hash结果是无碰撞的。
Fibonacci 散列可能不是最好的散列函数,但它是从大范围数字映射到小范围数字的最佳方式。我们只是为此而使用它。
转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 using1174@foxmail.com
文章标题: 斐波那契Hash
文章字数: 188
本文作者: Jun
发布时间: 2021-12-20, 10:10:55
最后更新: 2021-12-20, 11:01:16
原始链接: http://yoursite.com/2021/12/20/斐波那契Hash/版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。