斐波那契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 散列可能不是最好的散列函数，但它是从大范围数字映射到小范围数字的最佳方式。我们只是为此而使用它。