扫码获取更多资源

●哈希表

在顺序查找表和动态査找表中，由于记录的存储位置和关键字之间不存在确定的对应 关系，在查找时，只能通过一系列的给定值与关键字的比较，其算法均是建立在关键字“比 较”的基础上，查找效率依赖于查找过程中进行的给定值与关键字的比较次数。

理想的情况是不经过任何比较，直接得到待查记录的存储位置，查找的期望复杂度为 0（1）。这就必须在记录的存储位置和其关键字之间建立一个确定的对应关系，使得每个关 键字和唯一的一个存储位置相对应。在查找时，根据此对应关系找到给定值映射，如果查找 表中存在这个记录，则必定在该映射的位置上。这种查找方法称为哈希（Hash）方法，因为 Hash的原意本是杂凑，因此也称为杂凑方法。

哈希表的定义

设任意给定的关键字集合记为K,设定一个函数H将K映射到表T[0 .. m-1]的下 标上，这样以K中记录的关键字为自变量，以H为函数的运算结果就是相应记录的存储地 址，从而达到在0（1）时间内就可以完成记录查找，如图8-34所示。

哈希造表的过程分为两步：

(1)存储记录：通过哈希函数计算记录的哈希地址，并按此地址存储该记录。

(2)查找记录：通过同样的哈希函数计算记录的哈希地址，并按此地址访问该记录。

由此可见，哈希既是一种存储方法，也是一种查找方法。但哈希表不是一种完整的存储 结构，因为它只是通过记录的关键字来定位该记录，很难完整地表达记录之间的逻辑关系， 所以哈希表主要是面向查找的存储结构。 在哈希造表中，由于记录定位主要基于哈希函数的计算，不需要进行关键字的多次比 较，因此在一般情况下，哈希方法的查找速度要比前面介绍的基于关键字比较的查找方法的 查找速度高。但哈希方法一般不适用于允许多个记录有相同关键字的情况，也不适用于范 围查找。也就是说，在哈希表中，不可能找到最大或最小关键字的记录,也不可能找到在某一 范围内的记录。哈希方法最适合回答的问题是：如果有，则那个记录的关键字等于待查值。

2.哈希表的冲突 哈希造表是通过哈希函数建立从记录关键字集合到哈希表地址集合的一个映射，而哈 希函数的定义域是查找集合中全部记录的关键字，如果哈希表有m个地址单元，哈希函数 的值域必须在0〜m—1之间，这就产生了如何设计哈希函数的问题。 在理想情况下，对任意给定的记录关键字集合K,如果选定了某个理想的哈希函数H 及相应的哈希表T,则对K中的每个记录在哈希表T中都有唯一对应的哈希地址，但在实 际应用中这种情况很少出现。在大多数情况下，往往会岀现这样的情况：对于两个不同的 关键字k^k2,有H(k]) = H(kQ,即两个不同的记录需要存放在同一个存储位置中，这种 现象称为冲突(Collision),此时，k】和k2相对于H称作同义词(Synonym) 0例如图8-34中 的k2和k5的哈希地址相同，发生冲突。 如果记录按哈希函数计算出的地址加入哈希表时产生了冲突，就必须另外再找一个地 方来存放它，这就产生了如何处理冲突的问题。 因此，采用哈希方法需要考虑的两个主要问题是：一是哈希函数的设计，二是冲突的处理。

联系我们：