一、什么是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]为溢出表，所有关键字和根本表中关键字为同义词的记录，不论它们由哈希函数失去的哈希地址是什么，一旦发生冲突，都填入溢出表。