哈希函数和哈希表

哈希函数
哈希算法是通过一个哈希函数，将一段数据（也包括字符串、较大的数字等）转化为能够用变量表示或是直接就可作为数组下标的数字，这样转化后的数值我们称之为哈希值， 也就是算出一个数来代表一个字符串。
我们通过哈希值从而实现很快地查找和匹配

它又名散列函数，对于经典哈希函数来说，它具有以下5点性质：
1、输入域无穷大
2、输出域有穷尽
3、输入一样输出肯定一样
4、当输入不一样输出也可能一样（哈希碰撞）
5、不同输入会均匀分布在输出域上（哈希函数的散列性）

哈希表流程
现在要存储和使用下面的线性表：A(1,75,324,43,1353,91,40)。

定义一个一维数组A[1…n]，此时n=7，将表中元素按大小顺序存储在A[i]中，但这样就算使用二分查找，我们仍需要用O(log n)的时间去查找某个元素。

为了用O(1)的时间实现查找，可以开一个一维数组A[1…1353]，使得A[key]=key，但显然造成了空间上的很大浪费，尤其是数据范围很大时。

为了使空间开销减少，我们可以对第二种方法加以优化，设计一个哈希函数H(key) = key mod 13，然后令A[H(key)]=key，这样一来定义一个一维数组A[0…12]就已足够，这种方法就是哈希表。

但刚才那样的存储是有问题的，如H(1)=H(40)=1，在存储40时又把1给覆盖掉了，那么查询就会出现错误，这种不同的数据产生相同哈希值的情况我们称之为冲突。

这里与字符串Hash有所不同，可能不论我们怎样选用哈希函数，还是很难避免产生冲突。

因此我们考虑对每一个哈希值记一个链表（其实也就相当于邻接表），把所有等于同一个哈希值的数字都存储下来，而查询只要遍历对应的链表即可，这样实际复杂度取决于查询的链表长度，也可以看做是常数级。

例如我们定义哈希函数H(x) = x mod 16，插入一些数据的效果如下图。

转自
https://www.cnblogs.com/ljy-endl/p/11462207.html