散列表按照key来存取很快，O(1)，但是其存储是无序的，因此不支持有序遍历。

将大的输入数据，转换为小的整数，以便作为下标之类的来使用。

好的散列函数应当满足：

1. 高效地计算
2. 一致地分布key。使用相同散列函数的散列表，key的分布应当相同。

设n为总的元素数量，k为哈系表中槽的数目，那么:

load factor = n/k

载荷因子越大，哈系表越慢，甚至工作不正常。要保证哈系表达到常数级别的时间复杂度，必须保证load factor处在一定值以下。

如果两个key的hash值相同，后者插入时就会发现位置已被占据，这时就需要碰撞处理

将每个位置弄成链表，将冲突的元素都存进去，读取时遍历链表。

优点：

• 易于实现
• 哈希表永远都不会装满
• 对哈希函数、载荷因子较为不敏感
• 经常用于key的数量与插入/删除的频率未知的情况

缺点：

• 缓存性能不如开放地址法
• 浪费空间，哈系表的一些部分永远不会用到
• 如果链变得很长，搜索时间在最差情况下会退化到O(n)
• 需要额外的空间，来构建链表

设m为哈系表里的槽数，n为要插入的key的数量，链式法的性能:

Load factor α = n/m
期望搜索时间 = O(1 + α)
期望插入/删除时间 = O(1 + α)

可知，如果Load factor α为O(1)，那么搜索、插入、删除的时间复杂度为O(1)

在开放地址法中，所有元素都被存放在哈系表中。所以在任何时刻，哈系表的大小必须大于等于key的总数。

• insert(k)：持续探测，直到找到一个空槽。
• search(k)：持续探测，直到槽中的key不等于k，或者找到空槽。
• delete(k)：如果简单地把k移除，有可能会导致搜索失败。应当把该位置标记为“已删除”，插入时可以插入到已删除的位置，搜索时需要跳过删除的位置继续搜索。

如果槽hash(x) % S已满，我们就探测(hash(x) + 1) % S。如果也满了，我们就探测(hash(x) + 2) % S...

线性探测法的最大问题就是，相似的元素容易聚集在一起，导致寻找新的空槽、搜索所需时间上升。

依次探测一下槽：hash(x) % S => (hash(x) + 1*1) % S => (hash(x) + 2*2) % S => (hash(x) + 3*3)

使用另一个哈希函数，再hash一遍：hash(x) % S => (hash(x) + 1*hash2(x)) % S => (hash(x) + 2*hash2(x)) % S => (hash(x) + 3*hash2(x)) % S

线性探测法有最好的缓存性能，易于实现，但是会有相似元素聚集的问题。

双重哈希法拥有最差的缓存性能，但是没有相似元素聚集的问题。双重哈希也需要更多的时间来计算。

二次探测法介于两者之间。

缺点：

• 需要额外处理相似元素聚集、load factor问题

优点：

• 更好的缓存性能
• 不浪费空间
• 不需要额外空间，来构建链表

设m为哈系表中的槽数，n为所有插入的key的总数:

Load factor α = n/m  ( < 1 )
预期的搜索、插入、删除时间 < 1/(1 - α)