一、散列表

1.散列表概念

基本思想：记录存储位置与关键字之间存在对于关系

 通过一个函数，将关键字的值计算成地址用于存放
对应函数：Loc(i) = H(keyi)

1.例子：

H(key) = 取key的最后两位

将学号通过最后两位直接对应到相应的位置

优缺点：查找效率高，但是空间效率低。查找仅一次计算

2.术语：

2.1. 散列方法（杂凑法）：

选取某个函数，依该函数按关键字计算元素的存储位置，并按此存放。
查找时，由同一个函数对给定值k计算地址，将k与地址单元在元素关键码进行对比，确定查找是否成功。

2.2散列函数（杂凑函数）：

散列方法中使用的转换函数 

2.3.散列表（杂凑表）：

按上述思想构造的表

2.4.冲突：

不同关键码映射到同一个散列地址 ，key1 ！= key2 ，但是H（key1） = H（key2）

在散列表查找方法中，冲突是不可避免的，只能尽可能减少。

解决方法：1.构造好的散列函数：函数要简单并且计算出的地址应该集中致均匀分布  
                  2.制定一个好的解决冲突的方案

3.函数的构造方法：

3.1 函数的构造的考虑因素

1.执行速度
2.关键字的长度
2.散列表的大小
4.关键字的分布情况
5.操作频率

3.2集合的构造方法

1.具有的性质
n个数据原理仅占用n个地址，虽然散列表是以空间换时间，但是还需要散列空间尽量小。

2.构造方法

1.直接定址法：

以关键码key的某个线性函数值为散列地址，不会产生冲突。
缺点：空间使用率低，要占用连续地址空间 

2.除留余数法

Hash(key) = key mod p( p是一个整数  )   p一般小于等于表长且为质数

4.解决冲突的方法：

4.1开放定址法：

思想：有冲突就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将数据元素存入

例子：

伪随机方法：是能找到哪一个就存在哪一个

4.2 ：链地址法（拉链法）

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

理解：将冲突的的数据在这个地址上用单链表的形式表示。

链表上系欸但空间动态申请，适合于表长不确定的情况，

2.散列表的查找

3.哈希表的查找效率分析

1.散列函数
2.处理冲突的方法
3.散列表的装填因子（表中填入的记录数/哈希表的长度）

装填因子对打，表中记录数越多，表明表装的越满，发生冲突的可能性就越大