斐波那契 散列

java

https://blog.csdn.net/y4x5M0nivS ... le/details/81124944

散列（Hash）也称为哈希，就是把任意长度的输入，通过散列算法，变换成固定长度的输出，这个输出值就是散列值。
简单来说，哈希表的实现就是数组加链表的结合。在每个数组元素上都一个链表结构，当数据被 Hash 后，得到数组下标，把数据放在对应下标元素的链表上。


散列算法的宗旨就是：构造冲突较低的散列地址，保证散列表中数据的离散度。常用的有以下几种散列算法：
除法散列法
平方散列法（平方取中法)
斐波那契（Fibonacci）散列法
随机数法




懂了散列算法，我们再来了解下拉链法。拉链法是为了 HashMap 中降低冲突，除了拉链法，还可以使用开放寻址法、再散列法、链地址法、公共溢出区等方法。这里就只简单介绍了拉链法。
把具有相同散列地址的关键字(同义词)值放在同一个单链表中，称为同义词链表。有 m 个散列地址就有 m 个链表，同时用指针数组 T[0..m-1] 存放各个链表的头指针，凡是散列地址为 i 的记录都以结点方式插入到以 T 为指针的单链表中。T 中各分量的初值应为空指针。