哈希表

哈希表又叫散列表

散列函数:一个把查找表中的关键字映射成该关键字对应的地址的函数。

散列表:根据关键字而直接进行访问的数据结构。他建立了关键字与存储地址之间的一种直接映射关系。

冲突:散列函数可能会把多个不同的关键字映射到同一地址下的情况。

散列函数

直接定址法

直接取关键字的某个线性函数值为散列地址。

Hash（key）=a*key +b，其中a,b为常数

方法简单，不会产生冲突，若关键字分布不连续，则会浪费空间

除留取余法

Hash（key）=key % p

假定散列表表长为m，取一个不大于m但最接近或等于m的质数p

平方取中法

这种方法取关键字的平方值的中间几位作为散列地址

适用于关键字的每位取值不均匀或均小于散列地址所需要的位数。

折叠法

将关键字分割成位数相同的几部分，然后取这几部分的叠加和作为散列地址

例如：5211252==》521+125+2=648

适用于关键字的位数多，而且关键字中的每位上数字分布大致均匀

处理冲突

开放定址法

是指可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放。

• 线性探测法即d=0，1，2，3，m-1，会产生堆积现象
• 平方探测法即平方查找，缺点是不能探测到散列表上的所有单元*（至少可以探测到一般单元）
• 再散列法即d=i*Hash2（key）
• 伪随机法即d=伪随机序列

拉链法

把所有同义词存放在一个线性链表中，这个线性链表由地址唯一标识，即散列表中每个单元存放该链表头指针。拉链法适用于经常进行插入和删除的情况

散列表查找

查找效率取决于：散列函数、处理冲突的方法和填装因子
填装因子=表中记录数/散列表长度

本作品采用《CC 协议》，转载必须注明作者和本文链接