哈希函数的定义与功能概述

哈希函数
哈希函数又称为散列函数，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。假设输出值域为S，哈希函数的性质如下：

典型的哈希函数都有无限的输入值域
当哈希函数输入一致时，输出必相同
当哈希函数传入不同的输入值时，返回值可能一样，也可能不一样，由于输入域远大于值域
（重要）很多的不同输入所得的输出值会均匀的分布在S上（但不是绝对均匀）
最后一个性质对于一个优秀的哈希函数是非常重要的，并且这种均匀与数据的输入规律无关。比如“aa1”、"aa2"经过hash后可能结果会相差很多，当一个哈希函数的输出在S中是均匀的，那么我们将输出值对m取余（%m），就会将不定长输入映射到0～m-1空间中，并且在这个空间也保持均匀分布！哈希表就是这么做的，一会再说！哈希函数还有以下特点：
免碰撞：即不会出现输入 x≠y ，但是H(x)=H(y) 的情况，其实这个特点在理论上并不成立，比如目前比特币使用的 SHA256 算法，会有2^256种输出，如果我们进行2^256 + 1 次输入，那么必然会产生一次碰撞，事实上，通过 理论证明 ，通过2^130次输入就会有99%的可能性发生一次碰撞，不过即使如此，即便是人类制造的所有计算机自宇宙诞生开始一直运算到今天，发生一次碰撞的几率也是极其微小的。
隐匿性：也就是说，对于一个给定的输出结果 H(x) ，想要逆推出输入 x ，在计算上是不可能的。如果想要得到 H(x) 的可能的原输入，不存在比穷举更好的方法。
常见的哈希函数有：SHA1、MD5、SHA2等
哈希函数映射
哈希表
哈希表就是利用哈希函数，可以根据关键码而直接进行访问的数据结构，也就是将关键码（Key value）通过哈希函数映射到表中的一个位置来进行访问。由于是直接访问，所以对于哈希表的元素理论上的增删改查时间复杂度都是O(1)。
而计算散列地址的方法有很多种，通常我们使用的是除留余数法，也就是说使用哈希函数对关键字得到的输出值对散列表长度取余得到的余数即为散列地址。