何为散列
散列（Hash）也称为哈希，就是把任意长度的输入，通过散列算法，变换成固定长度的输出，这个输出值就是散列值。
散列算法的宗旨就是：构造冲突较低的散列地址，保证散列表中数据的离散度。
除法散列法
散列长度 m, 对于一个小于 m 的数 p 取模，所得结果为散列地址。对 p 的选择很重要，一般取素数或 m
公式：f(k) = k % p （p<=m）
因为求模数其实是通过一个除法运算得到的，所以叫“除法散列法”
先通过求关键字的平方值扩大相近数的差别，然后根据表长度取中间的几位数作为散列函数值。又因为一个乘积的中间几位数和乘数的每一位都相关，所以由此产生的散列地址较为均匀。
公式：f(k) = ((k k) >> X) << Y对于常见的32位整数而言，也就是 f(k) = (k k) >> 28
平方散列法（平方取中法）
先通过求关键字的平方值扩大相近数的差别，然后根据表长度取中间的几位数作为散列函数值。又因为一个乘积的中间几位数和乘数的每一位都相关，所以由此产生的散列地址较为均匀。
公式：f(k) = ((k k) >> X) << Y对于常见的32位整数而言，也就是 f(k) = (k k) >> 28
斐波那契（Fibonacci）散列法
和平方散列法类似，此种方法使用斐波那契数列的值作为乘数而不是自己。
对于 16 位整数而言，这个乘数是 40503。
对于 32 位整数而言，这个乘数是 2654435769。
对于 64 位整数而言，这个乘数是 11400714819323198485。
公式：f(k) = ((k 2654435769) >> X) << Y
对于常见的32位整数而言，也就是 f(k) = (k 2654435769) >> 28
可以发现 0x61c88647 与一个神奇的数字产生了关系，它就是 (Math.sqrt(5) - 1)/2。也就是传说中的黄金比例 0.618（0.618 只是一个粗略值），即0x61c88647 = 2^32 * 黄金分割比。同时也对应上了上文所提到的斐波那契散列法。
随机数法
选择一随机函数，取关键字的随机值作为散列地址，通常用于关键字长度不同的场合。
公式：f(k) = random(k)
链地址法（拉链法）
懂了散列算法，我们再来了解下拉链法。拉链法是为了 HashMap 中降低冲突，除了拉链法，还可以使用开放寻址法、再散列法、链地址法、公共溢出区等方法。这里就只简单介绍了拉链法。
把具有相同散列地址的关键字(同义词)值放在同一个单链表中，称为同义词链表。有 m 个散列地址就有 m 个链表，同时用指针数组 T[0..m-1] 存放各个链表的头指针，凡是散列地址为 i 的记录都以结点方式插入到以 T[i] 为指针的单链表中。T 中各分量的初值应为空指针。