数据结构-散列表

一、Hash 冲突可以避免？

Hash 冲突是肯定存在的，但是可以 尽量 避免

散列均匀：元素远小于存储空间的时候，避免冲突，要有好的 hash 算法。

二、散列冲突的解决方法

• 为什么 Java 的 Map 使用了 16 个 Entry？
  $2^n$ 可以使用 位运算 替换 模运算，速度比较快。

java 中 Hash 冲突（碰撞）的解决方法
链表的方式（1.7）
红黑树（1.8）
线性探测（ThreadLocalMap）

1. 开放定址法（开地址法）

1.1 线性探测法

1.2 二次探测法

散列函数：

$$H_i = (Hash(key) + d_i) \mod m$$

其中，m 为散列表长度，m 要求是某个 4k+3 的质数；$d_i$ 为增量序列：

$$1^2, -1^2, 2^2, -2^2, ..., q^2$$

1.3 伪随机探测法

$H_i = (Hash(key)+d_i) \mod m (1 =< i < m)$
其中，mod 为散列长度，$d_i$ 为伪随机数。

2. 链地址法（拉链法）

基本思想：相同散列地址的记录链成一个单链表。

m 个散列地址就设 m 个单链表，然后用一个数组将 m 个单链表的表头指针存储起来，形成一个动态的结构。

散列表的装填因子 $a$：$$a = \frac{表中填入的数据}{哈希表的长度}$$

散列表技术具有很好的平均性能，优于一些传统的技术；
链地址法优于开地址法；
除留取余法作散列函数优于其它类型函数（取小于等于表长的一个质数）。