哈希表概述 -常见哈希函数和解决冲突的方法概述

可以把哈希表理解为一种高级的数组，这种数组的下标可以是很大的整数，浮点数，字符串甚至结构体。

哈希函数

核心是均匀，工程上常利用哈希函数把大数据量的样本，均匀哈希到多台机器、多个文件，从而省下内存使用。
性质

• 输入的规模可能是无限的，输出规模相对有限
• 单值函数，同样的输入对应同一个输出，完全无随机机制
• 不同的输入可能对应同一个输出，可能发生哈希碰撞（散列冲突）
• 大规模的输出，会均匀分布在输出域上

最后一条是哈希函数的核心性质，用好的哈希函数和尽量大的输出域规避碰撞。
好的哈希函数应当易于计算，并且尽量使计算出来的索引均匀分布。

除留余数法

此方法为最常用的构造哈希函数方法。
在 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 key+bf(x)=a⋅key+b
优点是简单、均匀、不会产生冲突。但需要实现知道关键字的分布情况，适合查找表较小且连续的情况。

数字分析法

抽取关键字的一部分来计算地址。比如手机号的后四位。
适合关键字位数比较多的情况，如果事先知道关键字的分布且关键字分布的若干位分布较均匀，就可以考虑这个方法。

平方取中法

将关键字平方后取中间几位作为地址。
适合不知道关键字分布，而位数又大的情况。

折叠法

将关键字分割成位数相等的几部分，然后将这几部分叠加求和，再取后几位作为地址。
比如：
9876543210 → 987 ∣ 654 ∣ 321 ∣ 0 → 987 + 654 + 321 + 0 = 1962 → 962 9876543210 \to 987|654|321|0 \to 987+654+321+0=1962 \to 9629876543210→987∣654∣321∣0→987+654+321+0=1962→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{privatestaticfinalintSIZE=1_000_000;privatestaticfinalintM=999_997;privatestaticclassNode{intnext;intvalue;intkey;Node(intnext,intvalue,intkey){this.next=next;this.value=value;this.key=key;}Node(){}}privatefinalNode[]data=newNode[SIZE+1];privatefinalint[]head=newint[M];privateintsize=0;privateintf(intkey){intr=key%M;returnr<0?r+M:r;}publicintget(intkey){for(intp=head[f(key)];p!=0;p=data[p].next){if(data[p].key==key)returndata[p].value;}return-1;}publicintmodify(intkey,intvalue){for(intp=head[f(key)];p!=0;p=data[p].next){if(data[p].key==key)return(data[p].value=value);}return0;}publicintadd(intkey,intvalue){if(get(key)!=-1)return-1;intidx=f(key);size=size+1;data[size]=newNode(head[idx],value,key);head[idx]=size;returnvalue;}}

封装模板：

publicclassHashMap{staticclassData{longu;intv;intnex;Data(longu,intv,intnex){this.u=u;this.v=v;this.nex=nex;}}privatefinalintSZ;privatefinalData[]e;privatefinalint[]h;privateintcnt;publicHashMap(intSZ){this.SZ=SZ;this.e=newData[SZ<<1];this.h=newint[SZ];this.cnt=0;}privateinthash(longu){intr=(int)(u%SZ);returnr<0?r+SZ:r;}publicDataref(longu){inthu=hash(u);for(inti=h[hu];i!=0;i=e[i].nex){if(e[i].u==u)returne[i];}cnt=cnt+1;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)(i=1,2,\cdots,k)fi​(x)=RHi​(x)(i=1,2,⋯,k)
R H i RH_iRHi​为不同的哈希函数，可以把上文说的什么除留余数法、直接定址法、随机数法全都用上。每当发生一次冲突就换一个哈希函数。
这种方法能使得关键字不聚集，但也增加了计算时间。

公共溢出区法

此方法把所有冲突的关键字统统存放在一个公共溢出区。
查找时先在哈希表中查找，若没找到，再取溢出区顺序查找。
在冲突数据较少时，此方法查找性能还是很高的。
#atom