哈希的基本概念.doc

- -.
- - 总结
哈希表及其查找★3◎4
　　哈希译自“hash”一词，也称为散列或杂凑。
　　哈希表查找的基本思想是：根据当前待查找数据的特征，以记录关键字为自变量，设计一个哈希函数，依该函数按关键码计算元素的存储位置，并按此存放；查找时，由同一个函数对给定值key计算地址，将key与地址单元中元素关键码进行比较，确定查找是否成功。哈希方法中使用的转换函数称为哈希函数（杂凑函数），按这个思想构造的表称为哈希表（杂凑表）。
　　对于n个数据元素的集合，总能找到关键码与存放地址一一对应的函数。若最大关键为m，可以分配m个数据元素存放单元，选取函数f(key)=key即可，但这样会造成存储空间的很大浪费，甚至不可能分配这么大的存储空间。通常关键码的集合比哈希地址集合大得多，因而经过哈希函数变换后，可能将不同的关键码映射到同一个哈希地址上，这种现象称为冲突（Collision）。映射到同一哈希地址上的关键码称为同义词。可以说，冲突不可能避免，只能尽可能减少。所以，哈希方法需要解决以下两个问题：
　　（1）构造好的哈希函数
　　① 所选函数尽可能简单，以便提高转换速度。
　　② 所选函数对关键码计算出的地址，应在哈希地址集中大致均匀分布，以减少空间浪费。
　　（2）制定解决冲突的方案
　　1．常用的哈希函数
　　（1）直接定址法
- -.
- - 总结
　　即取关键码的某个线性函数值为哈希地址，这类函数是一一对应函数，不会产生冲突，但要求地址集合与关键码集合大小相同，因此，对于较大的关键码集合不适用。如关键码集合为{100，300，500，700，800，900}，选取哈希函数为Hash(key)=key/100，则存放如表6-3所示。
表6-3 直接定址法构造哈希表
地址
0
1
2
3
4
5
6
7
8
9
关键码
100
300
500
700
800
900
　　（2）除留余数法
　　即取关键码除以p的余数作为哈希地址。使用除留余数法，选取合适的p很重要，若哈希表表长为m，则要求p≤m，且接近m或等于m。p一般选取质数，也可以是不包含小于20质因子的合数。
　　（3）数字分析法
　　设关键码集合中，每个关键码均由m位组成，每位上可能有r种不同的符号。
　　数字分析法根据r种不同的符号及在各位上的分布情况，选取某几位，组合成哈希地址。所选的位应是各种符号在该位上出现的