在元素的关键字k和元素的存储位置p之间建立一个对应的关系f，使得p= f(k)，其中f就称为哈希函数。插入数据时，把关键字为k的元素直接存入f(k)的位置，以后当查找关键字为k的元素时，就直接找f(k)的位置，从而达到了关键字直接存取元素的目的。
因为哈希函数总是不完美的，当关键字集合很大时，关键字值不同的元素可能会映射到哈希表中的同一个地址上，即k1!=k2，但f(k1)==f(k2)。这就是哈希冲突。
哈希冲突的解决方法
一、开放定址法
插入元素时，先根据元素关键字，算出元素在哈希表中的位置，如果出现了冲突，使用某种探测技术在散列表中形成一个探测序列，沿此序列逐个位置往下走，直到碰到空的位置（开放的地址）就进行插入。
查找元素的时候，同样先根据元素关键字，计算出元素在哈希表中的位置，如果该位置上的元素的关键字并不是我们需要查找的则按探测序列往下走，直到找到所需元素或者遇到空的位置（开放的地址）则判定为不存在该元素。
Note: 用开放定址建立散列表时，建表时，应该将表中的所有单元（单元中存储的关键字）置空。
形成探测序列的方法有主要有三种：线性探测法、线性补偿探测法、随机探测法
1、线性探测法
将散列表T(0,1, … ,m-1)看成是一个循环的向量，若初始探测的地址为d ( d= f(key))，则最长的探测序列为：
d, d+1, d+2, … , m-1 , 0 , 1 , … ,d-1
或者用函数形式表示探测序列
arr = ( f ( key ) + i ) % m (0 ≤ i ≤ m-1)
线性探测法处理冲突，思路清晰，算法简单，但存在以下缺点：
①当整个哈希表都被填满的时候需要另作处理，比如再建立一个顺序表来存储溢出数据
②出现哈希冲突会使删除工作变得困难，因为出现哈希冲突时，会按探测序列一路走下去查找所需元素，如果中间某个元素被删了，就会直接返回查找不到。因此删除不能是真正的删除，只能给要删除的元素标上标记
③线性探测法容易产生堆聚现象。堆聚现象就是指在哈希表里，元素很容易占据连续的位置，并且形成一大片，同时形成正反馈，越来越容易结块。而一旦堆聚的话，哈希表的效率就会变成O(n)
2、线性补偿探测法
线性补偿探测法相当于线性探测法的步长从1改到k，即探测序列的函数表示为：
arr = ( f (key) +ki ) % m (0 ≤ i ≤ m-1 , k与m互质)
相对于线性探测法而言，可能在一定程度上减少了堆聚现象
3、随机探测法
将线性探测的步长从常数改为随机数，在实际程序中应预先用随机数发生器产生一个随机序列，将此序列作为依次探测的步长。
相对于线性探测法而言，也在一定程度上减少了堆聚现象
二、再哈希法
这种方法就是构造多个不同的哈希函数f1,f2, … 。
当插入元素（元素关键字为key）时，先到 f1(key)的位置，如果出现了冲突，则到 f2(key)的位置，依次类推。
当查找元素（元素关键字为key）时，先到f1(key)的位置，如果f1(key)是空位置（开放地址），则返回找不到，如果该位置上元素的关键字就是所需，则返回该值，否则就继续找f2(key)，以此类推。
特点：不易产生堆聚，但增加了计算时间，并且不能保证在元素个数少于哈希表容量的时候能稳定插入元素
三、链地址法
可以理解为哈希函数计算出来的地址存储的不是一个元素，而是存储了一个单链表的头指针。
当插入元素（元素关键字为key）时，通过f (key)计算出一个链表的首地址，并且按照尾插法的方式插入元素。
当查找元素（元素关键字为key）时，通过f (key)计算出一个链表的首地址，按照顺序遍历的方式查找元素。
特点：不会出现哈希表溢出的情况、插入删除操作方便，但是一旦当元素个数远大于哈希表基本容量的情况，插入删除操作就相当于O(n)，即遍历链表的复杂度
四、建立公共溢出区
将哈希表分为基本表和溢出表两部分，两个表的哈希函数相同，凡是和基本表发生冲突的元素，一律填入溢出表。
特点：不能保证在元素个数少于哈希表容量的时候能稳定插入元素（比如只有一个基本表一个溢出表，而插入了哈希函数计算出相同地址的三个不同元素，最后一个元素插入时就会失败）
哈希函数的构造方法
构造原则：
①函数本身便于计算
②计算出来的地址分布均匀（即对任意关键字k，f(k)对应不同地址的概率相等，目的是尽可能减少冲突）
一、数字分析法
如果事先知道关键字的集合，并且关键字的位数比哈希表的地址码位多时，可以从关键字中选出分布较均匀的若干位，构成哈希地址。
例如：我们有50个元素，关键字可表示（编码）为6位十进制的整数，d1d2d3d4d5d6，如果哈希表容量取100，则哈希表地址空间为00~99。假设经过分析，各关键字中d2和d6取值相对均匀，则哈希函数f (key) = f( d1d2d3d4d5d6) = d2d6。就比如 f(123456)=26。
二、平方取中法
如果无法确定关键字中哪几位分布较均匀时，可以先求出关键字的平方值，然后按需要取平均值的中间几位作为哈希地址。因为，平方后中间几位和关键字中每一位都相关，故不同关键字会以较高概率产生不同的哈希地址。
例如：我们把英文字母在字母表中的位置序号作为该英文字母的内部编码。例如K是第十一位，编码为11，E为05，Y为25，A为01，B为02。于是可得”KEYA”,”KEYB”,”AKEY”,”BKEY”的编码，将其平方后取中间三位即可当作其对于的哈希地址。
+------+----------+-----------------+--------------+ | key_ | Encoding | After_Pow | Hash_address| +------+----------+-----------------+-------------+ | AKEY | 01110525 | 001233265775625 | 265 | | BKEY | 02110525 | 004454315775625 | 315 | | KEYA | 11050201 | 122157778355001 | 778 | | KEYB | 11050202 | 126564795010404 | 795 | +------+----------+-----------------+-------------+
三、分段叠加法
这种方法是让关键字分段相加得到地址，具体怎么分段要看哈希表的地址位数。比如哈希表的容量就是1000，则它是三位十进制的哈希地址（000~999）。那么关键字也要整（编码）成十进制，并且每三位划分为一段，最后相加。相加时如果是直接相加就称为移位法，如果时折叠相加就称为折叠法，具体如下：
1 2 3 1 2 3 4 5 6 6 5 4 + 7 8 + 7 8 -------------- ---------------- 1 3 5 9 1 5 5 7 （移位法） （折叠法：奇数行正常摆放，偶数行反着放）
最后取后三位作为哈希地址即可
四、除留余数法
假声哈希表长为m，p为小于等于m的最大素数，则哈希函数为f (k ) = k % p
例如：已知散列元素为( 18 ,75, 60, 43, 54, 90, 46)，表长m = 10，p=7，则有
f (18) = 18%7=4 ，f(75) = 75 % 7 =5 ，f(60) = 60 % 7 =4
f (43) = 43%7=1 ，f(54) = 54 % 7 =5 ，f(90) = 90 % 7 =6
f (46) = 46%7=4 ，
但此时冲突较多，应该让p更大一点，所以容量m 也要更大，当取m=p=13时，有如下结果
f (18) = 18%13=5 ，f(75) = 75 %13 =10 ，f(60) = 60 % 13 =8
f (43) = 43%13=4 ，f(54) = 54 %13 =2 ，f(90) = 90 % 13 =12
f (46) = 46%13=7
此时则不会发生冲突
五、伪随机数法
采用一个伪随机函数作为哈希函数，即f(key) = random( key)
实际应用中，应该根据具体情况定制哈希函数，并且通过实际数据去测试性能，一般有以下五个因素要考虑
①计算哈希函数所需时间
②关键字长度
③哈希表大小
④关键字分布情况
⑤记录查找的频率