C语言数据结构——哈希表

我们必须先了解一种新的存储方式—散列技术：散列技术是指在记录的存储位置和它的关键字（key）之间建立一个确定的对应关系f，使每一个关键字都对应一个存储位置。即：存储位置=f（关键字）。这样，在查找的过程中，只需要通过这个对应关系f 找到给定值key的映射f（key），得到对应的存储位置，再将对应存储位置中存储的关键字和需要查找的关键字进行比较即可。
我们把这种对应关系f 称为散列函数或哈希函数。
按照这个思想，采用散列技术将记录存储在一块连续的存储空间中，这块连续的存储空间称为哈希表。所得的存储地址称为哈希地址或散列地址。
- 数据的哈希地址=f（关键字的值）
通过关键字求哈希地址的过程称之为：哈希

三、哈希表的本质

哈希表的本质：数组。
通过哈希函数得到的哈希地址（哈希值）其实就是数组的下标或者索引。

四、哈希函数的构造方法

1、哈希函数的构造的原则

计算简单：哈希函数不应该有很大的计算量，否则会降低查找效率。
分布均匀：哈希函数值即散列地址，要尽量均匀分布在地址空间，这样才能保证存储空间的有效利用并减少冲突。

2、直接定址法

哈希函数是关键字值的线性函数，即：h(key) = a * key + b （a，b为常数）

假设需要统计中国人口的年龄分布，以10为最小单元。今年是2018年，那么10岁以内的分布在2008-2018，20岁以内的分布在1998-2008……假设2018代表2018-2008直接的数据，那么关键字应该是2018，2008，1998……
- 那么可以构造哈希函数H（key）=（2018-key）/10
- 那么hash表建立如下：

3、除留余数法

设有一组关键字，试用除留余数法求设计哈希函数。关键字组：（19,14,23,01,68,20,84,27,55,11,10,79,12,39,21）。
可以设置为H(key)=key%13；为什么取13？我们可以假设它取9，得出的余数分别为1 5 5 1 5 2 3 0 1 2 1 7 3 3 3。可以看出1 3 5的余数非常多，当它映射到存储地址时，会更容易的造成冲突。所以我们在选择取余数时，一般取质数，让它的冲突尽可能的少。

4、数字分析法

如果关键字由多位字符或者数字组成，就可以考虑抽取其中的 2 位或者多位作为该关键字对应的哈希地址，在取法上尽量选择变化较多的位，避免冲突发生。

例如下表中列举的是一部分关键字，每个关键字都是有 8 位十进制数组成：

通过分析关键字的构成，很明显可以看到关键字的第 1 位和第 2 位都是固定不变的，而第 3 位不是数字 3 就是 4，最后一位只可能取 2、7 和 5，只有中间的 4 位其取值近似随机，所以为了避免冲突，可以从 4 位中任意选取 2 位作为其哈希地址。

5、折叠法

是将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。此方法适合关键字位数较多的情况。

例如，在图书馆中图书都是以一个 10 位的十进制数字为关键字进行编号的，若对其查找表建立哈希表时，就可以使用折叠法。

若某书的编号为：0-442-20586-4，分割方式如图 1 中所示，在对其进行折叠时有两种方式：一种是移位折叠，另一种是间界折叠：

移位折叠是将分割后的每一小部分，按照其最低位进行对齐，然后相加，如图 1（a）；
间界折叠是从一端向另一端沿分割线来回折叠，如图 1（b）。

五、哈希冲突

在哈希函数的设计过程中，不管哈希函数设计的如何巧妙，总会有特殊的key导致哈希冲突。

解决哈希冲突主要有如下方法：

开放寻址法/开放定址法
再哈希法
拉链法/链地址法
建立公共溢出区

1 开放寻址法

开放寻址法的概念

开放寻址法指的是：当哈希值p = H(key)出现冲突时，以p为基础，产生另一个哈希值，如果p1仍然冲突，再以p为基础，产生另一个哈希值p2，…，直到找到一个不冲突的还行值，表示为：

其中H0表示第一次计算的哈希值，Hi表示第i次计算的哈希值。m为数组的长度。di为增量序列，根据增量序列的取值不同，又分为三种：

线性探测法
- di = 1，2，3，4，5，6，…，m-1，这种方法是在发生冲突时，顺序查看表中的下一个单元，直到找出一个空单元或查遍全表。
二次探测法
- di = 1 ^2^ ，-1 ^2^ ，2 ^2^ ，-2 ^2^ ，…(i = 1，2，3，4，…，(m-1)/2)，这种方法在发生冲突时，在表的左右进行跳跃式探测，比较灵活。
伪随机探测法

线性探测例题

题目：
- 已知一个线性表（38，25，74，63，52，48），假定采用散列函数h（key) = key%7计算散列地址，并散列存储在散列表A[7]中，采用线性探测方法解决冲突。
解题思路：
- 线性表长度为6，采用直接定址法，与质数7取模
- 进行38这个数据处理：38%7 = 3，直接把38放在下标为3的位置， {0, 0, 0, 38, 0, 0, 0}
- 处理25, 25%7=4，一样把25放在下标为4的位置，{0, 0, 0, 38, 25, 0, 0}
- 接下来是74， 74%7=4，可是这时候4上已经放了25了。得进行线性探测：
  - H(74) = 4;根据线性探测：D(i)=(H(i)+d)MOD M(M为散列表长度7)， d=1时候 D(1) = (4+1)%7=5散列表中5位置为空，因此能够把74放在位置5处
  - {0, 0, 0, 38, 25, 74, 0}
- 接下来是63， 63%7=0直接把63放在0处， {63， 0, 0, 38, 25, 74, 0}
- 接下来是52， 52%7=3可是位置3已经有38了冲突，得进行线性探测：
  - 线性探测：D（1）=（3+1）%7=4， 4上有25了，冲突
  - D(2)=(3+2)%7=5， 5上有74了，冲突
  - D(3) = (3+3)%7=6，能够把52放在6位置上
  - {63, 0, 0, 38, 25, 74, 52}
- 接下来是48， 48%7=6， 6位置有52了，冲突，得进行线性探测：
  - D(1) =（6+1）%7=0，0上有63了，冲突
  - D(2)=(6+2)%7=1， 1上还没有数据，能够放48
  - {63, 48, 0, 38, 25, 74, 52}

2、再哈希法

再哈希法是同时构造多个不同的哈希函数，第一个冲突了用第二个，第二个也冲突了用第三个。

例如：实用哈希函数 H = x + b时产生了冲突，就使用H = 2x + b, 再冲突了就使用H = 3x + b 。。。，但是这种方法不是很实用，而且每次冲突都需要重新调用哈希函数，效率不高。

3、拉链法（链地址法）

将所有产生冲突的关键字所对应的数据全部存储在同一个线性链表中。
例如有一组关键字为 {19,14,23,01,68,20,84,27,55,11,10,79}，其哈希函数为：H(key)=key MOD 13，使用链地址法所构建的哈希表如下图所示：

六、解决冲突的方法的总结

开放地址法：计算简单快捷，处理起来方便，但线性探测法容易形成“堆聚”。另外，该方法的删除操作显得十分复杂，我们不能直接删除关键字所在的记录，否则在查找删除位置后面的元素时，可能会出现找不到的情况，因为删除位置上已经成了空地址，查找到这里时会终止查找。所以，就需要重建哈希表，特别浪费性能。
拉链法：该方法将所有哈希地址相同的结点构成一个单链表，单链表的头结点存在哈希数组里，链地址法常出现在经常插入和删除的情况下，此时，哈希表的插入/删除/查找都是O(1)的时间复杂度。该法不会出现“堆聚”现象，哈希地址不同的关键字不会发生冲突；不需要重建哈希表。另外，如果开放地址法中，哈希表里存满关键字了就需要扩充哈希表然后重建哈希表，而链地址法不需要。

哈希函数和哈希表的应用

1、唯一标识

举个例子，如果在海量的图库中，搜索一张图是否存在，我们不能单纯的用图片的元信息（比如图片名称）来比对，因为有可能存在名称相同但是图片内存不同，或者名称不同图片内存相同的情况。那我们该如何搜索呢？

我们知道，任何文件在计算中都可以表示成二进制串。所以，比较笨的方法是，拿要查找的图片的二进制码串与图库中所有图片的二进制码串一一比对。如果相同，则说明图片在图库中存在。但是，每个图片小则几十 KB、大则几 MB，转换成二进制是一个非常长的串，比对起来非常耗时。有没有比较快的方法呢？
我们可以给每个图片取一个唯一标识，或者说信息摘要。比如，我们可以从图片的二进制串开头取10个字节，从中间取10个字节，从最后取10个字节，然后将这300个字节放在一块，通过哈希算法（比如 MD5），得到一个哈希字符串，用它作为图片的唯一标识。通过这个唯一标识来判定图片是否在图库中，这样就可以减少很多工作量。
如果还想继续提高效率，我们可以把每个图片的唯一标识，和相应的图片文件在图库中的路径信息，都存储在散列表中。当要查看某个图片是不是在图库中的时候，我们先通过哈希算法对这个图片取唯一标识，然后在散列表中查找是否存在这个唯一标识
如果不存在，那就说明这个图片不再图库中；如果存在，我们在通过散列表中存储的文件路径，获取到这个已经存在的图片，跟现在要插入的图片做全量的比对，看是否完全一样。如果一样，就说明已经存在；如果不一样，说明两张图片尽管唯一标识相同，但是并不是相同的图片。

2、数据校验

我们知道，BT下载的原理是基于P2P协议的。我们从多个机器上并行下载一个2GB的电影，这个电影文件可能会被分隔成很多文件块（比如可以分成 100 块，每块大约 20MB）。等所有的文件块都下载完成之后，再组装成一个完整的电影文件就行了。

我们知道，网络传输是不安全的，下载的文件块有可能是被宿主机恶意修改过的，又或者下载过程中出现了差错，所以下载的文件块可能不是完整的。如果我们没有能力检测这种恶意修改或者文件下载出错，就会导致最终合并后的电影无法观看，甚至导致电影中电脑中毒。现在的问题是，如何来校验文件块的安全、正确、完整呢？

思路：

我们通过哈希算法，对100个文件块分布取哈希值，并且保存在种子文件中
我们知道，哈希算法有一个特点，对数据很敏感。只要文件块的内容有一丁点儿的改变，最后计算出的哈希值就会完全不同。
所以，当文件块下载完成之后，我们可以通过相同的哈希算法，对下载号的文件块逐一求哈希值，然后跟种子文件中保存的哈希值比对。如果不同，说明这个文件块不完整或者被篡改了，需要再重新从其他宿主机器上下载这个文件块。

3、如何统计“搜索关键词”出现的次数

问题：假如我们有1T的日志文件，这里面记录了用户的搜索关键词，我们想要快速统计出每个关键词被搜索的次数，应该怎么做呢？

这个问题主要有两个难点：

第一个是搜索日志很大，没办法放到一台机器的内存中
第二个是如果只用一台机器来处理这么大的数据，处理时间会很长。

那如何解决这两个难点呢？

我们可以先对数据进行分片，然后采用多台机器处理的方法，来提高处理速度

具体思路：

为了提高处理的速度，我们用 n 台机器并行处理。
我们从搜索记录的日志文件中，依次读出每个搜索关键词，并且通过哈希函数计算哈希值，然后再跟n 取模，最终得到的值，就是应该被分配到的机器编号。
这样，哈希值相同的搜索关键词就被分配到了同一个机器上。也就是说，同一个搜索关键词会被分配到同一个机器上。每个机器会分别计算关键词出现的次数，最后合并起来就是最终的结果

4、何快速判断图片是否在图库中？

如何快速判断图片是否在图库中？可以给即给每个图片取唯一标识（或者信息摘要），然后构建散列表。

假设现在我们的图库中有 1 亿张图片，很显然，在单台机器上构建散列表是行不通的。因为单台机器的内存有限，而 1 亿张图片构建散列表显然远远超过了单台机器的内存上限。

我们同样可以对数据进行分片，然后采用多机处理。我们准备 n 台机器，让每台机器只维护某一部分图片对应的散列表。我们每次从图库中读取一个图片，计算唯一标识，然后与机器个数 n 求余取模，得到的值就对应要分配的机器编号，然后将这个图片的唯一标识和图片路径发往对应的机器构建散列表。
当我们要判断一个图片是否在图库中的时候，我们通过同样的哈希算法，计算这个图片的唯一标识，然后与机器个数 n 求余取模。假设得到的值是 k，那就去编号 k 的机器构建的散列表中查找。

现在，我们来估算一下，给这 1 亿张图片构建散列表大约需要多少台机器。

散列表中每个数据单元包含两个信息，哈希值和图片文件的路径。假设我们通过 MD5 来计算哈希值，那长度就是 128 比特，也就是 16 字节。文件路径长度的上限是 256 字节，我们可以假设平均长度是 128 字节。如果我们用链表法来解决冲突，那还需要存储指针，指针只占用 8 字节。所以，散列表中每个数据单元就占用 152 字节（这里只是估算，并不准确）。
假设一台机器的内存大小为 2GB，散列表的装载因子为 0.75，那一台机器可以给大约1000 万（2GB*0.75/152）张图片构建散列表。所以，如果要对 1 亿张图片构建索引，需要大约十几台机器。

实际上，针对这种海量数据的处理问题，我们都可以采用多机分布式处理。借助这种分片的思路，可以突破单机内存、CPU 等资源的限制。