1、什么是hash表

	散列表（hash table，也叫哈希表），是根据关键码值（key value）而直接进行访问的数据结构。

	也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫 散列函数，存放记录的数组叫做散列表。

	给定表M，存在函数f（key），对于任意给定的关键字值 key，代入函数后若能得到包含改关键字的记录在表中的地址，则称表M为哈希（hash）表，函数 f（key）为哈希（hash）函数。

2、hash冲突

	对应不同的关键字可能获得相同的 hash 地址，即 key1 ≠ key2，但是f（key1） = f（key2）。这种现象就是冲突，而且这种冲突只能尽可能的减少，不能完全避免。

	因为哈希函数是从关键字集合和地址集合的映像，通畅关键字集合比较大，而地址集合的元素仅为哈希表中的地址值。

3、常用的hash函数

1、直接定址法

	取 key 的线性函数值作为 hash 值，value = a * key + b

2、除留余数法

	假设数组长度为l，value = key % l

	这一种散列码实现简单，运用比较多，但是如果输入的元素集合不具有一定的规律，比较容易产生冲突。数组的长度最好是质数，被除数为质数在一定程度上可以缓解数据堆积的问题。

3、数字分析法

	对关键字进行分析，取关键字的若干位进行或者组合进行hash计算

4、平方区中法

取关键字平方后中间几位作为哈希地址

4、处理hash冲突的方法

1、开放定址法

	所谓的开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。 

	fi(key) = ( f(key) + di) MOD m  (di = 1,2,3,......,m-1)

2、再哈希法

	再哈希法又叫双哈希法，有多个不同的Hash函数，当发生冲突时，使用第二个，第三个，...... ,等哈希函数

	计算地址，直到无冲突。

（不易发生聚集，但是增加计算时间）

3、链地址法

	每个哈希表节点都有一个next指针，多个哈希表节点可以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以用 next 指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向链表连接起来。

	键值对k2，v2与键值对k1，v1通过计算后的索引值都为2，这时及时产生冲突，但是可以通到next 指将 k2，k1所在的节点连接起来，这样就解决了哈希的冲突问题。

4、建立公共溢出区

	将 哈希表 分为 基本表 和 溢出表两部分

	凡是和基本表发生冲突的元素，依赖包填入溢出表。