胖蔡说技术Hash算法又称散列函数，指的是通过散列算法将任意长度的输入数据转换成固定长度的输出。这个输出就是我们得到的hash值。常见的hash算法有：MD5、SHA-1、SHA-256、RipeMD-160。
什么是hash碰撞？
基石由于hash算法的输入值有足够的大，就会出现了不同输入数据源却出现相同hash的情况。
k1 ≠ k2
h(k1) = h(k2)如何解决hash碰撞？
通过网上资料总结，发现目前常用的解决hash碰撞的方式大致可以分为四种。
1、开放定址法
就是所有的元素通过散列表方式存储，通过下标地址访问获取。这就有可能会存在控件被填满 ，以致于不能插入任何新的元素。在开放寻址法中，当要插入一个元素时，可以连续地检查或探测散列表的各项，直到有一个空槽来放置待插入的关键字为止。有三种技术用于开放寻址法：
- 线性探测：步长是1，逐步增加。
- 二次探测：步长是由另外一个hash函数取模数组长度决定。
- 双重探测：步长按照平方增加。
2、再hash法
再hash法就是当出现hash碰撞时，使用第二个、第三个…哈希函数，直到无冲突为止，一定程度上可以解决问题，但是付出的却是计算翻倍的代价。
3、链接法
将所有关键字为同义词的记录存储在同一线性单链表中，
我们称这种表为同义词子表，在哈希表中只存储所有同义词子表的头指针。对于关键字集合{12,67,56,16,25,37,22,29,47,48,34}，我们用12作为除数，进行除留余数法，可得到下图结构，此时，就不存在哈希冲突换地址的问题，无论有多少个冲突，都只是在当前位置给单链表增加结点的问题。
4、建立公共溢出区
将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。建立一个公共溢出区域，就是把冲突的都放在另一个地方，不在表里面。
