数据结构与程序设计(王丽苹)23hash函数.ppt
5/27/2023,数据结构与程序设计,1,数据结构与程序设计(23)Chapter09 9.6 Hashing函数,王丽苹,5/27/2023,数据结构与程序设计,2,哈希函数,顺序查找和二分查找都是建立在“比较”的基础上，所要查找的关键字与存贮地址之间无确定的关系，故查找的效率决定于查找中比较的次数。如果能找到一种函数，对应于每个关键字，都能唯一确定一个存贮地址，那么在查找时，只要根据给定的关键字用该函数进行计算后即可直接取得该关键字所在记录的存贮地址，从而获得待查记录。这个思想就是哈希查找的思想，相应地称这种函数为哈希函数。Hash函数输入为：关键字Hash函数输出为：存储位置 满足上述存储关系的表为Hash表。关键字在整个Hash表中必须要唯一。,5/27/2023,数据结构与程序设计,3,哈希函数,建立哈希函数带有极强的技术性和经验性，下面简单介绍几种常用方法。1直接哈希函数直接哈希函数是直接取关键字或关键字的某个线性函数作为哈希函数，其特点是关键字与哈希地址之间是一对一的关系，因此不会发生冲突，但它的空间浪费严重，因为在大多数情况下，由哈希函数计算出来的地址不是连续的。例如，对参加某一活动的同学进行登记，关键字为学生的学号，哈希函数为H(key)=key。,5/27/2023,数据结构与程序设计,4,哈希函数,2除数取余法这种方法是先找出一个合适的正整数m，取关键字对m的余数作为哈希函数的值，即H（key）=key mod m。为了尽可能避免冲突，一般m取小于存贮区长度的尽可能大的素数。,5/27/2023,数据结构与程序设计,5,哈希函数,3随机法当关键字的长度不等时，通常采用随机函数法，先选择一个随机函数作为哈希函数，关键字对应的随机函数值即为哈希地址，即H（key）=ran(key)。,5/27/2023,数据结构与程序设计,6,哈希函数,在哈希表的建表过程中，若对于某个哈希函数H（k），若有两个或两个以上的关键字映射的哈希地址相同，即H（key1）=H（key2）（key1key2），则发生冲突。在前一节提到过，选择哈希函数时应选择均匀的，冲突较少的。但在大多数情况下，冲突是不可避免的，因此选择哈希函数和解决冲突是哈希查找中两个主要研究内容。常用的处理冲突的方法有开放地址法和链地址法。,5/27/2023,数据结构与程序设计,7,开放地址法,开放地址法解决哈希冲突的思想是，将整个哈希地址区看成一个环形表，当冲突发生时，根据某种解决冲突的方法，为发生冲突的关键字找出一个“空”的地址单元作为该关键字的哈希地址。若插入元素，则碰到空的地址单元就存放要插入的同义词。若检索元素，则需要碰到空的地址单元后，才能说明表中没有待查的元素(检索失败)。,开放地址法,用开地址法解决冲突的方法讨论：（1）用线性探测法：即将基本存储区看作一个循环表。若在地址为d=h(key)的单元发生碰撞，则依次探查下述地址单元d+1,d+2,m-1,0,1,d-1(m为基本存储区的长度)直到找到一个空单元或查找到关键码为key的元素为止。如果从单元d开始探查，查找一遍后，又回到地址d，则表示基本存储区已经溢出。可能会造成“堆积”。,5/27/2023,数据结构与程序设计,8,例子：已知关键码集合K=18，73，10，5，68，99，27，41，51，32，25，设散列表基本区域用数组element表示，大小为m(m=13)，散列函数为h(key)=key%13，用线性探查法解决碰撞。按散列函数d=key%13计算每个元素的散列地址如下：h(18)=5,h(73)=8,h(10)=10,h(5)=5,h(68)=3,h(99)=8 h(27)=1,h(41)=2,h(51)=12,h(32)=6,h(25)=12最后的散列表为：,开放地址法,用开地址法解决冲突的方法讨论：（2）平方探测法我们可以改变增量的形式，如发生冲突时，检测H(key)1，H(key函数)4,H(key函数)9 这种方法就称为平方探测法。（3）增量函数法选择两个散列函数h1和h2他们均以关健字为自变量，h1产生0到m-1之间的数作为地址，如果有冲突，则计算h2的值，h2产生一个1到m-1之间的并和m互素的数作为地址的增量。例如两个散列函数可以为h1(key)=key%m和h2(key)=key%(m-2)+1。如果d=h1(key)发生碰撞，则再计算h2(key)，得到探查序列为(d+h2(key)%m,(d+2h2(key)%m,(d+3h2(key)%m,5/27/2023,数据结构与程序设计,10,5/27/2023,数据结构与程序设计,11,开放地址法实现讨论,enum Error_codenot_present,overflow,duplicate_error,success;const int hash_size=97;class Hash_table public:void clear();Error_code insert(const Record,5/27/2023,数据结构与程序设计,12,开放地址法,class Key int key;public:Key(int x=0);int the_key()const;bool operator=(const Key,5/27/2023,数据结构与程序设计,13,开放地址法,class Recordpublic:operator Key();/implicit conversion from Record to Key.Record(int x=0,int y=0);int the_key()const;int the_other()const;private:int key;int other;bool operator!=(const Record,5/27/2023,数据结构与程序设计,14,开放地址法,void Hash_table:clear()for(int i=0;ihash_size;i+)Record tmp;tablei=tmp;,5/27/2023,数据结构与程序设计,15,开放地址法,/以下是Hash函数的设计int hash(const Record,开放地址法,Error_code insert(const Record 创建Hash表的方法：(1)计算当前待插入元素new_entry在Hash表中的位置。(2)判断该关键字是否唯一。不唯一则报错。(2)判断当前位置是否空闲：如果空闲直接将元素放入当前位置如果不空闲，选用冲突检测方法，计算下一个可放置的位置。(3)重复（2），直到找到位置，或者判断出当前表格已满。约定：0，表示当前位置空闲。-1，表示当前位置的元素被删除。,5/27/2023,数据结构与程序设计,17,开放地址法,Error_code Hash_table:insert(const Record,开放地址法,Error_code retrieve(const Key 访问Hash表：(1)通过Hash函数计算得到target的位置prob。(2)判断prob位置的值是否与target相等：如果相等，则找到该关键字。将其内容存储于found中。如果不相等，则根据冲突解决的方法，计算下一个地址prob。(3)重复步骤2，直到找到，或者确定target不存在于hash表中：a,碰到Prob位置为空闲，b，计算了所有可能的位置。,5/27/2023,数据结构与程序设计,19,Error_code Hash_table:retrieve(const Key,开放地址法,Error_code Hash_table:remove(const Key&target,Record&found)删除Hash表的一个元素。(1)通过Hash函数计算得到target的位置prob。(2)判断prob位置的值是否与target相等：如果相等，则找到该关键字。将其内容存储于found中,将该位置置为-1。如果不相等，则根据冲突解决的方法，计算下一个地址prob。(3)重复步骤2，直到找到，则删除成功。或者确定target不存在于hash表中：a,碰到Prob位置为空闲，b，计算了所有可能的位置。此时删除失败。,5/27/2023,数据结构与程序设计,21,开放地址法,Error_code Hash_table:remove(const Key,5/27/2023,数据结构与程序设计,22,开放地址法,void main()Hash_table myhash;myhash.insert(Record(3,20);myhash.insert(Record(5,30);myhash.insert(Record(9,50);Record target;myhash.retrieve(Key(5),target);coutKey:target.the_key()The other:target.the_other()endl;target=Record(0,0);myhash.retrieve(Key(3),target);coutKey:target.the_key()The other:target.the_other()endl;,5/27/2023,数据结构与程序设计,23,Result,Key:5 The other:30Key:3 The other:20,5/27/2023,数据结构与程序设计,24,开放地址法,target=Record(0,0);myhash.remove(Key(3),target);coutKey:target.the_key()The other:target.the_other()endl;target=Record(0,0);myhash.retrieve(Key(3),target);coutKey:target.the_key()The other:target.the_other()endl;cin.get();,5/27/2023,数据结构与程序设计,25,Result,Key:3 The other:20Key:0 The other:0,5/27/2023,数据结构与程序设计,26,链地址法,拉链法解决哈希冲突的思想是将所有具有相同哈希地址的关键字连接成一个单链表。设基本区域长度为m，使用拉链法需要建立m条链表，所有散列地址相同的元素存放在同一条链表中。设给定元素的关键码为key，首先根据散列函数h计算出h(key)，即确定是在第h(key)条链表中，然后在该链表中进行插入、删除及检索操作。已知关键码集合K=18，73，10，5，68，99，27，41，51，32，25，m取13，设散列函数为h(key)=key%13，用拉链法得到的散列表如下图所示。,5/27/2023,数据结构与程序设计,27,5/27/2023,数据结构与程序设计,28,链地址法,#include Record.h#include LinkList.cpp const int hash_size=97;class Hash_table public:void clear();Error_code insert(const Record,5/27/2023,数据结构与程序设计,29,链地址法,void Hash_table:clear()for(int i=0;ihash_size;i+)tablei.clear();,5/27/2023,数据结构与程序设计,30,链地址法,/仍然选用与开地址法相同的Hash函数int hash(const Record,链地址法,Error_code Hash_table:insert(const Record&new_entry)创建Hash表：(1)通过Hash函数计算得到new_entry的位置prob。(2)判断new_entry是否在下表为prob的List中存在。如果存在则插入失败。如果不存在，插入new_entry,5/27/2023,数据结构与程序设计,32,链地址法,Error_code Hash_table:insert(const Record,链地址法,Error_code Hash_table:retrieve(const Key&target,Record&found)const访问关键字target：(1)通过Hash函数计算得到new_entry的位置prob。(2)判断target是否在下标为prob的List中存在。即：逐一访问tableprob中的每一个元素，判断是否与target相等。,5/27/2023,数据结构与程序设计,34,链地址法,Error_code Hash_table:retrieve(const Key,5/27/2023,数据结构与程序设计,35,链地址法,Error_code Hash_table:remove(const Key/不存在的话，删除失败。,分析,P411书本9.7节,课后作业,作业：完成P409 E6（a）请用线性探测解决冲突，写出hash表存储的内容。上机实现链地址法哈希散列表。,5/27/2023,数据结构与程序设计,37,
