经典算法学习——哈希查找

哈希查找也称为散列查找。所谓的哈希其实就是在记录的存储位置和记录的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f(key)。查找时，根据这个确定的对应关系找到给定值的映射f(key),若查找集合中存在这个记录，则必定在f(key)的位置上。哈希技术既是一种存储方法，也是一种查找方法。示例代码上传至：https://github.com/chenyufeng1991/hashsearch 。

六种哈希函数的构造方法：

（1）直接定址法

函数公式：f(key) = a * key + b（a,b为常数）

这种方法的优点是：简单、均匀，不会产生冲突。但是需要事先知道关键字的分布情况，适合查找表较小并且连续的情况。

（2）数字分析法

也就是取出关键字中的若干位组成哈希地址。比如我们的11位手机号是“187****1234”，其中前三位是接入号，一般对应不同的电信公司。中间四位表示归属地。最后四位才表示真正的用户号。

如果现在要存储某个部门的员工的手机号，使用手机号码作为关键字，那么很有可能前面7位都是相同的，所以我们选择后面的四位作为哈希地址就不错。

（3）平方取中法

取关键字平方后的中间几位作为哈希地址。由于一个数的平方的中间几位与这个数的每一位都有关，所以平方取中法产生冲突的机会相对较小。平方取中法所取的位数由表长决定。

如：k=456，k^2=207936,如果哈希表的长度为100，则可以取79（中间两位）作为哈希函数值。

（4）折叠法

折叠法是将关键字从左到右分割成位数相等的几个部分（最后一部分位数不够可以短），然后将这几部分叠加求和，并按哈希表表长，取后几位作为哈希地址。当关键字位数很多，而且关键字中每一位上数字分布大致均匀时，可以使用折叠法。

如：我们的关键字是9876543210，哈希表表长三位，我们可以分为四组：987 | 654 | 321 | 0，然后将他们叠加求和：987+654+321+0 = 1962,再取后三位就可以得到哈希地址为962.

（5）除留余数法

选择一个适当的正整数p（p<=表长），用关键字除以p，所得的余数可以作为哈希地址。即：h(key) = key % p(p<=表长)，除留余数法的关键是选取适当的p，一般选p为小于或等于哈希表的长度(m)的某个素数。

如：m = 8,p=7.

m = 16,p = 13.

m = 32,p = 31.

（6）随机数法

函数公式：f(key) = random(key). 这里的random是随机函数，当关键字的长度不等时，采用这种方式比较合适。

总之，哈希函数的规则就是：通过某种转换关系，使关键字适度的分散到指定大小的顺序结构中。越分散，查找的时间复杂度就越小， 空间复杂度就越高。哈希查找明显是一种以空间换时间的算法。

 

上面提到了如何构造一个哈希函数，那就不得不提如何避免冲突的算法。

（1）开放定址法

当冲突发生时，使用某种方法在哈希表中形成一探查序列。然后沿着该探查序列逐个单位的查找，直到找到一个开放的地址（即该地址单元为空）为止。对于哈希表中形成一探查序列时，可以有3种不同的方法：

1.线性探测法

将散列看成一个环形表，探测序列是（假设表长为m）：

h(k),h(k)+1,h(k)+2.....m-1,0,1......h(k)-1。用线性探测法解决冲突时，求下一个开放地址的公式为：hi = (h(k)+i) mod m.

2.二次探测法

二次探测法的探测序列依次是12，-12，22，-22等等。当发生冲突时，求下一个开放地址的公式为：

h2i-1=(h(k)+i2)modm

h2i=(h(k)-i2)modm(1=优点：减少了堆集发生的可能性；

缺点：不容易探测到哈希表空间。

3.伪随机探测法

采用随机探测法解决冲突时，下一个开放地址的公式为：hi=(h(k)+ri)modm。

其中r1,r2,...,rm-1是一个随机排列。

（2）再哈希法

当冲突发生时，使用另一个函数计算得到一个新的哈希地址，直到冲突不再发生时为止。hi=rhi(key)i=1,2,…,k 。其中rhi均是不同的哈希函数。优点是不易产生聚集，缺点是增加了计算时间。

（3）链地址法

将所有关键字为同义词的结点链接在同一个单链表中。若选定的哈希函数所产生的哈希地址为0~m-1,则可以将哈希表定义成一个由m个链表头指针组成的指针数组。优点是：不产生聚集；由于结点空间是动态申请的，故更适合造表前无法确定表长的情况；从表中删除节点容易。

（4）公共溢出区法

假设哈希函数的值域为[0...m-1]，则设向量hashtable[0...m-1]为基本表，每个分量存放一个记录，另设立向量overtable[0..v]为溢出表。所有关键字和基本表中关键字为同义词的记录，不管它们由哈希函数得到的哈希地址是什么，一旦发生冲突，都被填入溢出表中。

在哈希表上进行查找的过程和建表的过程基本一致。假设给定的值为k，根据建表时设定的哈希函数h，计算出哈希地址h(k),若表中该地址对应的空间未被占用。则查找失败。否则将该地址中的节点与给定值k比较，若相等则查找成功，否则按建表时设定的处理冲突方法找下一个地址，如此反复下去，直到找到某个地址空间未被占用（查找失败）或者关键字比较相等（查找成功）为止。

代码如下：

//
//  main.c
//  hashsearch
//
//  created by chenyufeng on 16/2/17.
//  copyright © 2016年 chenyufengweb. all rights reserved.
//

#include "stdio.h"
#include "stdlib.h"

#define hashsize 7 // 定义散列表长为数组的长度
#define nullkey -32768

typedef int status;
typedef struct{
    int *elem; // 数据元素存储地址，动态分配数组
    int count; //  当前数据元素个数
}hashtable;

// 散列表表长，全局变量
int m = 0;

void inithashtable(hashtable *hashtable);
status hash(int key);
void insert(hashtable *hashtable,int key);
status search(hashtable *hashtable,int key);
void displayhashtable(hashtable *hashtable);

int main(int argc, const char * argv[]) {

    int result;
    hashtable hashtable;
    int arr[hashsize] = {13,29,27,28,26,30,38};

    //初始化哈希表
    inithashtable(&hashtable);

    /**
     *  向哈希表中插入数据;
     也就是把元素使用哈希函数映射到哈希表中；
     */
    for (int i = 0;i < hashsize;i++){
        insert(&hashtable,arr[i]);
    }
    //数据已存到哈希表中，打印观察哈希表，元素的位置和原数组是完全不一样的
    displayhashtable(&hashtable);

    //查找数据
    result = search(&hashtable,30);
    if (result == -1){
        printf("没有找到！");
    }else{
        printf("在哈希表中的位置是:%d\n",result);
    }

    return 0;
}

//初始化一个空的哈希表
void inithashtable(hashtable *hashtable){

    m = hashsize;
    hashtable->elem = (int *)malloc(m * sizeof(int)); //申请内存
    hashtable->count = m;
    for(int i = 0;i < m;i++){
        hashtable->elem[i] = nullkey;
    }
}

//哈希函数(除留余数法)
status hash(int key){
    return key % m;
}

//插入
void insert(hashtable *hashtable,int key){

    /**
     *  根据每一个关键字，计算哈希地址hashaddress；
     */
    int hashaddress = hash(key); //求哈希地址
    /**
     *  发生冲突，表示该位置已经存有数据
     */
    while(hashtable->elem[hashaddress] != nullkey){
        //利用开放定址的线性探测法解决冲突
        hashaddress = (hashaddress + 1) % m;
    }
    //插入值
    hashtable->elem[hashaddress] = key;
}

//查找
status search(hashtable *hashtable,int key){
    //求哈希地址
    int hashaddress = hash(key);
    //发生冲突
    while(hashtable->elem[hashaddress] != key){
        //利用开放定址的线性探测法解决冲突
        hashaddress = (hashaddress + 1) % m;
        if (hashtable->elem[hashaddress] == nullkey || hashaddress == hash(key)){
            return -1;
        }
    }
    //查找成功
    return hashaddress;
}

//打印结果
void displayhashtable(hashtable *hashtable){
    for (int i = 0;i < hashtable->count;i++){
        printf("%d ",hashtable->elem[i]);
    }
    printf("\n");
}

在c语言中，我们常常会设定一些预定义常量，或者说是函数的结果状态码，如下所示：

#define true 1
#define false 0
#define ok 1
#define error 0
#define infeasible -1
#define overflow -2

因为在c语言中是没有bool布尔这种数据类型的，所以上面的预定义可以简化编程。我们有时候还会进行如下的预定义：

typedef int status;

表示status是函数的返回类型，其值是函数结果状态代码。我在上述代码中也使用了这种预定义。 =(m-1)>=(m-1)>