• 哈希表的链地址法实现

    用C语言实现一个哈希表
    服务器君一共花费 27.035 ms 进行了 2 次数据库查询,努力地为您提供了这个页面。
    广告很萌的

    哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。哈希表在像Java、C#等语言中是与生俱来的。可是在C的世界中,似乎只有自己动手,丰衣足食了。

    哈希表实现中需要注意的问题。

    1. 哈希函数

    也叫散列函数,即:根据key,计算出key对应记录的储存位置:position = f(key)

    散列函数满足以下的条件:

    1. 对输入值运算,得到一个固定长度的摘要(Hash value);
    2. 不同的输入值可能对应同样的输出值;

    以下的函数都可以认为是一个散列函数:

    • f(x) = x mod 16;
    • f(x) = (x2 + 10) * x; 
    • f(x) = (x | 0×0000FFFF) XOR (x >> 16); 

    不过,仅仅满足上面这两条的函数,作为散列函数,还有不足的地方。我们还希望散列函数满足下面几点:

    1. 散列函数的输出值尽量接近均匀分布;
    2. x的微小变化可以使f(x)发生非常大的变化,即所谓“雪崩效应”(Avalanche effect);

    上面两点用数学语言表示,就是:

    1. 输出值y的分布函数F(y)=y/m, m为散列函数的最大值。或记为y~U[0, m]
    2. |df(x)/dx| >> 1;
    • 从上面两点,大家看看,前面举例的三个散列函数,哪个更好呢?对了,是第三个:f(x) = (x | 0×0000FFFF) XOR (x >> 16);

    它很完美地满足“好的散列函数”的两个附加条件。

    2、哈希冲突(Hash collision)

    也就是两个不同输入产生了相同输出值的情况。首先,哈希冲突是无法避免的,因此,哈希算法的选择直接决定了哈希冲突发送的概率;同时必须要对哈希冲突进行处理,方法主要有以下几种:

    1. 链地址法。即对Hash表中每个Hash值建立一个冲突表,即将冲突的几个记录以表的形式存储在其中。具体可以参照 散列冲突处理:链地址法 。
    2. 开放地址法。具体可以参照 散列冲突处理:开放定址法 。
    //#include "stdafx.h"
    #include "string.h"
    #include "stdio.h"
    #include "stdlib.h"
    
    typedef struct _node
    {
        char *name;
        char *desc;
        struct _node *next;
    } node;
    
    #define HASHSIZE 101
    static node* hashtab[HASHSIZE];
    
    void inithashtab()
    {
        int i;
        for(i=0; i < HASHSIZE; i++)
            hashtab[i]=NULL;
    }
    
    unsigned int hash(char *s)
    {
        unsigned int h=0;
        for(; *s; s++)
            h=*s+h*31;
        return h%HASHSIZE;
    }
    
    node* lookup(char *n)
    {
        unsigned int hi=hash(n);
        node* np=hashtab[hi];
        for(; np!=NULL; np=np->next)
        {
            if(!strcmp(np->name,n))
                return np;
        }
    
        return NULL;
    }
    
    char* m_strdup(char *o)
    {
        int l=strlen(o)+1;
        char *ns=(char*)malloc(l*sizeof(char));
        strcpy(ns,o);
        if(ns==NULL)
            return NULL;
        else
            return ns;
    }
    
    char* get(char* name)
    {
        node* n=lookup(name);
        if(n==NULL)
            return NULL;
        else
            return n->desc;
    }
    
    int install(char* name,char* desc)
    {
        unsigned int hi;
        node* np;
        if((np=lookup(name))==NULL)
        {
            hi=hash(name);
            np=(node*)malloc(sizeof(node));
            if(np==NULL)
                return 0;
            np->name=m_strdup(name);
            if(np->name==NULL) return 0;
            np->next=hashtab[hi];
            hashtab[hi]=np;
        }
        else
            free(np->desc);
        np->desc=m_strdup(desc);
        if(np->desc==NULL) return 0;
    
        return 1;
    }
    
    /* A pretty useless but good debugging function,
    which simply displays the hashtable in (key.value) pairs
    */
    void displaytable()
    {
        int i;
        node *t;
        for(i=0; i < HASHSIZE; i++)
        {
            if(hashtab[i]==NULL)
                printf("()");
            else
            {
                t=hashtab[i];
                printf("(");
                for(; t!=NULL; t=t->next)
                    printf("(%s.%s) ",t->name,t->desc);
                printf(".)");
            }
        }
    }
    
    void cleanup()
    {
        int i;
        node *np,*t;
        for(i=0; i < HASHSIZE; i++)
        {
            if(hashtab[i]!=NULL)
            {
                np=hashtab[i];
                while(np!=NULL)
                {
                    t=np->next;
                    free(np->name);
                    free(np->desc);
                    free(np);
                    np=t;
                }
            }
        }
    }
    
    main()
    {
        int i;
        char* names[]= {"name","address","phone","k101","k110"};
        char* descs[]= {"Sourav","Sinagor","26300788","Value1","Value2"};
    
        inithashtab();
        for(i=0; i < 5; i++)
            install(names[i],descs[i]);
    
        printf("Done");
        printf("If we didnt do anything wrong..""we should see %s\n",get("k110"));
    
        install("phone","9433120451");
    
        printf("Again if we go right, we have %s and %s",get("k101"),get("phone"));
    
        /*displaytable();*/
        cleanup();
        return 0;
    }
    
更多 推荐条目

Welcome to NowaMagic Academy!

现代魔法 推荐于 2013-02-27 10:23   

本章最新发布
随机专题
  1. [软件工程与项目管理] 浏览器的CSS解析 7 个条目
  2. [移动开发] Android里的ContentValues 2 个条目
  3. [Python程序设计] 写几个简单的Tornado程序吧 5 个条目
  4. [Python程序设计] Django Web环境配置 2 个条目
  5. [搜索引擎优化] 百度搜索引擎优化指南 3 个条目
  6. [移动开发] Android Studio的使用技巧 4 个条目
  7. [JavaScript程序设计] Web实时通信技术名词解析 5 个条目
  8. [PHP程序设计] httpd.conf设置相关 3 个条目
  9. [移动开发] Layout_weight属性解析 5 个条目
  10. [JavaScript程序设计] jQuery与表单操作 2 个条目
  11. [数据结构] 散列表(哈希表) 13 个条目
  12. [智力开发与知识管理] 信息的类型与结构 9 个条目
窗口 -- [八点]