第八章散列

xiaoxiao2021-02-28  36

散列的含义

散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。

对不同的关键字可能得到同一散列地址,即k1≠k2,而f(k1)=f(k2),这种现象称为碰撞(英语:Collision)。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述,根据散列函数f(k)和处理碰撞的方法将一组关键字映射到一个有限的连续的地址集(区间)上,并以关键字在地址集中的“像”作为记录在表中的存储位置,这种表便称为散列表,这一映射过程称为散列造表或散列,所得的存储位置称散列地址。

散列函数

(1)直接定址法

   取关键字的某个线性函数为散列地址,Hash(Key)= Key 或 Hash(Key)= A*Key + B,A、B为常数。

(2)除数留余法

  设散列表中允许的地址数为m,取一个不大于m,但接近或者等于m的质数p作为除数,按照哈希函数:Hash(key) = key mod p  p<=m,将关键码转换成哈希地址。对p的选择很重要,一般取素数或m,若p选的不好,容易产生同义词。

(3)平方取中法

  平方后取中间的,每位包含信息比较多。假设关键字是1234,那么它的平方就是1522756,再抽取中间的3位就是227作为散列地址;再比如关键字是4321,那么它的平方就是18671041,抽取中间的3位就可以是671或者710用作散列地址。

(4)折叠法

有时关键码所含的位数很多,采用平方取中法计算太复杂,则可将关键码分割成位数相同的几部分(最后一部分的位数可以不同),然后取这几部分的叠加和(舍去进位)作为散列地址,这方法称为折叠法。

比如:关键字是9876543210,散列表表长为三位,我们将它分成四组987|654|321|0|,然后将它们叠加求和987+654+321+0=1962,再求后3位得到散列地址为962。有时可能这还不能够保证分布均匀,不妨从一段向另一端来回折叠后对齐相加。比如将987和321反转,再与654和0相加,编程789+654+123+0=1566,此时的散列地址为566。

散列冲突

解决冲突的技术可以分为两类:开散列方法(open hashing,也称单链方法,separate chaining)和闭散列方法(closed hashing,也称开地址方法,open addressing)。开散列方法解决冲突是将冲突记录在表外,而闭散列方法是将冲突记录在表内的另一个空槽。

(1)开散列方法:运用单链表存储方式,不产生堆积现象,但因为附加了指针域而增加了空间开销。

       

代码如下:

function HashTable() { this.table=new Array(137); this.simpleHash=simpleHash; this.betterHash=betterHash; this.showDistro=showDistro; this.put=put; this.get=get; this.buildChains=buildChains;//开链法 } function put(key,data){ // let pos=this.simpleHash(key); let pos=this.betterHash(key); let index=0; while(this.table[pos][index]!=undefined){ index++; } this.table[pos][index]=data; } function get(key){ // let pos=this.simpleHash(key); let pos=this.betterHash(key); let index=0; if(this.table[pos][index]==key){ return this.table[pos][index]; }else{ while(this.table[pos][index]&&this.table[pos][index]!=key){ index++; } return this.table[pos][index]; } } //容易发生碰撞 function simpleHash(data){ let total=0; for(let i=0;i<data.length;i++){ total +=data.charCodeAt(i); } return total%this.table.length; } //使用霍纳算法的散列函数 function betterHash(string){ const H=37; let total=0; for(let i=0;i<string.length;i++){ total +=H*total+string.charCodeAt(i); } total=total%this.table.length; if (total<0) { total +=this.table,length-1; } return parseInt(total); } function showDistro(){ let n=0; for(let i=0;i<this.table.length;i++){ if (this.table[i][0] !=undefined) { console.log(i+":"+this.table[i]); } } } //开链法 function buildChains(){ for(let i=0;i<this.table.length;i++){ this.table[i]=new Array(); } } //测试 let someNames=["David","Jennifer","Donnie","Raymond", "Cynthia", "Mike", "Clayton", "Danny", "Jonathan","Tom","Jack","Divad","Caylton"]; let hTable=new HashTable(); hTable.buildChains(); for(let i=0;i<someNames.length;i++){     hTable.put(someNames[i],someNames[i]); } hTable.showDistro();

(2)闭散列方法:运用顺序表存储,存储效率较高,但容易产生堆积,查找不易实现,需要用到二次再查找。闭散列方法有桶式散列、线性探查、二次探查、双散列方法。

//线性探测法 function HashTable() { this.table=new Array(137); this.values=[]; this.betterHash=betterHash; this.showDistro=showDistro; this.put=put; this.get=get; } function put(key,data){ let pos=this.betterHash(key); while(this.table[pos]!=undefined){ pos++; } this.table[pos]=key; this.values[pos]=data; } function get(key){ let pos=this.betterHash(key); if(this.table[pos]==key){ return this.values[pos]; }else{ while(this.table[pos]&&this.table[pos]!=key){ pos++; } return this.values[pos]; } } //使用霍纳算法的散列函数 function betterHash(string){ const H=37; let total=0; for(let i=0;i<string.length;i++){ total +=H*total+string.charCodeAt(i); } total=total%this.table.length; if (total<0) { total +=this.table,length-1; } return parseInt(total); } function showDistro(){ let n=0; for(let i=0;i<this.table.length;i++){ if (this.table[i] !=undefined) { console.log(i+":"+this.values[i]); } } } //测试 let someNames=["David","Jennifer","Donnie","Raymond", "Cynthia", "Mike", "Clayton", "Danny", "Jonathan","Tom","Jack","Divad","Caylton"]; let hTable=new HashTable(); for(let i=0;i<someNames.length;i++){ hTable.put(someNames[i],someNames[i]); } hTable.showDistro(); console.log(hTable.get('Town'));//undefined console.log(hTable);
转载请注明原文地址: https://www.6miu.com/read-2400167.html

最新回复(0)