? ? ? ?大家好，我是练习编程时长两年半的昆工第一ikun，今天我们来分享查找算法中的一个——哈希查找，哈希查找适用于有庞大的数据量时的查找，是一种很好用的查找算法，话不多说，开团！！！
一、六种哈希函数的构造方法：
1，直接定址法：
函数公式：f(key)=a*key+b (a,b为常数)?
比如：关键字是2，a=1，b=1，那么2+1=3就为存储位置。
这种方法的优点是：简单，均匀，不会产生冲突。但是需要事先知道关键字的分布情况，适合查找表较小并且连续的情况。
2，数字分析法：
比如我们的11位手机号码“136XXXX7887”，其中前三位是接入号，一般对应不同运营公司的子品牌，如130是联通如意通，136是移动神州行，153是电信等。中间四们是HLR识别号，表示用户归属地。最后四们才是真正的用户号。
若我们现在要存储某家公司员工登记表，如果用手机号码作为关键字，那么极有可能前7位都是相同的，所以我们选择后面的四们作为哈希地址就是不错的选择。
3，平方取中法：
故名思义，比如关键字是1234，那么它的平方就是1522756，再抽取中间的3位就是227作为哈希地址。
4，折叠法：
折叠法是将关键字从左到右分割成位数相等的几个部分(最后一部分位数不够可以短些)，然后将这几部分叠加求和，并按哈希表表长，取后几位作为哈希地址。
比如我们的关键字是9876543210，哈希表表长三位，我们将它分为四组，987|654|321|0 ，然后将它们叠加求和987+654+321+0=1962，再求后3位即得到哈希地址为962，哈哈，是不是很有意思。
5，除留余数法：
函数公式：f(key)=key mod p (p<=m)m为哈希表表长。
这种方法是最常用的哈希函数构造方法。
6，随机数法：
函数公式：f(key)= random(key)。
这里random是随机函数，当关键字的长度不等时，采用这种方法比较合适。
二、解决冲突
设计得最好的哈希函数也不可能完全避免冲突，当我们在使用哈希函数后发现两个关键字key1!=key2，但是却有f(key1)=f(key2)，即发生冲突。解决冲突，有2种方法
解决冲突的方法有以下两种：
1.开放地址法
如果两个数据元素的哈希值相同，则在哈希表中为后插入的数据元素另外选择一个表项。当程序查找哈希表时，如果没有在第一个对应的哈希表项中找到符合查找要求的数据元素，程序就会继续往后查找，直到找到一个符合查找要求的数据元素，或者遇到一个空的表项。
2.链地址法
将哈希值相同的数据元素存放在一个链表中，在查找哈希表的过程中，当查找到这个链表时，必须采用线性查找方法。
?
我将采用除留余数法来构造哈希表，用开放地址法来解决冲突，代码如下：
#include <stdio.h>
int hash(int *a, int len, int k);
int main(int argc, char *argv[])
{
int a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int ret = hash(a, 10, 9);
printf("该数的下标是%d\n", ret);
return 0;
}
int hash(int *a, int len, int k)
{
int buf[10], i, j = 0, n, arr[10];
for(i = 0; i < 10; i++){
buf[i] = -1;
}
for(i = 0; i < len; i++){
n = a[i] % 7;
if(buf[n] == -1){
buf[n] = a[i];
}
else{
arr[j] = a[i];
j++;
}
}
j = 0;
for(i = 0; i < 10; i++){
if(buf[i] == -1){
buf[i] = arr[j];
j++;
}
}
for(i = 0; i < 10; i++){
if(k == buf[i]){
for(j = 0; j < len; j++){
if(buf[i] == a[j]){
return j;
}
}
}
}
}比如我要查找9这个数据的位置，运行结果如下：
?
? ? ? ?好了，今天分享的哈希查找就结束了，哈希查找有很多种方法，我只是列举了其中一种，欢迎大家补充，互相交流学习，我是练习编程时长两年半的昆工第一ikun，我们明天再见。