散列表的概念
- 散列函数：一个把查找表中的关键字映射成该关键字对应的地址的函数。
- 散列表：根据关键字而直接进行访问的数据结构。建立可关键字与存储地址之间的一种直接映射关系。
- 冲突：散列函数可能会把多个不同的关键字映射到同一个地址下。
散列函数的构造方法
Hash（key）=Addr
- 要求
- 散列函数的定义域必须包含全部需要存储的关键字，而值域的范围则依赖于散列表的大小或地址范围。
- 散列函数计算出来的地址应该能等概率，均匀分布在整个地址空间中，从而减少冲突的发生。
3.散列函数应尽量简单，能够在较短时间内计算出任一关键字对应的散列地址。
- 构造方法
- 直接定址法——直接取关键字的某个线性函数值为散列地址。
Hash(key)=a*key+b;其中a，b为常数
特点：方法简单，不会产生冲突，但容易浪费空间。
直接定址法.JPG -
除留取余法——Hash(key)=key%p
选好p是关键，可以减少冲突的可能。
假定散列表表长为m，取一个不大于m但最接近或等于m的质数p
除留取余法.JPG - 数字分析法——选取关键字的几位作为散列地址，这几位的特点是：他们的出现是均匀的，不重复的。
- 平方取中法——取关键字的平方的中间几位作为散列地址。
特点：适用于关键字的每位取值不均匀或小于散列地址所需要的位数。 - 折叠法——将关键字分割成位数相同的几部分，然后取这几部分的叠加和作为散列地址。
特点：适用于关键字的位数较多，而且关键字中的每位上数字分布大致均匀。
冲突处理的方法
-
开放地址法
——是指可存放新表项的空闲地址既向它的同义词表项开放，有向它的非同义词表项开放。
Hi=(H(key)+di)%m,m为散列表表长，di为增量序列
特点：在开放定址法中不能随便删除某个元素，因为会产生空单元，使得查找终端。
如何计算增量序列
①线性探查法
线性探测法.JPG
查找：查找到空闲单元说明，待查值未在散列表中。
缺点：堆积现象大大降低查找效率。
②平方探测法di=02,12,-12,22,-22...k2,-k^2,
特点：避免堆积问题，缺点是不能探测到散列表上的所有单元。
③再散列法——di=i*Hash2(key)
④伪随机序列法——di= 伪随机序列 -
拉链法
——把所有的同义词存放在一个线性链表中，这个线性链表由地址唯一标识，即散列表中每个单元存放该链表头指针。
特点：适用于经常进行插入和删除的情况。
拉链法.JPG
散列表的查找查找
初始化：Addr=Hash(key)
①检测查找表中地址为Addr的位置上是否有记录，若无记录，则返回查找失败，若有记录，则比较它与key值，若相等则返回成功，否则执行步骤②。
②用给定的处理冲突方法计算“下一散列地址”，把Addr置为此地址，转入步骤①。
散列表性能分析
与下列因素有关
- 散列函数
- 处理冲突的方式
- 填装因子
——一般记为α，表示表的装满程度=表中记录数n/散列表长度m
散列表的平均查找长度依赖于散列表的填装因子。
