共计 1607 个字符，预计需要花费 5 分钟才能阅读完成。
一、什么是 hash
- Hash，个别翻译做“散列”，也有间接音译为“哈希”的，就是把任意长度的输出（又叫做预映射，pre-image），通过散列算法，变换成固定长度的输入，该输入就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输出的空间，不同的输出可能会散列成雷同的输入，而不可能从散列值来惟一的确定输出值。简略的说就是一种将任意长度的消息压缩到某一固定长度的音讯摘要的函数。
- 哈希表是依据设定的哈希函数 H（key）和解决抵触办法将一组关键字映射到一个无限的地址区间上，并以关键字在地址区间中的象作为记录在表中的存储地位，这种表称为哈希表或散列，所得存储地位称为哈希地址或散列地址。作为线性数据结构与表格和队列等相比，哈希表无疑是查找速度比拟快的一种。
- 简略解释：哈希（Hash）算法，即散列函数。它是一种单向明码体制，即它是一个从明文到密文的不可逆的映射，只有加密过程，没有解密过程。同时，哈希函数能够将任意长度的输出通过变动当前失去固定长度的输入。哈希函数的这种单向特色和输入数据长度固定的特色使得它能够生成音讯或者数据。
二、罕用 hash 算法的介绍：
- MD4
MD4（RFC 1320）是 MIT 的 Ronald L. Rivest 在 1990 年设计的，MD 是 Message Digest（音讯摘要）的缩写。它实用在 32 位字长的处理器上用高速软件实现——它是基于 32 位操作数的位操作来实现的。
- MD5
MD5（RFC 1321）是 Rivest 于 1991 年对 MD4 的改良版本。它对输出仍以 512 位分组，其输入是 4 个 32 位字的级联，与 MD4 雷同。MD5 比 MD4 来得简单，并且速度较之要慢一点，但更平安，在抗剖析和抗差分方面体现更好。
- SHA- 1 及其他
SHA1 是由 NIST NSA 设计为同 DSA 一起应用的，它对长度小于 264 的输出，产生长度为 160bit 的散列值，因而抗穷举（brute-force）性更好。SHA-1 设计时基于和 MD4 雷同原理，并且模拟了该算法。
三、哈希碰撞（hash 抵触）及解决
在计算 hash 地址的过程中会呈现对于不同的关键字呈现雷同的哈希地址的状况，即 key1 ≠ key2，然而 f(key1) = f(key2)，这种状况就是 Hash 抵触。具备雷同关键字的 key1 和 key2 称之为同义词。
通过优化哈希函数能够缩小这种抵触的状况（如：平衡哈希函数），然而在通用条件下，思考到于表格的长度无限及要害值（数据）的有限，这种抵触是不可避免的，所以就须要解决抵触。
抵触解决
抵触解决分为以下四种形式：
- 凋谢地址
- 再哈希
- 链地址
- 建设公共溢出区
其中凋谢地址又分为：
- 线性探测再散列
- 二次探测再散列
- 伪随机探测再散列
1. 凋谢地址
凋谢地址法解决抵触的根本准则就是呈现抵触后依照肯定算法查找一个空地位寄存。公式：
Hi 为计算出的地址，H(key)为哈希函数，di 为增量。其中 di 的三种获取形式既是下面提到的凋谢地址法的三种分类（线性探测再散列、二次探测再散列、伪随机探测再散列）。
- 线性探测再散列，即顺次向后查找
- 二次探测再散列，即顺次向前后查找，增量为 1、2、3 的二次方。
- 伪随机探测再散列
伪随机，顾名思义就是随机产生一个增量位移。
2. 再哈希法
再哈希法，就是呈现抵触后采纳其余的哈希函数计算，直到不再抵触为止。
，其中 RHi 为不同的哈希函数。
3. 链地址法
链接地址法不同与前两种办法，他是在呈现抵触的中央存储一个链表，所有的同义词记录都存在其中。形象点说就行像是在呈现抵触的中央间接把后续的值摞下来。例如 HashMap，如下图。
4. 建设公共溢出区
建设公共溢出区的根本思维是：假如哈希函数的值域是 [1,m-1]，则设向量 HashTable[0…m-1] 为根本表，每个重量寄存一个记录，另外设向量 OverTable[0…v]为溢出表，所有关键字和根本表中关键字为同义词的记录，不论它们由哈希函数失去的哈希地址是什么，一旦发生冲突，都填入溢出表。
