Hash 表
1. 介绍¶
散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。
2. 基本概念¶
若关键字为k，则其值存放在f(k)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数，按这个思想建立的表为散列表。
对不同的关键字可能得到同一散列地址，即k1≠k2，而f(k1)=f(k2)，这种现象称为冲突（英语：Collision）。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述，根据散列函数f(k)和处理冲突的方法将一组关键字映射到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便称为散列表，这一映射过程称为散列造表或散列，所得的存储位置称散列地址。
若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数（Uniform Hash function），这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。
3. 常用方法¶
散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快地定位。
实际工作中需视不同的情况采用不同的哈希函数，通常考虑的因素有：
- 计算哈希函数所需时间
- 关键字的长度
- 哈希表的大小
- 关键字的分布情况
- 记录的查找频率
3.1 直接寻址法¶
取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a·key + b，其中a和b为常数（这种散列函数叫做自身函数）。若其中H(key）中已经有值了，就往下一个找，直到H(key）中没有值了，就放进去。
3.2 数字分析法¶
分析一组数据，比如一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体相同，这样的话，出现冲突的几率就会很大，但是我们发现年月日的后几位表示月份和具体日期的数字差别很大，如果用后面的数字来构成散列地址，则冲突的几率会明显降低。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。
3.3 平方取中法¶
当无法确定关键字中哪几位分布较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。这是因为：平方后中间几位和关键字中每一位都相关，故不同关键字会以较高的概率产生不同的哈希地址。
例：我们把英文字母在字母表中的位置序号作为该英文字母的内部编码。例如K的内部编码为11，E的内部编码为05，Y的内部编码为25，A的内部编码为01,B的内部编码为02。由此组成关键字“KEYA”的内部代码为11052501，同理我们可以得到关键字“KYAB”、“AKEY”、“BKEY”的内部编码。之后对关键字进行平方运算后，取出第7到第9位作为该关键字哈希地址，
| 关键字 | 内部编码 | 内部编码的平方值 | H(k)关键字的哈希地址 |
|---|---|---|---|
| KEYA | 11052501 | 122157778355001 | 778 |
| KYAB | 11250102 | 126564795010404 | 795 |
| AKEY | 01110525 | 001233265775625 | 265 |
| BKEY | 02110525 | 004454315775625 | 315 |
3.4 折叠法¶
将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列地址。数位叠加可以有移位叠加和间界叠加两种方法。移位叠加是将分割后的每一部分的最低位对齐，然后相加；间界叠加是从一端向另一端沿分割界来回折叠，然后对齐相加。
3.5 随机数法¶
选择一随机函数，取关键字的随机值作为散列地址，即H(key)=random(key)其中random为随机函数,通常用于关键字长度不等的场合。
3.6 除留余数法¶
取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p,p<=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生同义词。
4. 实现哈希表¶
4.1 哈希表原理¶
如果说每一个数据它都对应着一个固定的位置，那我们查找特定一个数据时，就可以直接查看这个数据对应的位置是否存在数据。一个形象的例子就是学生在教室中的位置，开学的时候，老师会给学生每一个人分配一个位置，而且不允许学生随便乱坐位置，以后老师要查看今天李刚同学有没有上课，直接看李刚同学的位置是不是有人就可以判断，没必要点了全班同学的名才可以知道李刚同学来了没有。
4.2 实现简单的哈希表¶
根据上面的原理，首先，我们要分配一片空间用来存储我们数据，比如是一个空的数组
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| None | None | None | None | None | None | None | None | None | None | None |
然后，有数据存进来的时候，按照特定规则得出这个数据在数组中的位置，将数据存进这个位置，我们就以存进一个整型数据为例，特定规则就是取余
| 数据 | 内部编码 |
|---|---|
| 54 | 54%11=10 |
| 26 | 26%11=4 |
| 93 | 93%11=5 |
| 17 | 17%11=6 |
| 77 | 77%11=0 |
| 31 | 31%11=9 |
根据计算出来的值，将这些数据放入对应的位置，我们的数组变为
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 77 | None | None | None | 26 | 93 | 17 | None | None | 31 | 54 |
我们已经把数据插入到了哈希表中，现在，我们要查找一个数据，只要按照取余规则计算出这个数据在数组中对应的位置，然后查看数组的这个位置，就可以取出这个数据了，比如我们要从哈希表中取出52，根据取余规则，52的计算出来的位置是8，数组中8这个位置是空的，52不在哈希表中，找不到52的数据；从哈希表中取出77，77计算出来的位置是0，数组中0这个位置有值，而且值就是77，从哈希表中取出77的值。
至此，我们知道实现了一个很简单的哈希表的原理，其实还存在很多问题，这个我们接下来讨论，这儿先把我们前面的一些概念用专业的术语替换一下，前面我们所说的特定规则，我们称之为哈希函数，用特定股则计算出来的值称之为哈希值。
4.3 存在问题¶
- 有可能两个数据通过哈希函数计算出来的哈希值有可能相等，比如77，88计算出来的位置值都是0
- 如果哈希表满了，该怎么扩容
第一个问题就是如何解决这种冲突
有开放定址法，链定址法，我们说一下开放定址法，就是将这个冲突的数据再重新计算一个空的位置，将其存进去，比如我们要存放88，哈希值是0，数组这个位置已经有值了，那我们再获取一个哈希值，比如在原哈希值的基础上加1，得到1，1的位置是空，我将88放进去。有人会问，1这个位置被占了，那下一个数据是1这个位置怎么办，这时候，我们还是同样的做法，给这个数据再计算一个哈希值。
插入88后的数组变为
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 77 | 88 | None | None | 26 | 93 | 17 | None | None | 31 | 54 |
冲突解决了，但我们读取数据的时候，好像又出现问题了，88的哈希值是0，发现数组0位置不是空的，那我们确定88在哈希表中？肯定不行，0这个位置存储的是77，不是88。我们的解决方法是判断0这个位置的值是不是88，不是的话，再计算88的哈希值是1，判断是1这个位置是否为空，为空，则88不在哈希表中；不为空，判断值是否为88，若是88，确定在哈希表中；如果值不是88，我们则继续计算哈希值是2，依次下去，直到找到88或者值为空的位置。
第二个问题，哈希表扩容
一个简单的解决办法是，当插入数据时，发现所有的位置都满了，我们就再分配一个大于原先空间的一片空间，把原来空间中的值重新哈希到新的空间中。
4.4 哈希表的python实现¶
class Dict:
def __init__(self, size=10):
self.size = size
self.key = [None] * self.size
self.data = [None] * self.size
def __setitem__(self, key, value):
assert isinstance(key, int)
index = self.hash(key)
if not self.key[index]:
self.key[index] = key
self.data[index] = value
elif self.key[index] == key:
self.data[index] = value
else:
start = index
while self.key[index] and self.key[index] != key:
index = self.re_hash(index)
if index == start:
raise Exception('dict is full')
if self.key[index]:
self.data[index] = value
else:
self.key[index] = key
self.data[index] = value
def __getitem__(self, item):
assert isinstance(item, int)
index = self.hash(item)
if not self.key[index]:
raise KeyError(item)
else:
if self.key[index] == item:
return self.data[index]
else:
start = index
while self.key[index] and self.key[index] != item:
index = self.re_hash(index)
if start == index:
raise KeyError(item)
if self.key[index] == item:
return self.data[index]
else:
raise KeyError(item)
def __contains__(self, item):
assert isinstance(item, int)
index = self.hash(item)
if not self.key[index]:
return False
else:
if self.key[index] == item:
return True
else:
start = index
while self.key[index] and self.key[index] != item:
index = self.re_hash(index)
if start == index:
break
if self.key[index] == item:
return True
else:
return False
def hash(self, key):
index = key % self.size
return int(index)
def re_hash(self, index):
return index+1
a = Dict()
a[1]='3'
a[2]='4'
print(a[5])