算法小讲堂之哈希表|散列表|考研笔记

一、 基本概念

哈希表（ H a s h T a b l e Hash Table HashTable ）也称为散列表，是根据关键码值( K e y 、 V a l u e Key、Value Key、Value )而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做 散列函数 ，存放记录的数组叫做 散列表 。

其实可以简单理解为一张表里面存储了一些我们需要使用的元素，这些元素都有关键字，我们将关键字输入散列函数处理，然后给我们映射到一个地址，我们访问这个地址就能得到我们想要的元素

显然散列函数在帮我们映射关键字地址的时候难免会将不同的关键字映射到同一个地址，这种情况就是 冲突，或称哈希冲突 ，一般来说这样的冲突是无可避免的，所以在发生冲突前我们尽量设计好 散列函数 ，当然在发生冲突后我们也需要指定一系列的操作用于处理冲突，下面会一一道来。

通过上面的介绍，我们会发现哈希表的出现就是结合了数组和链表的优点的，数组的特点是寻址容易，插入和删除难，而链表的特点是寻址困难，但是插入和删除容易，而哈希表很显然我们会发现插入很容易，删除也很容易（理想情况下）

二、 哈希函数|散列函数

在构造散列函数需要注意几点：

• 散列函数的定义域一定要包含全部存储的关键字，值域的范围依赖于散列表的大小
• 散列函数计算出来的地址应尽量等概率均匀分布在整个地址空间，从而减少冲突
• 散列函数的设计应当尽量简单，能够在较短时间内计算出任意关键字对应的地址

下面则是常用的散列函数：

2.1 直接定址法

散列函数为一个线性函数，我们通过将关键字传入计算出相应的散列地址： H ( k e y ) = k e y 或者是 H ( k e y ) = a × k e y + b H(key)=key \\ \text{或者是} \\ H(key) = a\times key + b H(key)=key或者是H(key)=a×key+b 其中 a a a 和 b b b 为常数，因为是线性函数，即 一对一的模式，所以不会产生哈希冲突，他适合关键字分布基本连续的情况，否则会造成存储空间的浪费

2.2 保留余数法

假设散列表长为 m m m ,取一个不大于 m m m 的最大质数 p p p 哈希函数为： H ( k e y ) = k e y % p H(key) = key \% p H(key)=key%p

2.3 数字分析法

设关键字是 r r r 进制数（如十进制数），而 r r r 个数码在各位上出现的频率不一定相同 ，可能在某些位上分布均匀一些，每种数码出现的机会均等；而在某些位上分布不均匀，只有某几种数码经常出现，此时应选取数码分布较为均匀的若干位作为散列地址。 这种方法适合于己知的关键字集合，若更换了关键字， 则需要重新构造新的散列函数

2.4 平方取中法

将关键字的平方值的中间几位作为散列值，具体取多少位根据实际情况而定（感觉很鸡肋……）

2.5 折叠法

将关键字分割成位数相同的几部分（最后一部分可以不同），然后再将这几部分累加起来作为哈希地址

例如一个电话 18784878052 18784878052 18784878052 我们将其分割成每一部分三位数字，从前往后分割，就得到了这几个数： { 187 , 848 , 780 , 52 } \{187,848,780,52 \} {187,848,780,52} 然后我们再将其累加起来得到：

187 + 848 + 780 + 52 = 1867 187+848+780+52 = 1867 187+848+780+52=1867

这样就是一个折叠发的映射处理了~

2.6 随机数法

这……就很顾名思义了，通过伪随机数作为关键字的映射地址（这个也很鸡肋，知道就行了）

三、冲突处理

在某些哈希函数的处理下，冲突是无法避免的，那么解决哈希冲突大概有以下的方法：

3.1 开放定址法

当哈希冲突发生的时候，通过往后探测，找到一个空位，显然往后探测的方法不同，也就划分了不同的方式，简单理解为，你在学校准备上厕所，你一眼相中了第二个坑位，当你过去的时候你发现里面有人了（这就是冲突），然后你得去找下一个没有人的坑位（解决冲突），那么你是直接到下一个坑位查看有没有人呢，还是说直接跳三个坑位再看（解决冲突的方法）

一般的开放地址法的递推公式如下： H i = ( H ( k e y ) + d i ) % m H_i = (H(key) + d_i) \% m Hi​=(H(key)+di​)%m 其中， H ( k e y ) H(key) H(key) 为散列函数， i = 0 , 1 , 2 … … , k ( k < = m − 1 ) i=0,1,2……,k(k