斐波那契Hash

Fibonacci Hashing:

https://book.huihoo.com/data-structures-and-algorithms-with-object-oriented-design-patterns-in-c++/html/page214.html

https://probablydance.com/2018/06/16/fibonacci-hashing-the-optimization-that-the-world-forgot-or-a-better-alternative-to-integer-modulo/

黄金比例数:

公式

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" 转载请保留原文链接及作者。

目录
×

喜欢就点赞,疼爱就打赏