散列

基础定义

1、 散列：由数据项的值来确定数据存放的位置。散列表中的存储位置被成为槽。

2、散列函数：实现从数据项到存储槽的转换的函数称为散列函数。

3、 槽号：散列函数返回的数据项的存储位置。

几种常用的散列函数：

求余散列：

1. 方法：
   将数据项除以散列表的大小，得到的余数作 为槽号。
   实际上“求余数”方法会以不同形式出现在所有 散列函数里 因为散列函数返回的槽号必须在散列表大小范围 之内，所以一般会对散列表大小求余。
2. 数据的查找：
   只需要使用同一个散列函数，对查找项进行计算，测试下返回的槽号所对应的槽中是否有 数据项即可
3. 不足：
   可能会出现”冲突“现象。即：两个不同的数据项通过求余数后得到相同的槽号。

完美散列函数：

1. 方法：
给定一组数据项，如果一个散列函数能把 每个数据项映射到不同的槽中。对于固定的一组数据，总是能想方设法设计出完美散列函数。

2. 不足：
但是如果这组数据经常变动的话，很难有一个完美的散列函数（即会出现些许的冲突，但！冲突其实也不致命的，我们可以妥善的处理他们！）

3. 设计完美散列函数的方法：
①设计出一个足够大的散列表（即：扩大散列表的容量）使得所有可能出现的数据项都能够占据不同的槽。（不实用）
②退而求其次，好的散列函数需要具备特性 ：
冲突最少（近似完美）、
计算难度低（额外开销小）、
充分分散数据项（节约空间）

散列的应用之一

区域链
区域链介绍：区域链是一种分布式数据库，通过网络连接的节点 每个节点都保存着整个数据库所有数据 任何地点存入的数据都会完成同步。
其本质特征：去中心化，即不存在任何控制中心，协调中心节点，所有节点都是平等的 ，无法被控制。

区块链由一个个区块（block）组成，区 块分为头（head）和体（body） 
区块头记录了一些元数据和链接到前一个区块的信息。
生成时间、前一个区块(head+body)的散列值

区域链具有不可修改性：
由于散列值具有抗修改性，任何对某个区 块数据的改动必然引起散列值的变化，为了不导致这个区块脱离链条，就需要修改所有 后续的区块。
由于有“工作量证明”的机制，这种大规模修改 不可能实现的，除非掌握了全网51%以的计算力。

散列函数设计

1.折叠法：
将数据项按照位数分为若干段，再将几段数字相加， 最后对散列表大小求余，得到散列值。
有时候折叠法还会包括一个隔数反转的步骤

2.平方取中（计算量稍大）：
首先将数据项做平方运算，然后取平方数的中间两位，再对散列表的大小求余。

3.非数项：
也可以对非数字的数据项进行散列， 把字符串中的每个字符看作ASCII码即可，再将这些整数累加，对散列表大小求余。

注意：
这样的散列函数对所有的变位词都 返回相同的散列值 为了防止这一点，可以将字符串所在的位置作为 权重因子，乘以ord值。

4.数字分析法：
对于给定的关键码集合，分析所有关键码中各位数字出现的频率，从中选出分布情况较好的若干数字作为散列函数的值。

散列函数设计基本法则

1.
散列函数不能太复杂，否则将成为存储过程和查找过程的计算负担。

2.
散列值应尽可能地均匀分布

冲突的解决方案：

1.解决冲突：
一个系统化的方法在散列表中保存发生冲突数据中的第二个数据项。

2.解决方法
开放定址：即 再找一个开放的空槽来保存 最简单的就是从冲突的槽开始往后扫描，直到碰 到一个空槽 如果到散列表尾部还未找到，则从首部接着扫描 。
向后逐个槽寻找的方法则是开放定址技术 中的“线性探测。

3.缺点：
容易有聚集趋势。

4.改进：
将逐个探测改为跳跃式探测（再散列）。

参考资料：

北京大学 陈斌老师的数据结构与算法（python）网课课件