哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
顺序搜索以及二叉树搜索树中，元素存储位置和元素各关键码之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。搜索的效率取决于搜索过程中元素的比较次数。
理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。
如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。
当向该结构中：
插入元素时：根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放
搜索元素时：对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功
该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者
称散列表)
例如：数据集合{180，750，600，430，541，900，460}
用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快
问题：按照上述哈希方式，向集合中插入元素443，会出现什么问题？
这回就要引出一个概念叫哈希冲突：对于两个数据元素的关键字 和 （i !=j），有 ！= ，但有：HashFun(Ki) == HashFun(Kj)即不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。
解决哈希冲突两种常见的方法是：闭散列和开散列
闭散列：
闭散列：也叫开放地址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到表中“下一个” 空位中去
那如何寻找下一个空余位置？ 这里就要用到两种方法：线性探测和二次探测
线性探测
设关键码集合为{37, 25, 14, 36, 49, 68, 57, 11}，散列表为HT[12]，表的大小m = 12，假设哈希函数为：Hash(x) = x %p（p = 11，是最接近m的质数），就有：
Hash(37) = 4
Hash(25) = 3
Hash(14) = 3
Hash(36) = 3
Hash(49) = 5
Hash(68) = 2
Hash(57) = 2
Hash(11) = 0
其中25，14，36以及68，57发生哈希冲突，一旦冲突必须要找出下一个空余位置
线性探测找的处理为：从发生冲突的位置开始，依次继续向后探测，直到找到空位置为止
【插入】
1）. 使用哈希函数找到待插入元素在哈希表中的位置
2）. 如果该位置中没有元素则直接插入新元素；如果该位置中有元素且和待插入元素相同，则不用插入；如果该位置中有元素但不是待插入元素则发生哈希冲突，使用线性探测找到下一个空位置，插入新元素；
采用线性探测，实现起来非常简单，缺陷是：
一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。 如何缓解呢？ 引入新概念负载因子（负载因子的应用在下一篇博文）和二次探测
二次探测
发生哈希冲突时，二次探查法在表中寻找“下一个”空位置的公式为：
Hi= (Ho + i^2) % m,Hi = (Ho -i^2 ) % m, i = 1,2,3…，(m-1)/Ho. 是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小假设数组的关键码为37, 25, 14, 36, 49, 68, 57, 11，取m = 19，这样可设定为HT[19]，采用散列函数Hash(x) = x % 19，则：
Hash(37)=18
Hash(25)=6
Hash(14)=14
Hash(36)=17
Hash(49)=11
Hash(68)=11
Hash(57)=0
Hash(11)=11
采用二次探测处理哈希冲突：
研究表明：当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5；如果超出必须考虑增容