静态散列

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。

• 折叠法
• 数字分析法

综观以下方法，可看出散列函数的一个特性就是尽量体现对标识符所有位的全相关性。

3. 溢出处理

• 线性开放定址法

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

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

• 拉链法

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

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