对于散列函数的定义与整数散列

散列定义

对于一个简单的问题，给定N个正整数和M个正整数，要求当M个正整数中的元素如果在N中出现的话就输出YES。

一个很直观的思想即对于遍历M个正整数，然后在N中进行查找，找到的话就输出YES，但是这样的话，其时间效率将达到O(N*M)，当N和M非常大的时候，这个方法根本不能满足实现。

然而我们我已这样，定义一个bool型的hashTable数组，初始化为false

bool hashTable[100001] = {false};

对于每输入一个N中的数时，将该数作为hashTable的下标并设为true，如输入正整数11。

hashTable[11] = true;

这样对于N = {4,1,6,34,12}，M{4,12,1}，在hashTable中下标为4,1,6,34,12的位置为true，其他为false。遍历M判断其是否为true来输出YES。

for(int i =0;i < 3;i++){
	if(hashTable[M[i]]) printf("YES");
}

这便是一个简单散列映射的例子，它的时间效率降到了O(N+M)，这是一个很好的用空间换了时间的策略。

那么什么是散列？

一般来说，散列可以浓缩成一句话“将元素通过一个函数转换为整数，使得该整数可以尽量唯一地代表这个元素”。其中把这个转换函数称为散列函数H,也就是说，如果元素在转换前为ky,那么转换后就是一个整数H(key)。

那么对key是整数的情况来说，有哪些常用的散列函数呢？一般来说，常用的有直接定址法、平方取中法、除留余数法等，其中直接定址法是指恒等变换（即Hkey)=key,上面的例子就是直接把key作为数组下标，是最常见最实用的散列应用，或是线性变换（即H(key)=a*key+b)；而平方取中法是指取key的平方的中间若干位作为hash值（很少用）。一般来说比较实用的还有除留余数法，我们对其进行特别介绍。

除留余数法

除留余数法是指把key除以一个数mod得到的余数作为hash值的方法，即
H(key)=key mod，通过这个散列函数，可以把很大的数转换为不超过mod的整数，这样就可以将它作为可行的数组下标（注意：表长TSize必须不小于mod,不然会产生越界）。显然，当mod是一个素数时，Hkey)能尽可能覆盖[0,mod]范围内的每一个数。但是稍加思考便可以注意到，通过除留余数法可能会有两个不同的数key1和key2,它们的hash值H(key1)与H(key2)是相同的，这样key1已经把表中位置为H(key1)的单元占据时，key2便不能再使用这个位置了。我们把这种情况叫作“冲突”。既然冲突不可避免，那就要想办法解决冲突。下面以三种方法来解决冲突为例。

1.线性探查法

既然key1以及占据了这个位置，那么就检查H(key2)+1这个位置是否被占用，如果没有，就使用这个位置，否则继续，当检查超过表长时就回到表的首位继续检查，这个做法容易导致扎堆，即表中连续若干个位置都被使用，这在一定程度上会降低效率。

2. 平方探查法

在平方探查法中，为了尽可能避免扎堆现象，当表中下标为Hky)的位置被占时，将按下面的顺序检查表中的位置：H(key)+1的平方、H(key)-12、H(key)+2的平方、H(key)-2的平方、H(key)+3的平方等。如果检查过程中H(key)+k超过了表长TSize,那么就把H(key)+k的平方对表长TSize取模：
如果检查过程中出现Hkey)-k的平方<0的情况（假设表的首位为0），那么将((H(key)-k的平方%TSize+TSize)%TSize作为结果（等价于将H(key)-k的平方不断加上TSize直到出现第一个非负数）。如果想避免负数的麻烦，可以只进行正向的平方探查。可以证明，如果k在[0,TSize)范围内都无法找到位置，那么当k≥TSz时，也一定无法找到位置。

3.链地址法

和上面两种方法不同，链地址法不计算新的hash值，而是把所有Hkey)相同的key连接成一条单链表（可以在学习完7.3小节后回过头来看）。这样可以设定一个数组Lk,范围是Link[0]~Link[mod],其中Link[h]存放H(key)=h的一条单链表，于是当多个关键字key的hash值都是h时，就可以直接把这些冲突的key直接用单链表连接起来，此时就可以遍历这条单链表来寻找所有H(key)=h的key。当然，一般来说，可以使用标准库模板库中的map来直接使用hash的功能(C+l1以后可以用unordered map,速度更快)，因此除非必须模拟这些方法或是对算法的效率要求比较高，一般不需要自己实现上面解决冲突的方法。