散列表

àì夳堔傛蜴生んèń 2022-08-01 01:22 196阅读 0赞

散列表

前几天看《linux内核设计与实现》的时候，发现一个新名词（对于我来说）“散列表”，直接给我看蒙住了，散列表是个什么鬼，于是今天晚上找了本数据结构的书，来学习下散列表这个新东西。

散列表：

既是一种存储的技术，又是一种查找的技术，也就是说可以用它来查找与存储，不同于一般的存储与查找，一般正常的存储，举个例子一个已经存在的数组，其中每一个数据内容与它的下标都是一一对应的关系，需要查找时就进行一次遍历要么找到，要么没找到。很直接，要找的内容都是固定的，但是散列表并不用来处理这类查找。散列表把你需要查找的关键字与其下标建立了一种关系，就像上面所说过的，一个数组的下标和它里面存在的内容没有半毛钱的关系。但是散列表则不然，散列表把存储的东西与下标建立了一种有规则的关系，这种规则你自己定。但是定的方法很讲究，一会再说。

还是给一个关于散列表的官方定义吧

散列表：

[散列表][Link 1]（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的 [数据结构][Link 2]。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做 [散列函数][Link 3]，存放记录的 [数组][Link 4]叫做 [散列表][Link 1]。

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

以上定义来自百度百科。

其实和我说的差不多，那个有规则的关系就是哈希函数。可以同时定义多个哈希函数。

现在来说说散列表的构造方法：

直接定址法：

取关键字的某个线性函数值为散列表地址

f(key) = a \* key + b;

数字分析法：

将某些特定的数字进行处理，例如131XXXXX1234，132XXXXX6789.。。。。例如这些手机号，其实只有后边的4位数字是相同的那么我们，就应当取处后面的4位进行比较甄别。

简单来说就是屏蔽掉重复的数字，主要处理那些能够表征问题的数字。

平方取中法：

就是如字面意思将一个数字平方然后取中间的某几位数字，其实做了这么多只是为了排除那些重复的关键字，这是我们的原则，根据不同的需求选择不同的哈希方法，如果有人可以想出万用的哈希函数，那么也不失为一个壮举。

除留余数法：

就是给定的东西取余，得出余数，以余数作为存储的下标，当然余数是很可能相同的所以如果出现相同的情况就对除数+1，一直这样下去，直到找出可以放置的位置为止。

还有随机数法，溢出数表。。。。。多种方法，原则就是打造出适合问题的哈希函数。

下面贴上一个代码：就是使用余数法建议一个散列表，这个散列表初始化位5个存储位置，首先进行5个数字的存入操作，然后可以输入一个数字，查找出它在散列表中的存储位置。

#include<stdlib.h>
    #include<string.h>
    #define SUCCESS 1
    #define UNSUCCESS 0
    #define HASHSIZE  12
    #define NULLKEY   -32768
    #define OK        2
    
    typedef struct hashtable{
        int *elem;   //数据元素存储基址，动态分配数组
        int count;   //当前数据元素个数
    }HASHTABLE;
    
    int m = 5;       //散列表表长
    
    int init_hashtable(HASHTABLE *H)    //初始化散列表
    {
        int i;           
        H->count = m;
        H->elem  = (int *)malloc(m*sizeof(int));
        if(H->elem == NULL){
            printf("malloc error :%d\n",__LINE__);
        }
        for(i = 0;i<m;i++)
        {
            H->elem[i] = NULLKEY;
        }
        return OK;
    }
    
    
    int HASH(int key)           //散列函数
    {
        return key % m;
    }
    void inserthash(HASHTABLE *H,int key)    //插入关键字进散列表
    {
        int addr = HASH(key);               //求散列表
        while(H->elem[addr] != NULLKEY)     //如果不为空，则冲突
            addr = (addr+1)%m;              //开放定址法的线性探测
        H->elem[addr] = key;                //直到有空位后插入关键字
    }
    
    int searchhash(HASHTABLE H,int obj,int *addr)  //散列表查找关键字
    {
        *addr = HASH(obj);                      //求散列表地址
        while(H.elem[*addr]!= obj)               //如果不为空则冲突
        {
            *addr = (*addr+1)%m;                //开放定址法的线性探测
            if(H.elem[*addr] == NULLKEY || *addr == HASH(obj))
            {                         //如果循环回到原点
                return UNSUCCESS;         //则说明关键字不存在
            }
        }
        return SUCCESS;
    }
    
    int main()
    {
        HASHTABLE H = {NULL,0}; 
        int key;
        int obj;
        int addr;
        int ret;
        init_hashtable(&H);    //初始化散列表
        int i = 5;
        for(i=0;i<5;i++)
        {
         printf("please enter your key:");
         scanf("%d",&key);
         inserthash(&H,key);    //插入关键字进散列表
         key = 0;
        }
        printf("please enter what number you want:");
        scanf("%d",&obj);
        ret = searchhash(H,obj,&addr);  //散列表查找关键字
        if(ret == 0){
            printf("sorry no obj\n");
        }else{
            printf("yes we find it %d\n",addr);
        }
        return 0;
    }

[Link 1]: http://baike.baidu.com/view/1320746.htm
[Link 2]: http://baike.baidu.com/view/9900.htm
[Link 3]: http://baike.baidu.com/view/131153.htm
[Link 4]: http://baike.baidu.com/view/209670.htm