哈希表及其应用.docVIP

哈希表及其应用 一、定义 二、基本原理 哈希表的基本原理是：使用一个下标范围比较大的数组A来存储元素，设计一个函数h，对于要存储的线性表的每个元素node，取一个关键字key，算出一个函数值h(key)，把h(key)作为数组下标，用A[h(key)]这个数组单元来存储node。也可以简单的理解为，按照关键字为每一个元素“分类”，然后将这个元素存储在相应“类”所对应的地方（这一过程称为“直接定址”）。 但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了“冲突”，换句话说，就是把不同的元素分在了相同的“类”之中。例如，假设一个结点的关键码值为key，把它存入哈希表的过程是：根据确定的函数h计算出h(key)的值，如果以该值为地址的存储空间还没有被占用，那么就把结点存入该单元；如果此值所指单元里已存了别的结点（即发生了冲突），那么就再用另一个函数I进行映象算出I(h(key)),再看用这个值作为地址的单元是否已被占用了，若已被占用，则再用I映象，……，直到找到一个空位置将结点存入为止。当然这只是解决“冲突”的一种简单方法，如何避免、减少和处理“冲突”是使用哈希表的一个难题。 在哈希表中查找的过程与建立哈希表的过程相似，首先计算h(key)的值，以该值为地址到基本区域中去查找。如果该地址对应的空间未被占用，则说明查找失败，否则用该结点的关键码值与要找的key比较，如果相等则检索成功，否则要继续用函数I计算I(h(key))的值，……。如此反复到某步或者求出的某地址空间未被占用（查找失败）或者比较相等（查找成功）为止。 三、基本概念和简单实现 1、两个集合：U是所有可能出现的关键字集合；K是实际存储的关键字集合。 2、函数h将U映射到表T[0..m-1]的下标上，可以表示成 h：U→{0，1，2，...，m-1}，通常称h为“哈希函数(Hash Function)”，其作用是压缩待处理的下标范围，使待处理的|U|个值减少到m个值，从而降低空间开销（注：|U|表示U中关键字的个数，下同）。 3、将结点按其关键字的散列地址存储到哈希表（散列表）中的过程称为“散列(Hashing)”。方法称为“散列法”。 4、h(Ki)(KiU)是关键字为Ki的结点的“存储地址”，亦称散列值、散列地址、哈希地址。 5、用散列法存储的线性表称为“哈希表（Hash Table）”，又称散列表。图中T即为哈希表。在散列表里可以对结点进行快速检索（查找）。 6、对于关键字为key的结点，按照哈希函数h计算出地址h(key)，若发现此地址已被别的结点占用，也就是说有两个不同的关键码值key1和key2对应到同一个地址，即h(key1)=h(key2)，这个现象叫做“冲突（碰撞）”。碰撞的两个（或多个）关键码称为“同义词”（相对于函数h而言）。如图1中的关键字k2和k5，h(k2)=h(k5)，即发生了“冲突”，所以k2和k5称为“同义词”。假如先存了k2，则对于k5，我们可以存储在h(k2)+1中，当然h(k2)+1要为空，否则可以逐个往后找一个空位存放。这是另外一种简单的解决冲突的方法。 发生了碰撞就要想办法解决，必须想办法找到另外一个新地址，这当然要降低处理效率，因此我们希望尽量减少碰撞的发生。这就需要分析关键码集合的特性，找适当的哈希函数h使得计算出的地址尽可能“均匀分布”在地址空间中。同时，为了提高关键码到地址转换的速度，也希望哈希函数“尽量简单”。然而对于各种取值的关键码而言，一个好的哈希函数通常只能减少碰撞发生的次数，无法保证绝对不产生碰撞。因此散列除去要选择适当的哈希函数以外，还要研究发生碰撞时如何解决，即用什么方法存储同义词。 7、负载因子 我们把h(key)的值域所对应到的地址空间称为“基本区域”，发生碰撞时，同义词可以存放在基本区域还没有被占用的单元里，也可以放到基本区域以外另开辟的区域中（称为“溢出区”）。下面引入散列的一个重要参数“负载因子或装填因子(Load Factor)”，它定义为： а= 负载因子的大小对于碰撞的发生频率影响很大。直观上容易想象，а越大，散列表装得越满，则再要载入新的结点时碰上已有结点的可能性越大，冲突的机会也越大。特别当а＞1时碰撞是不可避免的。一般总是取а＜1，即分配给散列表的基本区域大于所有结点所需要的空间。当然分配的基本区域太大了也是浪费。例如，某校学生干部的登记表，每个学生干部是一个结点，用学号做关键码，每个学号用7位数字表示，如果分配给这个散列表的基本区域为107个存储单元，那么散列函数就可以是个恒等变换，学号为7801050的学生结点就存入相对地址为7801050的单元，这样一次碰撞也不会发生，但学校仅几百个学生干部，实际仅需要