构造哈希表的基础知识是软件评测师考试的重要考点，经常出现在上午场的客观选择题当中。根据设定的哈希函数H(key)和处理冲突的方法，将一组关键字映射到一个有限的连续的地址集(区间)上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表称为哈希表，也叫作散列表，这一映射过程称为哈希造表或散列，所得的存储位置称为哈希地址或散列地址。下面就该知识点并结合例题进行总结学习。
一、哈希表概述
哈希表通过以记录的关键字为自变量的函数(称为哈希函数)得到该记录的存储地址，在哈希表中进行查找操作时，需用同一哈希函数计算得到待查记录的存储地址，然后到相应的存储单元去获得有关信息。对于某个哈希函数H和两个关键字K1和K2，如果K1≠K2，而H(K1)=H(K2)，则称为冲突。具有相同哈希函数值的关键字对该哈希函数来说称为同义词。
二、利用线性探测法解决哈希表冲突
（1）概述：线性探查法是指在发生冲突时，顺序地到存储区的下一个单元进行探测。例如，某记录的关键字为key，哈希函数值H(key)=j。若在哈希地址j发生了冲突(即此位置已存放了其他元素)，则对哈希地址j+1进行探测，若仍然有冲突，再对地址j+2进行探测，依此类推，直到将元素存入哈希表。构造的函数如下：
Hi=(Hash(key)) %m
i=1，2，…，k (k≤m-1)，其中，Hash(key)为哈希函数；m为哈希表的表长；%是取余操作。
（2）实例：设关键码序列为（47，34，13， 12，52，38，33，27，3），哈希表表长为11, 哈希函数为Hash(key)=key%11，则：
Hash(47)=47%11= 3；放入编号为3的哈希表中；
Hash(34)=34%11= 1；放入编号为1的哈希表中；
Hash(13)=13%11 =2；放入编号为2的哈希表中；
Hash(12)=12%11= 1；因为编号为1的位置已经被34所占，所以按顺序到下一个编号为2的位置查看是否被占用，结果被13所占，继续寻找下一个编号唯3的位置，发现被47所占，继续寻找下一个编号为4的位置，发现没有被占用，所以放入编号为4的位置上；
Hash(52)=52%11= 8；放入编号为8的哈希表中；
Hash(38)=38%11 =5；放入编号为5的哈希表中；
Hash(33)=33%11 =0；放入编号为0的哈希表中；
Hash(27)=27%11 =5；因为编号为5的位置已经被38所占，所以按顺序到下一个编号为6的位置查看是否被占用，发现没有被占用，所以放入编号为6的位置上；
Hash(3)=3%11 = 3；因为编号为3的位置已经被47所占，所以按顺序到下一个编号为4的位置查看是否被占用，结果被12所占，继续寻找下一个编号为5的位置，发现被38所占，继续寻找下一个编号为6的位置，发现被27所占，继续寻找下一个编号为7的位置，发现没有被占用，所以放入编号为7的位置上；
最终使用线性探测法解决冲突构造的哈希表如下：
下面是近几年对该知识点考察过的真题，以后仍是考试出题的重点，大家要重视起来。
【2018年第25题】对于关键字序列(10，34，37，51，14，25，56，22，3)，用线性探查法解决冲突构造哈希表，哈希函数为H(key) = key % 11，关键字25存入的哈希地址编号为（ ）。
A、2
B、3
C、5
D、6
解析：本题考查构造哈希表的基础知识。
通过哈希函数为H(key) = key % 11可知，表长为11，编号从0-10。首先对关键字序列(10，34，37，51，14，25，56，22，3)通过key%11计算得到对应的值序列（10，1，4，7，3，3，1，0，3）。需要注意的是，我们的序列是按照顺序依次进行存放的，具体过程参考上面的例题，本题的详细过程大家可以自己通过构造哈希表进行验证。
本题25代入哈希值为3，其中3已被14所占，后退一位4号被37占用，其中5号为空，所以25应该存入标号为5的位置。
故正确答案为：C
作者唯一官方个人微信公众号（昊洋与你一起成长）：HYJY20180101
写于2021年10月18日
作者：昊洋讲师
版权所有，侵权必究
