斐波那契散列法

斐波那契散列法本质上是一个乘法散列法，特殊的是它采用一个特殊的乘数,选择的这个乘数和黄金分割比例密切相关；

黄金分割比例

给定两个正数x和y,如果x/y=(x+y)/x,则

黄金分割比例

被叫做黄金分割比例;
![](http://www.forkosh.com/mathtex.cgi?%20\Large%20{\frac xy}={\frac {x+y}x})

![](http://www.forkosh.com/mathtex.cgi?%20\Large%20\phi={\frac xy})

![](http://www.forkosh.com/mathtex.cgi?%20\Large%20{\phi}={\frac {1+\sqrt5}2})
在斐波那契散列法中，我们关心的并不是黄金分割比例，而是它的倒数：

位数(w) 乘数 备注
16 40503 0.6180339887*2^16=40503.4754834432
32 2654435769 0.6180339887*2^32=2654435769.2829335552
64 11400714819323198485 0.6180339887*2^64=11400714818402800990.5250107392
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • 斐波那契数列之美
    有这样一个数列：1、1、2、3、5、8、13、21、34……前两个元素为1，其他元素均为前两个元素和。在数学上以如...
    Pasu阅读 7,357评论 2赞 30
  • 一颗梨的出走
    一颗站也站不稳的梨，鲜美多汁。这颗脑满肠肥的梨，挺着便便大腹，满精神地傲立了一小会儿，又安逸地倒下了。 还是躺着舒...
    熊猫居士阅读 304评论 0赞 0
  • 最好的学习方法
    巴赫是巴洛克时期的德国著名音乐家，很长一段时间里，他都在莱比锡圣多马教堂度过，一边担任牧师一边进行音乐创作。 一次...
    女人那点美事阅读 516评论 0赞 0
  • App排版设计初期版
    小钢件阅读 461评论 0赞 0
  • Thread_线程安全
    count方法计算0-10的总和，并输出当前线程名，期望每个线程都打印出55. 结果:只有一个线程输出55.为保证...
    perfect_jimmy阅读 299评论 0赞 0