哈希表（散列表）捋一捋

散列表（Hash table）通过将关键码映射到表中的某个位置来存储元素，然后根据关键码用同样的方式进行直接访问

散列表

理想的搜索方法是可以不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结构，使元素的存储位置与它的关键码之间建立一个确定的对应函数关系Hash()，那么每个元素关键码与结构中的一个唯一的存储位置相对应：

• Address = Hash(Key)

在插入时，根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放。在搜索时，对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功。该方式即散列方法(Hash Method)，在散列方法中使用的转换函数叫散列函数(Hash function)，构造出来的结构叫散列表(Hash Table)。

散列函数

• 散列函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0~m-1之间。
• 散列函数计算出来的地址应能均匀分布在整个地址空间中。
• 散列函数应该简单，计算快。

直接定址法

取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B。
优点：简单、均匀
缺点：需要事先知道关键字的分布情况
适合查找比较小且连续的情况。

除留余数法

设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数。
哈希函数为：Hash(key) = key % p p<=m,将关键码转换成哈希地址。
为什么要取质数（素数）呢？减小哈希冲突发生的概率

如果N=13，                          比如N=12， 
g=4, f(g,x)=g*x mod N，则          g=4, f(g,x)=g*x mod N 
4*1 mod N = 4                        4*1 mod N = 4 
4*2 mod N = 8                        4*2 mod N = 8 
4*3 mod N = 0                        4*3 mod N = 12 
4*4 mod N = 4                        4*4 mod N = 3 
4*5 mod N = 8                        4*5 mod N = 7 
4*6 mod N = 0                        4*6 mod N = 11 
4*7 mod N = 4                        4*7 mod N = 2 
4*8 mod N = 8                        4*8 mod N = 6 
4*9 mod N = 0                        4*9 mod N = 10 
4*10 mod N = 4                       4*10 mod N = 1 
4*11 mod N = 8                       4*11 mod N = 5 
4*12 mod N = 9 

数字分析法

设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。

数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀的情况。

平方取中法

假设关键字是1234，那么它的平方就是1522756，再抽取中间的3位就是227作为散列地址；再比如关键字是4321，那么它的平方就是18671041，抽取中间的3位就可以是671或者710用作散列地址。
平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况。

折叠法

折叠法是将关键字从左到右分割成位数相等的几部分(注意：最后一部分位数不够时可以短些)，然后将这几部分叠加起来。有两种叠加方法：

• 位移法：把各部分的最后一位对齐相加
• 分界法：各部分不折断，沿各部分的分界来回折叠，然后对齐相加，将相加的结果当做散列地址。

假定关键码为：key = 23938587841，若存储空间限定3位，则划线结果为每段三位：
239 | 385 | 878 | 41
把超出地址位数的最高位删去，仅保留3位。

随机数法

选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数函数，通常应用于关键字长度不等时采用此法。

散列冲突

对于两个数据元素的关键字Ki和Kj(i != j)，有Ki ！= Kj(i != j)，但HashFun(Ki)== HashFun(Kj)，将该种现象称为哈希冲突或哈希碰撞。把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”，由同义词引起的冲突称为同义词冲突。

处理冲突的闭散列方法

闭散列也叫开地址法。
设散列表的编址为0到m-1，当添加关键码key时通过散列函数hash(key)计算key的存放位置，但在存放时发现这个桶已经被另一个keyx占据了，即发生哈希冲突。如果表未被装满，表示在给定的范围内必然还有空位置，则可以把key存放到表中“下一个”空位中。
简而言之：一旦发生冲突，就去寻找下一个空的散列表地址，只要散列表足够大，空的散列地址总能找到。

线性探查

设给出一组元素，它们的关键码为：37,25,14,36,49,68,57,11，散列表为HT[12]，表的大小m =12，假设采用Hash(x) = x % p; // (p = 11) 11是最接近m的质数，就有：
Hash(37) = 4 Hash(25) = 3 Hash(14) = 3 Hash(36) = 3
Hash(49) = 5 Hash(68) = 2 Hash(57) = 2 Hash(11) = 0

散列情况统计：

二次探查

使用二次探查法，在表中寻找“下一个”空位置的公式为：
Hi = (H0 + i^2)%m, Hi = (H0 - i^2)%m, i = 1,2,3…，(m-1)/2
H0是通过散列函数Hash(x)对元素的关键码x进行计算得到的位置，m是表的大小。
假设数组的关键码为37,25,14,36,49,68,57,11，假设取m=19，这样可设定为HT[19]，采用散列函数
Hash(x) = x % 19
Hash(37)=18 Hash(25)=6 Hash(14)=14 Hash(36)=17
Hash(49)=11 Hash(68)=11 Hash(57)=0 Hash(11)=11

散列情况统计：

双散列法

使用双散列方法，需要两个散列函数。第一个散列函数Hash()按关键码key计算其所在的位置H0 =Hash(key)。一旦发生冲突，利用第二个散列函数ReHash()计算该key到达“下一个”桶的位移，它的取值与key的值有关，要求它的取值应该是小于地址空间大小TableSize，且与TableSize互质的正整
数。
若设表的长度为m = TableSize，则在表中寻找“下一个”桶的公式为：
j = H0 = Hash(key)，p = ReHash(key)； j = (j+p)%m;p是小于m且与m互质的整数。

处理冲突的开散列方法

开散列法又叫链地址法(开链法)。
开散列法首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点组成一个向量，因此，向量的元素个数与可能的桶数一致。
设元素的关键码为37,25,14,36,49,68,57,11,散列表为HT[12]，表的大小为12，散列函数为Hash(x)= x % 11
Hash(37)=4 Hash(25)=3 Hash(14)=3 Hash(36)=3
Hash(49)=5 Hash(68)=2 Hash(57)=2 Hash(11)=0