数据结构系列：哈希表？这涉及的可是“加密/区块链”等技术的核心

之前的几篇文章分别介绍了线性表和树结构相关的特点和应用，本文将分享另一种主要应用在加密领域的数据结构，哈希表(散列表)。当然，不仅仅限于加密领域，因为哈希表的效率极其优秀。

 01 什么是哈希表

官方概念

哈希表（Hash table），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

非官方理解

哈希表既然作为一种抽象的数据结构，那必然和栈结构或者树结构一样，对存放的数据呈现出一定的规律特点。那么哈希表这种结构的特点是什么？总结一句话：哈希表可以由数据项的值确定数据存放的位置，每一个存储位置，称之为槽，用来保存数据项（value），每个槽应该有唯一的标记(key)

哈希表存储的是一种映射关系：可以想象假设存在两张表，一张存储key，用来做唯一标记；一张存储value，存放key对应的所有数据项。如果你要想找某个数据项，必须通过key值，key会通过某种你目前所不了解的方法被转化为唯一的哈希值(位置信息)，根据这个唯一值，才能定位到你所需要查找的数据。

就像python中字典的基础数据结构通过key就可以找到value，但是key值必须唯一

02 哈希表相关的概念

上面简单介绍了到底什么是哈希表，接下来介绍一下学习哈希表需要知道的相关概念

散列技术

数据的存储位置和他的关键字之间建立一个明确的映射关系，使得每个关键字key对应一个存储位置f(key)，查找时，根据这个确定的对应关系找到给定值key对应的映射f（key）

散列值

把任意长度数据的输入，通过散列函数，变换成固定长度字符串的输出，该输出就是散列值

散列函数

通过算法实现从数据项到存储槽名称转换的函数称之为散列函数，接收数据项作为参数，返回数据集中唯一的标记（key），这是实现哈希表的核心

完美散列函数

1) 概念

给定一组数据项，如果有一个散列函数能够把每个数据项映射到不同的槽中，(没有相同的key),那么这个函数就称之为完美散列函数

2) 难点

如果数据集合是不变的，其实很好写出这样的函数，但是遇到变化的数据集合，则很难实现通用的完美散列函数。

3) 近似完美散列函数

完美散列函数基本不存在，所以要想办法实现尽可能的完美，一般包含以下几个条件：1.对于不同的数据集合，冲突越少越好；2.函数要尽可能的性能高；3.不会使用大量的内存

4) 近似完美函数举例

MD5：将任何长度的数据变换为固定长度为128位（16字节）的摘要

SHA：SHA-0/SHA-1输出160位，SHA-256/SHA-224/SHA-512/SHA-384分别输出后面数字长度的位数

03 一般对散列函数的要求

1) 压缩性：任意长度的数据，得到的散列值的长度是固定的

2) 易计算性：生成散列值不难

3) 抗修改性：对原始数据做出更改的话，散列值会发生剧烈变化

4) 抗冲突性：基本不会生成相同的散列值

04 散列涉及到的一些特点

1) 假设存放数据的槽有11个，而数据项求余数后添加到槽中只填满了5个，那么此时就可说负载因子为5/11

2) 所以要查看一个数据是否在一个数据集合中，如果使用哈希的方法，我们只需要通过标记定位到槽的位置，看下槽中是否由数据项即可

3)散列是不可逆的，就是可以通过算法实现数据项到散列值的映射，但是不可能通过散列值求出原数据

4)散列函数的输入和输出并不是唯一对应的关系，如果两个散列值相同，那么两个输入有可能是相同的，也有可能是不同的

05 哈希碰撞

最简单的散列函数就是依次对数据集中的数据（找一个任意有效数作为除数）求余数，每个数据项的余数就是标记数据项的（key），但是这种方式很容易有不同的数据项插入到一个槽中了，这样就造成了冲突，称之为哈希碰撞

简单点说，就是：如果两个数据项被散列映射到同一个槽，需要一个系统的方法在散列表中保存第二个数据项，这个解决的过程就称之为解决冲突

目前比较成熟的解决方案

1)线性探测：为冲突的数据项再找一个开放的空槽来保存数据，最简单的就是从冲突的槽开始往后扫描，直到碰到一个空槽，如果到散列表尾部还没找到，则从首部接着扫描，这种寻找空槽的技术称之为"开放定址"，向后逐个槽寻找的方法则是开放定址技术中的线性探测。线性探测方法的问题在于如果同一个槽冲突的数据项越多的话 ，这些数据就会再槽附近聚集起来，呈现数据项聚集的趋势。

2)跳跃式探测：为避免出现聚集的情况，对线性探测的方法提出了改进，就是将数据位置+1的操作改为数据位置+n（n为大于1的有效数字），构成跳跃式探测，针对这个n的取值，不能被散列表大小整除，不然永远有空槽找不到，一个技巧是把散列表的大小设置为质数

3)二次探测：不再是固定的n值，而是逐步增加n的大小

4)数据项链：将每个槽的格式更改为可以存储数据集合的形式，这样每个槽就可以容纳多个数据项，只要有散列冲突，就把新的数据项添加到数据项集合中

06 散列函数的应用

1) 数据一致性做校验，比如从网站上下载的数据是否完整，比如两个文件的内容是是否完全一致，因为不论多大的数据，生成的散列值是一样的，只有128位（如果是MD5的话）

2) 密码的加密，对散列值进行对比

3) 防文件篡改

4) 区块链技术，（区块链是一种分布式数据库），通过网络连接的节点，每个节点保存着整个数据库的所有数据，最大的特点就是去中心化，每个节点都拥有全部信息。区块链由一个个区块组成，区块分为头和体，头信息包含元数据和前一个区块的信息，由于散列函数的特征，可以保证数据的真实可靠。

07 哈希函数的一个实现

最基础的针对非数字的散列函数

哈希函数（参考）

我是一名奋战在编程界的pythoner，工作中既要和数据打交道，也要和erp系统，web网站保持友好的沟通……时不时的会分享一些提高效率的编程小技巧，在实际应用中遇到的问题以及解决方案，或者源码的阅读等等，欢迎大家一起来讨论！如果觉得写得还不错，欢迎关注点赞，谢谢。