散列表查找-数据结构与算法:Java版-散列查找

前面讨论的各种查找方法是建立在给定值和记录关键字比较的基础上的。查找效率依赖于元素的数量和查找过程中所进行的比较次数。理想的情况是不经过任何比较，通过计算就能直接得到记录所在的存储地址，散列表查找（Hashed Search），又称为哈希查找，就是基于这一设计思想的一种查找方法。

散列是一种重要的存储方式，又是一种查找方法。按散列存储方式构造的存储结构称为散列表（Hashed Table）。散列的核心是散列函数（Hashed Function），又称哈希函数。每个记录的关键字通过哈希函数计算都对应得到记录的存储地址：i=Hash(key)。Hash函数实际上就是关键字到存储地址的映射，这样，查找时也可以先根据关键字计算其存储地址，然后就可以直接找到该数据元素了。

【例7.7】已知某校某届的1 000个学生的记录构成散列表。其中关键字是学生的学号，学号由8位十进制数字组成，从左算起的前4位是进校年份，如“2018”，这1 000个学生都一样，第五位是系的编号，第六、七、八位是该届所有学生的编号，没有重复。

解：可以把这1 000个学生的记录存储在一个长为1 000的散列表中，即HashTable[1000]。散列地址i通过散列函数Hash(key)来计算，令Hash(key)=key%1000，则HashTable[i]中放入的学生记录就是学号后3位为i的学生记录。如Hash（“20181233”）=233，学号为“20181233”的学生的记录存放在散列表HashTable[1000]中233号地址中。

建立散列表的过程需要对每个记录的关键字进行散列函数的运算，计算出该记录存储的地址，并将记录存入此地址中。理想的散列函数使每一个记录和存储的地址一一对应，没有冲突。这样，查找每个记录所花的时间只是计算散列函数的时间，效率很高，而且查找每一个记录所花的时间相等。若不同记录的关键字经过散列函数运算后得到相同的地址，即key1≠key2时，Hash(key1)=Hash(key2)，则称之为发生冲突，将发生冲突的两个关键字称为散列函数的同义词。

在例7.7中，只有学生的编号后3位（第六、七、八位）不重复的情况下，才能有当key1≠key2时Hash(key1)≠Hash(key2)。若学生编号后3位出现重复，比如不同系的学生编号后3位都从1开始编码，但系的编码（第五位）不同，如Hash(“20181233”)=233，Hash(“20182233”)=233，学生编号不同，即key1≠key2，但Hash(key1)=Hash(key2)，造成了冲突。怎么办呢？(www.xing528.com)

有同学可能会想到，将地址空间扩大，比如现在把这1 000位学生存放到长为10 000的散列表，冲突会不会减少呢？此时如果不改变散列函数，冲突一点都没有减少，而且会产生大量的空闲空间，造成空间浪费。如果改变散列函数，比如Hash(key)=key%10000，此时散列后的地址能够分散在整个地址空间，但分布不均匀。而且有留级的学生时产生冲突的可能性比较大，比如Hash(20184221)=Hash(20174221)=4221，冲突。进一步继续改变散列函数，比如Hash(key)=key%9973，此时散列后的地址能够比较均匀地分布在整个空间中，使冲突的可能性减少，但并不能保证没有冲突，如Hash(20180001)=Hash(20189974)=4622，仍然有冲突，而且还是有大量的空闲空间，造成空间浪费。

散列后希望散列地址间没有冲突，又不浪费空间。从冲突方面考虑，需要设计不冲突的散列函数，但实际应用中，不发生冲突的理想化的散列函数极少存在，所以实际应用中还须考虑冲突发生时的处理办法。从空间方面考虑，可以让散列表空间大小与要存储的数据量大小相当。综上所述，散列查找必须考虑的两个主要问题如下。

（1）构造一个计算简单且冲突尽量少的地址分布比较均匀的散列函数。

（2）拟订解决冲突的方案。