3.7 散列查找（hash查找）
3.7.1 基本概念
散列函数
在进行查找时，在记录的存储位置与它的关键字之间建立一个确定的对应关系h,以线性表中每个元素的关键字K为自变量，通过函数h(K)计算出该元素的存储位置，我们将h函数称为散列函数或哈希函数。h(K)的值称为散列地址或哈希地址。 [1] 例：
假定一个线性表为A=(18,75,60,43,54,90,46)，选取散列函数为：
h(K)=K%m 取m=13
则得每个元素散列地址：
h(18)=18 % 13=5 h(75)=75 % 13=10 h(60)=60 % 13=8 h(43)=43 % 13=4
h(54)=54 % 13=2 h(90)=90 % 13=12 h(46)=46 % 13=7
根据散列地址，实现元素的存储映象H[m]：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| H | 54 | 43 | 18 | 46 | 60 | 75 | 90 |
冲突：在实际应用中，通常可能出现一个待插入元素的散列地址单元已被占用情况，使得该元素无法直接存入此单元，这种情况称为冲突。
同义词：具有不同关键字而具有相同散列地址的元素称为同义词，即key1≠key2，但h(key1)=h(key2)。由同义词引起的冲突称作同义词冲突。
例：如向下表中再插入元素70时，70%13=5，则出现了冲突
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| H | 54 | 43 | 18 | 46 | 60 | 75 | 90 |
装填因子(α)：指散列表中已存入的元素数n与散列表空间大小m的比值,即：α=n/m。当α越小时，冲突可能性就越小，但同时，存储空间利用率就越低。
散列表：根据设定的哈希函数及处理冲突的方法将一组关键字映象到一个有限的连续的地址集上，即把记录存放在表中映象的位置上，这种表便称为散列表(哈希表)。
一个散列表的好坏与三个因素有关：
- 装填因子
- 所采用的散列函数
- 解决冲突的方法
3.7.2 散列函数
构造散列函数的目标是使散列地址尽可能均匀分布在散列空间上，同时使计算尽可能简单，以节省计算时间。
直接定址法
以关键字K本身或关键字加上某个数值常量C作为散列地址的方法，对应的散列函数：
$$
h(K) = K+C(C为常数)
$$
除留余数法
以关键字K除以散列长度m所得余数作为散列地址的方法，对应的散列函数：
$$
h(K)=K 取余 m \
m:散列表长
$$
数字分析法
当关键码的位数很多时，可以通过对关键码的各位进行分析，丢掉分布不均的位，留下分布均与的位作为散列值。数字分析法只适合于静态的关键码值集合，当关键码值发生变化后，必须重新进行数字分析。这无疑限制了数字分析法在实际中的应用。
例：有一组关键字如下：
92326875
92739628
92343634
92706816
92774638
92381262
92394220
通过分析：每个关键字从左到右第1、2、3位和第6位取值较集中，不宜作散列地址，其余的第4、5、7、8位取值分散，可以选择，若取最后两位作散列地址，得：
(2,75,28,34,16,38,62,20)
平方取中法
取关键字平方的中间几位作为散列地址的方法，由平方取中法得到的散列地址同关键字的每一位都有关，使得散列地址有较好分散性。
它适用于关键字中每一位取值都不够分散或者较分散的位数小于散列地址所需要的位数的情况。
折叠法
首先将关键字分割成位数相同的几段(最后一段位数可少一些)，然后将它们的叠加和(舍去最高位进位)作为散列地址的方法。
随机乘数法
随机乘数法使用一个随机实数f(0≤f<1)。成绩f*key的分数部分在0―1之间，用这个分数部分的值与n（散列表的长度）相乘，乘积的整数部分就是对应的散列值，显然这个散列值落在0—n-1之间。
基数转换法
将关键码值看成是在另一个基数数制上的书，然后把它转化成原来基数上的数，再选择其中的若干位作为散列值。一般取大于原来基数的数作为转换的基数，并且两个基数应该是互素的。
例子：采用基数转换法，计算十进制关键码值key=852422241的散列值，取转换基数为13，则有：=8 * 5 *
取转换后的数值的中间4为数字作为散列值，于是Hash(key)=0789。
引用：
1.散列查找
