哈希

hash（散列、杂凑）函数，是将任意长度的数据映射到固定长度的域上。

即将一段数据M进行杂糅，然后输出一段数据h。作为他的数据特征（指纹）

即无论m多长，输出的h的长度是固定的。

Hash表采用一个映射函数 f : key —> address 将关键字映射到该记录在表中的存储位置，从而在想要查找该记录时，可以直接根据关键字和映射关系计算出该记录在表中的存储位置.

通常情况下，这种映射关系称作为Hash函数，而通过Hash函数和关键字计算出来的存储位置(注意这里的存储位置只是表中的存储位置，并不是实际的物理地址)称作为Hash地址.

比如上述例子中，假如联系人信息采用Hash表存储，则当想要找到“李四”的信息时，直接根据“李四”和Hash函数计算出Hash地址即可

hash函数

hash函数就是把任意长的输入字符串变化成固定长的输出字符串的一种函数。输出字符串的长度称为hash函数的位数。

一句话：散列（Hashing）通过散列函数将要检索的项与索引（散列，散列值）关联起来，生成一种便于搜索的数据结构（散列表）。

散列函数的性质：

同一函数的散列值不相同，那么其原始输入也不相同，上图中k1，k3和k4。（确定性）

散列函数的输入和输出不是唯一对应关系的，如果两个散列值相同，两个输入值很可能是不相同的，上图中的k2，k5这种情况称为“哈希碰撞”。（不确定性）

hash函数的构造准则：简单、均匀

1、 散列函数的计算简单，快速；

2、 散列函数能将关键字集合K均匀地分布在地址集{0,1，…，m-1}上，使冲突最小。