哈希表
哈希表：（数组和单向链表的结合体）
1.引入：
- 散列表（Hash table，也叫哈希表），是根据关键码值(关键字，对象的关键属性)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
- 散列查找法：（散列法）通过对元素的关键字值进行某种运算，直接求出元素的地址，不需要反复比较
- 散列函数和散列地址：存储位置P ， 关键字key， 建立函数关系H ，使 P=H(key) P就是散列地址，H是散列函数
- 散列表：用以存储散列函数计算得到相应散列地址的数据记录。通常散列表的存储空间是一个一维数组，散列地址P=H(key)是数组的下标，而每个数组元素之后可以类似认为其后有一个链表，就是计算后的散列地址是同一个的，依次相后链接，形成一个链表，每一个散列地址可能对应一个链表， 理解为：数组里是链表，链表里是结点
- 冲突和同义词：对不同的关键字可能得到同一散列地址，即k1≠k2，而f(k1)==f(k2)，这种现象称为冲突；具有相同函数值的关键字对该散列函数来说称做同义词。
- 数组在查询方面效率较高，随机增删效率低；而单向链表在查询方面效率较低，随机增删效率高；哈希表将二者结合在一起
- 散列表的缺陷：（1）散列技术一般不适合在允许多个记录有同样关键码的情况下使用。（2）散列方法也不适用于范围查找，比如查找最大值或者最小值，为散列表的值是类似函数的，映射函数一个变量只能对应一个值，不知道其他值，也不能查找最大值、最小值；
2. 实现散列函数
除留余数法： H(key)=key mod p
这个方法的关键在于如何选取 P，使得利用率较高并且冲突率较低，一般情况下，我们会选取最接近表长且小于等于表长的最大素数。
3.处理冲突
建立公共溢出区：
散列表包含基本表和溢出表两部分（通常溢出表和基本表的大小相同），将发生冲突的记录存储在溢出表中。
查找时，如果在基本表里找的到就返回成功，没找到就在溢出区顺序查找，注意这里不再是映射而是顺序查找，放置时也是按照顺序的方式。
例如：
Key的集合为：47 ，7，29，11，27，92，22，8，3
散列函数为H(key)=key mod 11
| 基本表 | 溢出表 | ||
|---|---|---|---|
| 0 | 11 | 29 | |
| 1 | 22 | ||
| 2 | 47 | 3 | |
| 3 | 47 | ||
| 4 | 92 | ||
| 5 | 27 | ||
| 6 | |||
| 7 | 7 | ||
| 8 | 8 | ||
| 9 | |||
| 10 |
算法流程
-
假设给定的值为 K，根据所设定的散列函数 h，计算出散列地址 h(K)；
-
如果将该地址中的值与 K 比较，若相等则检索成功，跳转到第 5 步；
-
否则，按建表时设定的处理冲突方法查找探查序列的下一个地址,反复执行并检查
- 如果某个地址空间未被占用（查找不成功，可以插入），跳转到第 5 步；
- 如果关键码比较相等（有重复记录，不需要插入）为止 ，跳转到第 5 步；
-
如果探测完整个 hash 表，都没有进行插入或查找失败，跳转到第 5 步；
-
end 算法结束。