数据结构与程序设计(王丽苹)23hash函数

2/26/202012/26/2020数据结构与程序设计1数据结构与程序设计(23)Chapter099.6Hashing函数王丽苹[e-mail]22/26/2020数据结构与程序设计2哈希函数顺序查找和二分查找都是建立在“比较”的基础上，所要查找的关键字与存贮地址之间无确定的关系，故查找的效率决定于查找中比较的次数。如果能找到一种函数，对应于每个关键字，都能唯一确定一个存贮地址，那么在查找时，只要根据给定的关键字用该函数进行计算后即可直接取得该关键字所在记录的存贮地址，从而获得待查记录。这个思想就是哈希查找的思想，相应地称这种函数为哈希函数。Hash函数输入为：关键字Hash函数输出为：存储位置满足上述存储关系的表为Hash表。关键字在整个Hash表中必须要唯一。32/26/2020数据结构与程序设计3哈希函数建立哈希函数带有极强的技术性和经验性，下面简单介绍几种常用方法。1．直接哈希函数直接哈希函数是直接取关键字或关键字的某个线性函数作为哈希函数，其特点是关键字与哈希地址之间是一对一的关系，因此不会发生冲突，但它的空间浪费严重，因为在大多数情况下，由哈希函数计算出来的地址不是连续的。例如，对参加某一活动的同学进行登记，关键字为学生的学号，哈希函数为H(key)=key。42/26/2020数据结构与程序设计4哈希函数2．除数取余法这种方法是先找出一个合适的正整数m，取关键字对m的余数作为哈希函数的值，即H（key）=keymodm。为了尽可能避免冲突，一般m取小于存贮区长度的尽可能大的素数。52/26/2020数据结构与程序设计5哈希函数3．随机法当关键字的长度不等时，通常采用随机函数法，先选择一个随机函数作为哈希函数，关键字对应的随机函数值即为哈希地址，即H（key）=ran(key)。62/26/2020数据结构与程序设计6哈希函数在哈希表的建表过程中，若对于某个哈希函数H（k），若有两个或两个以上的关键字映射的哈希地址相同，即H（key1）=H（key2）（key1≠key2），则发生冲突。在前一节提到过，选择哈希函数时应选择均匀的，冲突较少的。但在大多数情况下，冲突是不可避免的，因此选择哈希函数和解决冲突是哈希查找中两个主要研究内容。常用的处理冲突的方法有开放地址法和链地址法。72/26/2020数据结构与程序设计79.6.3开放地址法开放地址法解决哈希冲突的思想是，将整个哈希地址区看成一个环形表，当冲突发生时，根据某种解决冲突的方法，为发生冲突的关键字找出一个“空”的地址单元作为该关键字的哈希地址。若插入元素，则碰到空的地址单元就存放要插入的同义词。若检索元素，则需要碰到空的地址单元后，才能说明表中没有待查的元素(检索失败)。89.6.3开放地址法用开地址法解决冲突的方法讨论：（1）用线性探测法：即将基本存储区看作一个循环表。若在地址为d=h(key)的单元发生碰撞，则依次探查下述地址单元∶d+1,d+2,…,m-1,0,1,…,d-1(m为基本存储区的长度)直到找到一个空单元或查找到关键码为key的元素为止。如果从单元d开始探查，查找一遍后，又回到地址d，则表示基本存储区已经溢出。可能会造成“堆积”。2/26/2020数据结构与程序设计89例子：已知关键码集合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)=8h(27)=1,h(41)=2,h(51)=12,h(32)=6,h(25)=12最后的散列表为：109.6.3开放地址法用开地址法解决冲突的方法讨论：（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,…2/26/2020数据结构与程序设计10112/26/2020数据结构与程序设计11开放地址法实现讨论enumError_code{not_present,overflow,duplicate_error,success};constinthash_size=97;classHash_table{public:voidclear();Error_codeinsert(constRecord&new_entry);Error_coderetrieve(constKey&target,Record&found)const;Error_coderemove(constKey&target,Record&found);private:Recordtable[hash_size];};inthash(constRecord&new_entry);inthash(constKey&new_entry);122/26/2020数据结构与程序设计12开放地址法classKey{intkey;public:Key(intx=0);intthe_key()const;};booloperator==(constKey&x,constKey&y);132/26/2020数据结构与程序设计13开放地址法classRecord{public:operatorKey();//implicitconversionfromRecordtoKey.Record(intx=0,inty=0);intthe_key()const;intthe_other()const;private:intkey;intother;};booloperator!=(constRecord&x,constRecord&y);booloperator==(constRecord&x,constRecord&y);142/26/2020数据结构与程序设计14开放地址法voidHash_table::clear(){for(inti=0;ihash_size;i++){Recordtmp;table[i]=tmp;}}152/26/2020数据结构与程序设计15开放地址法//以下是Hash函数的设计inthash(constRecord&new_entry){returnnew_entry.the_key()%hash_size;}inthash(constKey&new_entry){returnnew_entry.the_key()%hash_size;}16开放地址法Error_codeinsert(constRecord&new_entry);创建Hash表的方法：(1)计算当前待插入元素new_entry在Hash表中的位置。(2)判断该关键字是否唯一。不唯一则报错。(2)判断当前位置是否空闲：如果空闲直接将元素放入当前位置如果不空闲，选用冲突检测方法，计算下一个可放置的位置。(3)重复（2），直到找到位置，或者判断出当前表格已满。约定：0，表示当前位置空闲。-1，表示当前位置的元素被删除。172/26/2020数据结构与程序设计17开放地址法Error_codeHash_table::insert(constRecord&new_entry){Error_coderesult=success;intprobe_count,//Countertobesurethattableisnotfull.increment,//Incrementusedforquadraticprobing.probe;//Positioncurrentlyprobedinthehashtable.probe=hash(new_entry);probe_count=0;increment=1;if(retrieve((Record)new_entry,(Record)new_entry)==success)return；duplicate_error;while(table[probe]!=0//Isthelocationempty?&&table[probe]!=-1//emptybecausedelete&&probe_count(hash_size+1)/2){//Hasoverflowoccurred?probe_count++;probe=(probe+increment)%hash_size;increment+=2;//Prepareincrementfornextiteration.每次递增2。}if(table[probe]==0)table[probe]=new_entry;if(table[probe]==-1)table[probe]=new_entry;//Insertnewentry.elseresult=overflow;//Thetableisfull.returnresult;}18开放地址法Error_coderetrieve(constKey&target,Record&found)const;访问Hash表：(1)通过Hash函数计算得到target的位置prob。(2)判断prob位置的值是否与target相等：如果相等，则找到该关键字。将其内容存储于found中。如果不相等，则根据冲突解决的方法，计算下一个地址prob。(3)重复步骤2，直到找到，或者确定target不存在于hash表中：a,碰到Prob位置为空闲，b，计算了所有可能的位置。192/26/2020数据结构与程序设计19Error_codeHash_table::retrieve(constKey&target,Record&found)const{intprobe_count,//Countertobesurethattableisnotfull.increment,//Incrementusedforquadraticprobing.probe;//Positioncurrentlyprobedinthehashtable.probe=hash(target);probe_count=0;increment=1;while(table[probe]!=0//Isthelocationempty?&&table[probe].the_key()!=target.the_key()//notfound&&probe_count(hash_size+1)/2){//Hasoverflowoccurred?probe_count++;probe=(probe+increment)%hash_size;increment+=2;//Prepareincrementfornextiteration.}if(table[probe].the_key()==target.the_key()){found=table[probe];returnsuccess;}elsereturnnot_present;}20开放地址法Error_codeHash_table::remove(constKey&target,Record&found)删除Hash表的一个元素