TOC
直接寻址
相对于哈希表来说，直接寻址是一种更为简单的方法，即使用一组键集合 K 来代表一组相应的值 U,但是直接寻址受限于一个重要的缺陷，即K可能相比较于U会小很多，并且会出现数组浪费情况，很多槽都可能是空的，注意这里和是OOP里面的对象键值对没有联系，哈希表都是以数组的形式出现的，因为只有当自身是数组的时候，才能做到最快速的偏移，因为数组在绝大多数语言之中都是以一段连续的内存出现的，这就是为什么哈希表做到O(1)访问的原因。
哈希表
哈希表（散列表）是一种直接寻址技术的增强，其核心思想在于，对原本的关键字进行一次hash()，也就是说，其在表中真正的key是
hash(k)。
散列表的最大好处就是利用hash缩减了数组的大小。
但这会引发一个问题，即如果多次插入一个相同关键字，那么可能会插入一个相同的槽中，这被称为*碰撞*或者是*冲突*（collision）。
对于这种情况，我们拥有一些解决方案
链接法
链接法是一种最为简单的解决冲突方案，当链接法遇见冲突的时候，就将同一插槽的元素合并成一个链表，并把插槽的指针指向链表的头部。
所以我们可以预见当整个关键字集合基本相同时，我们将得到一个超长的列表，这时候所谓的表的概念会变得模糊，这也是链接法最差情况。Θ(n)
这里我们还需要引申出一个概念，装载因子 α 即 n / m 也就是当key为n个槽为m个的时候，每个槽平均对应多少个key,在hash算法为尽量平均分布的时候，我们的查找时间就是 O(1 + α),由此可以看出，我们的哈希表时间复杂度和hash算法相关。并且分配越平均，越快。当然最快的情况肯定是一个键对应一个槽
链接法性能分析
既然我们的操作效率和hash算法非常相关，那么，什么样的hash函数才是一个号的hash函数呢？
让我们看看我们的目标
- 我们想要把key均匀分布到slot
- 他的输出不会过于和key的输入相关 比如输入偶数必然输出某个值
除法hash法
这就是一种经典的快速hash算法
h(k) = k mod m
> k = 原始key m = hashTable的长度
但要注意，m也就是表的长度最好选择一个质数，否则其平均分布的特性会大打折扣
当然还有一些别的的hash方法，比如乘法hash
解决碰撞之二 开放寻址法
开放寻址法的核心思想是构建一个Hash序列，当序列中的hash1无法找到空位的时，继续调用hash2,知道hash出一个插槽正好是空时，插入。查找也很类似，需要注意的是，这种方法在槽中是需要保存原始关键字的，因为在搜索的时候，需要比对原始key是否一致。
这种方法最大的缺陷就是删除起来非常的麻烦。
开放寻址法性能分析
既然核心是一个hash队列，那么我们的性能明显就和Hash算法的速度，整个实际运行序列的长度相关。
线性探查
给定一个普通的散列函数，获取一次h(key) 接下来遍历数组进行遍历（从h(key开始)，到末尾，又从t[0]开始，到h(k) - 1 结束），查找空位并插入，这就是线性探查，整个序列的最大长度就是m,他的理解和实现都相当的简单，但是问题也是存在的，这就是一次群集 。说白了就是槽很容易一大片都是满的，这样就不能实现很快速的插入了。并且会越来越严重，因为你本身插入就是在满的后面的空位插入。
二次哈希
h(k,i) = (h_1(k) + ih_2(k))mod m
h_1 和 h_2 是hash函数 ，第i次的探查位置等于 上次探查的位置+这次计算出的hash模m,也就是说每次的探查会变的比较有跳跃性，并且和上一次探查相关，整体分布就会比较平均。