Hash魔法:哈希表的原理与实现

用C实现一个Hash表
服务器君一共花费了278.133 ms进行了7次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

一列键值对数据,存储在一个table中,如何通过数据的关键字快速查找相应值呢?不要告诉我一个个拿出来比较key啊,呵呵。 

大家都知道,在所有的线性数据结构中,数组的定位速度最快,因为它可通过数组下标直接定位到相应的数组空间,就不需要一个个查找。而哈希表就是利用数组这个能够快速定位数据的结构解决以上的问题的。 

具体如何做呢?大家是否有注意到前面说的话:“数组可以通过下标直接定位到相应的空间”,对就是这句,哈希表的做法其实很简单,就是把Key通过一个固定的算法函数,既所谓的哈希函数转换成一个整型数字,然后就将该数字对数组长度进行取余,取余结果就当作数组的下标,将value存储在以该数字为下标的数组空间里,而当使用哈希表进行查询的时候,就是再次使用哈希函数将key转换为对应的数组下标,并定位到该空间获取value,如此一来,就可以充分利用到数组的定位性能进行数据定位。

不知道说到这里,一些不了解的朋友是否大概了解了哈希表的原理,其实就是通过空间换取时间的做法。到这里,可能有的朋友就会问,哈希函数对key进行转换,取余的值一定是唯一的吗?这个当然不能保证,主要是由于hashcode会对数组长度进行取余,因此其结果由于数组长度的限制必然会出现重复,所以就会有“冲突”这一问题,至于解决冲突的办法其实有很多种,比如重复散列的方式,大概就是定位的空间已经存在value且key不同的话就重新进行哈希加一并求模数组元素个数,既 (h(k)+i) mod S , i=1,2,3…… ,直到找到空间为止。还有其他的方式大家如果有兴趣的话可以自己找找资料看看。 

Hash表这种数据结构在java中是原生的一个集合对象,在实际中用途极广,主要有这么几个特点:

  1. 访问速度快
  2. 大小不受限制
  3. 按键进行索引,没有重复对象
  4. 用字符串(id:string)检索对象(object)

今天整理以前写的一些算法,翻出来一个hash表的实现,就贴出来,自己也温习温习。先看看头文件,也就是数据结构的定义,相当于java中的接口的概念:

#include <stdio.h>

#define    HASHSIZE 256

//定义hash表中的节点的类型
struct    nlist{
    struct    nlist    *next;
    char    *name;
    char    *defn;
};

//定义接口中的函数,也就是对外来说,这个程序可以做什么
unsigned    hash(char *s);//计算一个串的hash值
struct    nlist    *lookup(char *s);//查找一个value,根据key
struct    nlist    *install(char *name,char *defn);//插入一个key=value的对象

然后是具体实现:

#include <string.h>
#include "list.h"

static struct nlist *hashtab[HASHSIZE];

unsigned    hash(char *s)	//取得hash值
{
    unsigned    hashval;

    for(hashval = 0; *s != '\0';s++)
            hashval = *s + 31 * hashval;
    return hashval % HASHSIZE;
}

struct    nlist    *lookup(char *s)
{
    struct    nlist    *np;

    for(np = hashtab[hash(s)]; np != NULL; np = np->next)
        if(strcmp(s,np->name) == 0)
            return np;
    return NULL;
}

struct    nlist    *install(char *name,char *defn)
{
    struct    nlist    *np;
    unsigned    hashval;

    if((np = lookup(name)) == NULL){
        np = (struct nlist *)malloc(sizeof(struct nlist));
        if(np == NULL || (np->name = strdup(name)) == NULL)
                return NULL;
        hashval = hash(name);
        np->next= hashtab[hashval];
        hashtab[hashval] = np;
    }else
        free((void *)np->defn);
    if((np->defn = strdup(defn)) == NULL)
            return NULL;
    return np;
}

很简单,只有两个外部接口,

  1. install(key, value),用来插入一个新的节点
  2. lookup(key),根据一个键来进行搜索,并返回节点

代码很简单,主要用到的hash算法跟java中的String的hashcode()方法中用到的算法一样,使用:

unsigned hash(char *s)
{
    unsigned    hashval;

    for(hashval = 0; *s != '\0';s++)
            hashval = *s + 31 * hashval;
    return hashval % HASHSIZE;
}

这里的31并非随意,乃是一个经验值,选取它的目的在于减少冲突,当然,hash冲突这个问题是不能根本避免的。这里只是一个人们在测试中发现的可以相对减少hash冲突的一个数字,可能以后会发现更好的数值来。

延伸阅读

此文章所在专题列表如下:

  1. Hash魔法:哈希表的原理与实现
  2. Hash魔法:一致性 hash 算法
  3. Hash魔法:分布式哈希算法
  4. Hash魔法:哈希表的工作原理与常用操作

本文地址:http://www.nowamagic.net/librarys/veda/detail/1335,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/1335

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《重构:改善既有代码的设计》 福勒(Martin Fowler) (作者), 熊节 (译者)

《重构:改善既有代码的设计》清晰地揭示了重构的过程,解释了重构的原理和最佳实践方式,并给出了何时以及何地应该开始挖掘代码以求改善。书中给出了70多个可行的重构,每个重构都介绍了一种经过验证的代码变换手法的动机和技术。《重构:改善既有代码的设计》提出的重构准则将帮助你一次一小步地修改你的代码,从而减少了开发过程中的风险。

更多计算机宝库...