散列
（英语：Hashing）是电脑科学中一种对数据的处理方法，通过某种特定的函数/算法（称为散列函数/算法）将要检索的项与用来检索的索引（称为散列，或者散列值）关联起来，生成一种便于搜索的数据结构（称为散列表）。旧译哈希（误以为是人名而采用了音译）。它也常用作一种信息安全的实现方法，由一串数据中经过散列算法（Hashing algorithms）计算出来的数据指纹（data fingerprint），经常用来识别文件与数据是否有被窜改，以保证文件与数据确实是由原创者所提供。
如今，散列算法也被用来加密存在数据库中的密码（password）字符串，由于散列算法所计算出来的散列值（Hash Value）具有不可逆（无法逆向演算回原本的数值）的性质，因此可有效的保护密码。
散列函数
散列函数是从某一类数据中提取的一个小的数字“指纹”。
使用散列的方式包括：
- 加密散列: 在信息安全领域使用
- 散列表: 一种使用散列函数将键名和键值关联起来的数据结构
- 关联数组: 一种常常使用散列表来实现的数据结构
- 几何散列 ：寻找相同或相似的几何形状的一种有效方法
常见的散列算法
哈希冲突解决方法
（1）开放定址法：
就是在发生冲突后，通过某种探测技术，去依次探查其他单元，直到探查到不冲突为止，将元素添加进去。
假如是在index的位置发生哈希冲突，那么通常有一下几种探测方式：
-
线性探测法（线性探测再散列）：向后依次探测index+1，index+2…位置，看是否冲突，直到不冲突为止，将元素添加进去。
-
平方探测法：不探测index的后一个位置，而是探测2^i位置，比如探测2^0位置上时发生冲突，接着探测2^1位置，依此类推，直至冲突解决。
注意：
（1）用开放定址法建立散列表时，建表前须将表中所有单元(更严格地说，是指单元中存储的关键字)置空。
（2）两种探测方法的优缺点。
-
线性探测法虽然在哈希表未满的情况下，总能保证找到不冲突的地址，但是容易发生二次哈希冲突的现象。比如在处理若干次次哈希冲突后k,k+1,k+2位置上的都存储了数据，那下一次存储地址在k,k+1,k+2,k+3位置的数据都将存在k+3位置上，这就产生了二次冲突。
-
这里引入一个新的概念，堆积现象是指用线性探测法处理哈希冲突时，k,k+1,k+2位置已存有数据，下一个数据请求地址如果是k,k+1,k+2,k+3的话，那么这四个数据都会要求填入k+3的位置。
-
平方探测法可以减少堆积现象的发生，但是前提是哈希表的总容量要是素数4n+3才可以。
（2）链地址法（开散列法）
基本思想：
链表法就是在发生冲突的地址处，挂一个单向链表，然后所有在该位置冲突的数据，都插入这个链表中。插入数据的方式有多种，可以从链表的尾部向头部依次插入数据，也可以从头部向尾部依次插入数据，也可以依据某种规则在链表的中间插入数据，总之保证链表中的数据的有序性。Java的HashMap类就是采取链表法的处理方案。
例：已知一组关键字为(19，14，23，01，68，20，84，27，55，11，10，79)，则按哈希函数 H(key) = key MOD13 和链地址法处理冲突构造所得的哈希表为：
（3）再哈希法：（双散列法）
在发生哈希冲突后，使用另外一个哈希算法产生一个新的地址，直到不发生冲突为止。这个应该很好理解。
再哈希法可以有效的避免堆积现象，但是缺点是不能增加了计算时间和哈希算法的数量，而且不能保证在哈希表未满的情况下，总能找到不冲突的地址。
（4）建立一个公共溢出区：
建立一个基本表，基本表的大小等于哈希表的大小。建立一个溢出表，所有哈希地址的第一个记录都存在基本表中，所有发生冲突的数据，不管哈希算法得到的地址是什么，都放入溢出表中。
但是有一个缺点就是，必须事先知道哈希表的可能大小，而且溢出表里的数据不能太多，否则影响溢出表的查询效率。实际上就是要尽量减少冲突。
注意：本文归作者所有，未经作者允许，不得转载
