静态散列

1. 何为散列表

在静态散列方法中，把标识符存储在一个固定大小的表中，该表称为散列表。使用散列函数f确定标识符x在散列表中的地址。

2. 散列函数

散列函数的设计目的应该是计算简单并且能使冲突次数最少。对于任意的标识符x，可以等概率地散列到b个散列桶中，满足此性质的散列函数称为均匀分布散列函数。

这里记录几种均匀分布的散列函数：

• 平方取中法

假如x=59，平方值为3481，取其中值34为x的散列表地址

• 质数除余法

散列函数f=x%M，其中M的取值是关键，根据《数据结构》的说明，选择M较好的方法是，M首先是一个素数，且对于小整数k和a，M不能整除r^k +- a(r为字符集的基数),在实际应用中，可以选择满足上述和件且没有小于20的素因子的M。

• 折叠法
• 数字分析法

• 线性开放定址法

溢出发生时,即使用散列函数得到的地址已占用,最简单的方法是将该新元素插到最近的未满的散列桶中.

该方法的缺点很明显是极易产生标识符堆积,增加查找时间.

• 拉链法

拉链法的思想是引用链表处理冲突

散列表的性能仅依赖于处理溢出的方法.只要采用均匀分布散列函数,散列表的性能就与散列函数无关,但就不同散列函数的性能而言,质数除余法是一种理想的方法.