网站数据库安装教程山东省建行企业网站

网站数据库安装教程,山东省建行企业网站,水安建设集团网站,青岛房产网首页可以把哈希表理解为一种高级的数组#xff0c;这种数组的下标可以是很大的整数#xff0c;浮点数#xff0c;字符串甚至结构体。 哈希函数 核心是均匀#xff0c;工程上常利用哈希函数把大数据量的样本#xff0c;均匀哈希到多台机器、多个文件#xff0c;从而省下内存…可以把哈希表理解为一种高级的数组这种数组的下标可以是很大的整数浮点数字符串甚至结构体。哈希函数核心是均匀工程上常利用哈希函数把大数据量的样本均匀哈希到多台机器、多个文件从而省下内存使用。性质输入的规模可能是无限的输出规模相对有限单值函数同样的输入对应同一个输出完全无随机机制不同的输入可能对应同一个输出可能发生哈希碰撞散列冲突大规模的输出会均匀分布在输出域上最后一条是哈希函数的核心性质用好的哈希函数和尽量大的输出域规避碰撞。好的哈希函数应当易于计算并且尽量使计算出来的索引均匀分布。除留余数法此方法为最常用的构造哈希函数方法。在 OI 中最常见的情况应该是键值为整数的情况当键值的范围比较小的时候可以直接把键值作为数组的下标。但当键值的范围比较大比如以1 0 9 10^9109范围内的整数作为键值的时候就需要用到哈希表。一般把键值模一个较大的质数作为索引也就是f ( x ) x ( m o d p ) f(x)x \pmod pf(x)x(modp)显然本方法的关键在于选择合适的 p。根据经验若哈希表表长为 m通常 p 为小于或等于表长最接近 m的质数或不包含小于 20 质因数的合数。字符串哈希处理 key 为字符串的情况。篇幅较大详情。直接定址法取关键字的某个线性函数值为地址f ( x ) a ⋅ k e y b f(x)a\cdot keybf(x)a⋅keyb优点是简单、均匀、不会产生冲突。但需要实现知道关键字的分布情况适合查找表较小且连续的情况。数字分析法抽取关键字的一部分来计算地址。比如手机号的后四位。适合关键字位数比较多的情况如果事先知道关键字的分布且关键字分布的若干位分布较均匀就可以考虑这个方法。平方取中法将关键字平方后取中间几位作为地址。适合不知道关键字分布而位数又大的情况。折叠法将关键字分割成位数相等的几部分然后将这几部分叠加求和再取后几位作为地址。比如9876543210 → 987 ∣ 654 ∣ 321 ∣ 0 → 987 654 321 0 1962 → 962 9876543210 \to 987|654|321|0 \to 98765432101962 \to 9629876543210→987∣654∣321∣0→98765432101962→962适合不知道关键字分布关键字位数较多的情况。随机数法用 random 随机函数值作为地址。f ( x ) r a n d o m ( x ) f(x) random(x)f(x)random(x)适合关键字长度不等的情况。总之应视不同情况采用不同的哈希函数考虑计算地址所需时间关键字长度关键字分布情况哈希表大小记录、查找的频率哈希冲突在实际情况中常常会出现两个不同的键值他们用哈希函数计算出来的索引是相同的。这时候就需要一些方法来处理冲突。在 OI 中最常用的方法是拉链法也称开散列法、链地址法。拉链法/开散列法/链地址法拉链法是在每个存放数据的地方存放一个链表如果有多个关键字索引到同一个地方只要把他们都放进那个索引位置的链表里。这种方法保证不会出现找不到地址的保障也带来了时间损耗。查询时需要遍历整个链表。假设哈希函数优秀哈希表大小为N NN地址的范围为1 … M 1 \ldots M1…M那么每次插入/查询的平均时间为O ( N M ) O(\frac{N}{M})O(MN​)。Java、C 中封装的哈希表常用此方法。实现publicclassHashTable{privatestaticfinalintSIZE1_000_000;privatestaticfinalintM999_997;privatestaticclassNode{intnext;intvalue;intkey;Node(intnext,intvalue,intkey){this.nextnext;this.valuevalue;this.keykey;}Node(){}}privatefinalNode[]datanewNode[SIZE1];privatefinalint[]headnewint[M];privateintsize0;privateintf(intkey){intrkey%M;returnr0?rM:r;}publicintget(intkey){for(intphead[f(key)];p!0;pdata[p].next){if(data[p].keykey)returndata[p].value;}return-1;}publicintmodify(intkey,intvalue){for(intphead[f(key)];p!0;pdata[p].next){if(data[p].keykey)return(data[p].valuevalue);}return0;}publicintadd(intkey,intvalue){if(get(key)!-1)return-1;intidxf(key);sizesize1;data[size]newNode(head[idx],value,key);head[idx]size;returnvalue;}}封装模板publicclassHashMap{staticclassData{longu;intv;intnex;Data(longu,intv,intnex){this.uu;this.vv;this.nexnex;}}privatefinalintSZ;privatefinalData[]e;privatefinalint[]h;privateintcnt;publicHashMap(intSZ){this.SZSZ;this.enewData[SZ1];this.hnewint[SZ];this.cnt0;}privateinthash(longu){intr(int)(u%SZ);returnr0?rSZ:r;}publicDataref(longu){inthuhash(u);for(intih[hu];i!0;ie[i].nex){if(e[i].uu)returne[i];}cntcnt1;e[cnt]newData(u,-1,h[hu]);h[hu]cnt;returne[cnt];}}开放定址法/闭散列法闭散列方法把所有记录直接存储在散列表中如果发生冲突则根据某种方式继续进行探查。比如线性探测法、二次探测法、随机探测法。线形探测法f i ( x ) ( f ( x ) d i ) ( m o d m ) ( d i 1 , 2 , 3 , ⋯ , m − 1 ) f_i(x)(f(x)d_i) \pmod m (d_i 1,2,3, \cdots, m-1)fi​(x)(f(x)di​)(modm)(di​1,2,3,⋯,m−1)为了不让关键字都聚集在某一区块可以使用二次探测法f i ( x ) ( f ( x ) d i ) ( m o d m ) ( d i 1 2 , − 1 2 , 2 2 , − 2 2 , ⋯ , q 2 , − q 2 , q ≤ m / 2 ) f_i(x)(f(x)d_i) \pmod m (d_i 1^2, -1^2, 2^2, -2^2, \cdots, q^2, -q^2, q≤m/2)fi​(x)(f(x)di​)(modm)(di​12,−12,22,−22,⋯,q2,−q2,q≤m/2)随机探测法f i ( x ) ( f ( x ) d i ) ( m o d m ) ( d 是一个随机数列 ) f_i(x)(f(x)d_i) \pmod m (d 是一个随机数列)fi​(x)(f(x)di​)(modm)(d是一个随机数列)Python、Go 中封装的哈希表常用此方法。其中 Go 还使用溢出桶但并不是下文要提到的「公共溢出区法」。再哈希函数法f i ( x ) R H i ( x ) ( i 1 , 2 , ⋯ , k ) f_i(x) RH_i(x)(i1,2,\cdots,k)fi​(x)RHi​(x)(i1,2,⋯,k)R H i RH_iRHi​为不同的哈希函数可以把上文说的什么除留余数法、直接定址法、随机数法全都用上。每当发生一次冲突就换一个哈希函数。这种方法能使得关键字不聚集但也增加了计算时间。公共溢出区法此方法把所有冲突的关键字统统存放在一个公共溢出区。查找时先在哈希表中查找若没找到再取溢出区顺序查找。在冲突数据较少时此方法查找性能还是很高的。#atom