# 散列

散列（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) = random(k)

# 斐波那契（Fibonacci）散列法

当我们查看 ThreadLocal 执行设置元素时，有这么一段计算哈希值的代码；

private static final int HASH_INCREMENT = 0x61c88647;

private static int nextHashCode() {
    return nextHashCode.getAndAdd(HASH_INCREMENT);
}

ThreadLocal 使用的就是 斐波那契（Fibonacci）散列法 + 开放寻址法存储数据到数组结构中。之所以使用斐波那契数列，是为了让数据更加散列，减少哈希碰撞。具体来自数学公式的计算求值。
公式：

f(k) = ((k * 2654435769) >> X) << Y
对于常见的32位整数而言，也就是 f(k) = (k * 2654435769) >> 28

# todo

通过数据对散列程度进行比对