散列表（一）：散列表概念、 散列函数构造方法、 常见字符串哈希函数（测试冲突）

一、散列表基本概念

1、散列表(hash table) ，也叫哈希表，是根据关键码而直接进行访问的数据结构。也就是说，它通过把关键码映射到表中一个位置

来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

2、若结构中存在关键码为x的记录，则必定在hash(x)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系hash

为散列函数(hash function)，按这个思想建立的表为散列表。

举个例子：

影碟出租店维护一张表格，以电话号码作为关键码，为了提高查找速度，可以用选择哈希表进行存储

假设影碟出租店有一万张光碟，每天借出与归还均不超出500人次。因此哈希表维护500条记录即可。

我们发现真正要存储的记录比关键码总数（假设8位电话，则关键码总数2^8 个）要少得多。

散列地址冲突

3、散列函数是一个压缩映象函数。关键码集合比散列表地址集合大得多。因此有可能经过散列函数的计算，把不同的关键码映射到

同一个散列地址上，这就产生了冲突 (Collision)。即key1≠ key2，而hash(key1)=hash(key2)，这种现象称冲突。我们将key1与key2称

做同义词。

4、由于关键码集合比地址集合大得多，冲突很难避免。所以对于散列方法，需要讨论以下两个问题：

对于给定的一个关键码集合，选择一个计算简单且地址分布比较均匀的散列函数，避免或尽量减少冲突；

拟订解决冲突的方案。

散列函数选取原则

5、散列函数的选择有两条标准：简单和均匀

简单指散列函数的计算简单快速，能在较短时间内计算出结果。

均匀指散列函数计算出来的地址能均匀分布在整 个地址空间。若key是从关键字码集合中随机抽取的一个关键码，散列函数能

以等概率均匀地分布在表的地址集{0，1，…，m-1}上，以使冲突最小化。

二、散列函数构造方法

（一）、直接定址法

此类函数取关键码的某个线性函数值作为散列地址：hash ( key ) = a * key + b { a, b为常数 }

这类散列函数是一对一的映射，一般不会产生冲突。但是，它要求散列地址空间的大小与关键码集合的大小相同。

（二）、数字分析法

构造：对关键字进行分析，取关键字的若干位或其组合作哈希地址。
适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况。

例： 有80个记录，关键字为8位十进制数，哈希地址为2位十进制数

（三）、平方取中法

取关键字平方后中间几位作哈希地址。适于关键字位数不定情况。

具体方法：先通过求关键字的平方值扩大相近数的差别，然后根据表长度取中间的几位数作为散列函数值。又因为一个乘积的中间

几位数和乘数的每一位都相关，所以由此产生的散列地址较为均匀。（ps：不理解内码的含义）

（四）、折叠法

此方法把关键码自左到右分成位数相等的几部分，每一部分的位数应与散列表地址位数相同，只有最后一部分的位数可以短一些。

把这些部分的数据叠加起来，就可以得到具有该关键码的记录的散列地址。有两种叠加方法：

移位法 — 把各部分的最后一位对齐相加；

分界法 — 各部分不折断，沿各部分的分界来回折叠，然后对齐相加，将相加的结果当做散列地址。

一般当关键码的位数很多，而且关键码每一位上数字的分布大致比较均匀时，可用这种方法得到散列地址。

示例：设给定的关键码为 key = 23938587841，若存储空间限定 3 位, 则划分结果为每段 3 位. 上述关键码可划分为 4段：

把超出地址位数的最高位删去, 仅保留最低的3位，做为可用的散列地址。

（五）、随机数法

选择一个随机函数，取关键字的随机函数值为它的散列地址，即hash(key) = random(key) ；其中random为伪随机函数，但要保证函

数值是在0到m-1之间。

（六）、除留余数法

设散列表中允许的地址数为 m, 散列函数为：

hash ( key ) = key % p p <= m

若p取100，则关键字159、259、359互为同义词。我们选取的p值应尽可能使散列函数计算得到的散列地址与各位相关，根据经

验，p最好取一个不大于 m，但最接近于或等于 m 的质数 p, 或选取一 个不小于 20 的质因数的合数作为除数（比如8 = 2*2*2，2 是

8 的质因数，8 是合数）

示例：有一个关键码 key = 962148，散列表大小 m = 25，即 HT[25]。取质数 p= 23。散列函数 hash ( key ) = key % p。则散列地址

为 hash ( 962148 ) = 962148 % 23 = 12

可以按计算出的地址存放记录。需要注意的是，使用上面的散列函数计算出来的地址范围是 0到 22，因此，从23到24这几个散列地

址实际上在一开始是不可能用散列函数计算出来的，只可能在处理溢出时达到这些地址。

（七）、乘余取整法

使用此方法时，先让关键码 key 乘上一个常数 A (0 < A < 1)，提取乘积的小数部分。然后，再用整数 n 乘以这个值，对结果向下取

整，把它做为散列的地址。散列函数为：

三、常见字符串哈希函数

下面列出常见的8个字符串哈希函数，这些都是计算机科学家们研究出来的，计算出来的哈希地址比较平均，冲突较少，但还是会存

在冲突，另外在使用这些函数时，记得在return 的值后面再 % 地址总数，这样得出的地址才会在范围内。

C++ Code

<nobr>1<br> 2<br> 3<br> 4<br> 5<br> 6<br> 7<br> 8<br> 9<br> 10<br> 11<br> 12<br> 13<br> 14<br> 15<br> 16<br> 17<br> 18<br> 19<br> 20<br> 21<br> 22<br> 23<br> 24<br> 25<br> 26<br> 27<br> 28<br> 29<br> 30<br> 31<br> 32<br> 33<br> 34<br> 35<br> 36<br> 37<br> 38<br> 39<br> 40<br> 41<br> 42<br> 43<br> 44<br> 45<br> 46<br> 47<br> 48<br> 49<br> 50<br> 51<br> 52<br> 53<br> 54<br> 55<br> 56<br> 57<br> 58<br> 59<br> 60<br> 61<br> 62<br> 63<br> 64<br> 65<br> 66<br> 67<br> 68<br> 69<br> 70<br> 71<br> 72<br> 73<br> 74<br> 75<br> 76<br> 77<br> 78<br> 79<br> 80<br> 81<br> 82<br> 83<br> 84<br> 85<br> 86<br> 87<br> 88<br> 89<br> 90<br> 91<br> 92<br> 93<br> 94<br> 95<br> 96<br> 97<br> 98<br> 99<br> 100<br> 101<br> 102<br> 103<br> 104<br> 105<br> 106<br> 107<br> 108<br> 109<br> 110<br> 111<br> 112<br> 113<br> 114<br> 115<br> 116<br> 117<br> 118<br> 119<br> 120<br> 121<br> 122<br> 123<br></nobr>

unsignedintSDBMHash(char*str) { unsignedinthash=0; while(*str) { //equivalentto:hash=65599*hash+(*str++); hash=(*str++)+(hash<<6)+(hash<<16)-hash; } return(hash&0x7FFFFFFF)%BUCKETS; } unsignedintRSHash(char*str) { unsignedintb=378551; unsignedinta=63689; unsignedinthash=0; while(*str) { hash=hash*a+(*str++); a*=b; } return(hash&0x7FFFFFFF); } unsignedintJSHash(char*str) { unsignedinthash=1315423911; while(*str) { hash^=((hash<<5)+(*str++)+(hash>>2)); } return(hash&0x7FFFFFFF); } unsignedintPJWHash(char*str) { unsignedintBitsInUnignedInt=(unsignedint)(sizeof(unsignedint)*8); unsignedintThreeQuarters=(unsignedint)((BitsInUnignedInt*3)/4); unsignedintOneEighth=(unsignedint)(BitsInUnignedInt/8); unsignedintHighBits=(unsignedint)(0xFFFFFFFF)<<(BitsInUnignedInt-OneEighth); unsignedinthash=0; unsignedinttest=0; while(*str) { hash=(hash<<OneEighth)+(*str++); if((test=hash&HighBits)!=0) { hash=((hash^(test>>ThreeQuarters))&(~HighBits)); } } return(hash&0x7FFFFFFF); } unsignedintELFHash(char*str) { unsignedinthash=0; unsignedintx=0; while(*str) { hash=(hash<<4)+(*str++); if((x=hash&0xF0000000L)!=0) { hash^=(x>>24); hash&=~x; } } return(hash&0x7FFFFFFF); } unsignedintBKDRHash(char*str) { unsignedintseed=131;//31131131313131131313etc.. unsignedinthash=0; while(*str) { hash=hash*seed+(*str++); } return(hash&0x7FFFFFFF); } unsignedintDJBHash(char*str) { unsignedinthash=5381; while(*str) { hash+=(hash<<5)+(*str++); } return(hash&0x7FFFFFFF); } unsignedintAPHash(char*str) { unsignedinthash=0; inti; for(i=0;*str;i++) { if((i&1)==0) { hash^=((hash<<7)^(*str++)^(hash>>3)); } else { hash^=(~((hash<<11)^(*str++)^(hash>>5))); } } return(hash&0x7FFFFFFF); }

下面使用第一个哈希函数，写个小程序测试一下是否会产生冲突：

C++ Code

<nobr>1<br> 2<br> 3<br> 4<br> 5<br> 6<br> 7<br> 8<br> 9<br> 10<br> 11<br> 12<br> 13<br> 14<br> 15<br> 16<br> 17<br> 18<br> 19<br> 20<br> 21<br> 22<br> 23<br> 24<br> 25<br> 26<br> 27<br> 28<br> 29<br> 30<br> 31<br> 32<br> 33<br> 34<br> 35<br> 36<br> 37<br> 38<br> 39<br> 40<br> 41<br> 42<br> 43<br> 44<br> 45<br> 46<br> 47<br> 48<br> 49<br> 50<br></nobr>

#include<stdio.h> #defineBUCKETS101 unsignedintSDBMHash(char*str) { unsignedinthash=0; while(*str) { //equivalentto:hash=65599*hash+(*str++); hash=(*str++)+(hash<<6)+(hash<<16)-hash; } return(hash&0x7FFFFFFF)%BUCKETS; } intmain(void) { char*keywords[]= { "auto","break","case","char","const","continue","default","do", "double","else","enum","extern","float","for","goto","if", "int","long","register","return","short","signed","sizeof","static", "struct","switch","typedef","union","unsigned","void","volatile","while" }; //哈希表每个地址的映射次数 //0地址的映射次数用count[0]表示 intcount[BUCKETS]={0}; inti; intsize=sizeof(keywords)/sizeof(keywords[0]); for(i=0;i<size;i++) { intpos=SDBMHash(keywords[i]); count[pos]++; } for(i=0;i<size;i++) { intpos=SDBMHash(keywords[i]); printf("%-10s%d%d\n",keywords[i],pos,count[pos]); } return0; }

可以看出，确实会产生冲突，比如有3个词语 default、extern、for 都映射到了地址16上。