散列（哈希）表算法学习

什么是散列表？

散列表(Hash table，也叫哈希表),是根据关键码值(Key, value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中的一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。

什么是哈希算法？

哈希算法（Hash）又称摘要算法（Digest），它的作用是：对任意一组输入数据进行计算，得到一个固定长度的输出摘要。

哈希算法最重要的特点就是：

l 相同的输入一定得到相同的输出；

l 不同的输入大概率得到不同的输出。

哈希算法的目的就是为了验证原始数据是否被篡改。

定义：将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是哈希算法，而通过原始数据映射之后得到的二进制值串就是哈希值。

哈希算法要求？

Ø 从哈希值不能反向推导出原始数据（所以哈希算法也叫单向哈希算法）；

Ø 对输入数据非常敏感，哪怕原始数据只修改了一个 Bit，最后得到的哈希值也大不相同；

Ø 散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小

Ø 哈希算法的执行效率要尽量高效，针对较长的文本，也能快速地计算出哈希值。

哈希算法的应用：安全加密、唯一标识、数据校验、散列函数、负载均衡、数据分片、分布式存储等。

常见的散列函数？

l 最常用于加密的哈希算法是 MD5（MD5 Message-Digest Algorithm，MD5 消息摘要算法）；

l  SHA（Secure Hash Algorithm，安全散列算法）。除了这两个之外，当然还有很多其他加密算法，比如 DES（Data Encryption Standard，数据加密标准）、AES（Advanced Encryption Standard，高级加密标准）。

事实上，再好的散列函数都无法避免散列冲突。

抽屉原理

抽屉原理：桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面至少放两个苹果。这一现象就是我们所说的“抽屉原理”。

鸽巢原理

如果有 10 个鸽巢，有 11 只鸽子，那肯定有 1 个鸽巢中的鸽子数量多于 1 个，换句话说就是，肯定有 2 只鸽子在 1 个鸽巢内。

其实不管是抽屉原理还是鸽巢原理，其实都是一个意思，就是坑就这么多，当人数到达坑的个数就必然出现多个人同时占一个坑的情况。

对于散列表而言，无论设置的存储区域（n）有多大，当需要存储的数据大于 n 时，那么必然会存在哈希值相同的情况。这就是所谓的散列冲突。

常用的散列冲突解决方法。

1 开放寻址法

开放寻址法是一种解决碰撞的方法，对于开放寻址冲突解决方法，开放寻址法的核心思想是，如果出现了散列冲突，我们就重新探测一个空闲位置，将其插入。比较经典的有线性探测方法（Linear Probing）、二次探测（Quadratic probing）和 双重散列（Double hashing）等方法。具体大家可以网上找到方法的详情进行学习。

2 链表法

链表法是一种更加常用的散列冲突解决办法，相比开放寻址法，它要简单很多。我们来看这个图，在散列表中，每个“桶（bucket）”或者“槽（slot）”会对应一条链表，所有散列值相同的元素我们都放到相同槽位对应的链表中。

7 个常用的哈希应用

1. 安全加密

①常用于加密的哈希算法：

MD5：MD5 Message-Digest Algorithm，MD5 消息摘要算法

SHA：Secure Hash Algorithm，安全散列算法

DES：Data Encryption Standard，数据加密标准

AES：Advanced Encryption Standard，高级加密标准②对用于加密的哈希算法，有两点格外重要，第一点是很难根据哈希值反向推导出原始数据，第二点是散列冲突的概率要小。

③在实际开发中要权衡破解难度和计算时间来决定究竟使用哪种加密算法。

2.唯一标识

通过哈希算法计算出数据的唯一标识，从而用于高效检索数据。

3.数据校验

利用哈希算法对输入数据敏感的特点，可以对数据取哈希值，从而高效校验数据是否被篡改过。

4.散列函数

散列函数中用到的哈希算法更加关注散列后的值能不能平均分布，以及散列函数的执行快慢。

5.负载均衡

我们知道，负载均衡算法有很多，比如轮询、随机、加权轮询等。那如何才能实现一个会话粘滞（session sticky）的负载均衡算法呢？也就是说，我们需要在同一个客户端上，在一次会话中的所有请求都路由到同一个服务器上。最直接的方法就是，维护一张映射关系表，这张表的内容是客户端 IP 地址或者会话 ID 与服务器编号的映射关系。客户端发出的每次请求，都要先在映射表中查找应该路由到的服务器编号，然后再请求编号对应的服务器。这种方法简单直观，但也有几个弊端：如果客户端很多，映射表可能会很大，比较浪费内存空间；客户端下线、上线，服务器扩容、缩容都会导致映射失效，这样维护映射表的成本就会很大.

6.数据分片

哈希算法还可以用于数据的分片。我这里有两个例子。1.如何统计“搜索关键词”出现的次数？假如我们有 1T 的日志文件，这里面记录了用户的搜索关键词，我们想要快速统计出每个关键词被搜索的次数，该怎么做呢？我们来分析一下。这个问题有两个难点，第一个是搜索日志很大，没办法放到一台机器的内存中。第二个难点是，如果只用一台机器来处理这么巨大的数据，处理时间会很长。针对这两个难点，我们可以先对数据进行分片，然后采用多台机器处理的方法，来提高处理速度。具体的思路是这样的：为了提高处理的速度，我们用 n 台机器并行处理。我们从搜索记录的日志文件中，依次读出每个搜索关键词，并且通过哈希函数计算哈希值，然后再跟 n 取模，最终得到的值，就是应该被分配到的机器编号。这样，哈希值相同的搜索关键词就被分配到了同一个机器上。也就是说，同一个搜索关键词会被分配到同一个机器上。每个机器会分别计算关键词出现的次数，最后合并起来就是最终的结果。

7. 分布式存储

现在互联网面对的都是海量的数据、海量的用户。我们为了提高数据的读取、写入能力，一般都采用分布式的方式来存储数据，比如分布式缓存。我们有海量的数据需要缓存，所以一个缓存机器肯定是不够的。于是，我们就需要将数据分布在多台机器上。该如何决定将哪个数据放到哪个机器上呢？我们可以借用前面数据分片的思想，即通过哈希算法对数据取哈希值，然后对机器个数取模，这个最终值就是应该存储的缓存机器编号。