Hash（散列函数）

Hash（散列函数）是一个广义的算法，也可以认为是一种思想，使用Hash算法可以提高存储空间的利用率，可以提高数据的查询效率，也可以做数字签名来保障数据传递的安全性。所以Hash算法被广泛地应用在互联网应用中。

散列函数是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把任意长度的输入压缩成摘要，使得数据量变小，将数据的格式固定下来。该函数将数据打乱混合，重新创建一个叫做散列值（hash values，hash codes，hash sums，或hashes）的指纹。散列值通常用一个短的随机字母和数字组成的字符串来代表。

Hash碰撞

对不同的关键字可能得到同一散列地址，即k₁≠k₂，而∫(k₁)＝∫(k₂) ，这种现象称为hash碰撞或hash冲突，解决的方法有：

拉链法

拉出一个动态链表替代静态顺序存储结构，可以避免哈希函数的冲突。

多哈希法

设计多次哈希函数，降低发生冲突的概率。

开放寻址

当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。这种方法有一个通用的再散列函数形式：

Hi=（H（key）+di）% m i=1，2，…，n

建域法

建立一个公共溢出区

Hash算法的用途

1. 数据校验：将文件经过Hash转换成一个指定长度的字符串，可以防止文件被篡改，但是通过加密后的字符串很难逆向推出原文。
2. 唯一标识
3. 哈希表：根据键访问在内存储存位置的数据结构
4. 负载均衡 比如说，现在又多台服务器，来了一个请求，如何确定这个请求应该路由到哪个路由器呢?当然，必须确保相同的请求经过路由到达同一个服务器。一种办法就是保存一张路由关系的表，比如客户端IP和服务器编号的映射，但是如果客户端很多，势必查找的时间会很长。这时，可以将客户端的唯一标识信息(IP、username)进行哈希计算，然后与服务器个数取模，得到的就是服务器的编号。
5. 分布式存储 当我们有大量数据时，一般会选择将数据存储到多个服务器，为了提高读取与写入的速度，决定将文件存储到哪台服务器，就可以通过哈希算法取模的操作来得到。

目前常见的散列算法