首页 > 代码库 > 哈希表

哈希表

2024-08-23 14:28:47   222人阅读

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。
 
哈希表用来处理key-value的，这个表用来存储key-value（键值对），通过散列函数f(key)可定位key-value在表中存贮的位置，从而更快的访问到key-value。
表中的key-value查找的速度是哈希表性能的一大依据，主要还是散列函数的构造。构造散列函数的方法很多。
不同key值通过f(key)可能得到相同的哈希值，这样两组或多组key-value就出现了冲突，这种现象称为碰撞（英语：Collision）。处理冲突的方法可为开放定址法、再哈希法、链表法、建立一个公共溢出区等。
 
下面是一个哈希表方法访问字符串型key-value：

struct ram_tuple *ram_hash[256];

#define ARRAYSIZE(a) (sizeof(a)/sizeof(a[0]))

static unsigned int hash(const char *s)
{
    unsigned int hash = 0;

    while(*s)
    {
        hash = 31 * hash + *s++;
    }

    return hash;
}
char *_ram_get(const char *name)
{
    unsigned int i;
    struct ram_tuple *t;
    char *value;

    if(name == NULL)
        return NULL;

    i = hash(name) % ARRAYSIZE(ram_hash);

    for(t=ram_hash[i]; t && strcmp(t->name, name); t=t->next);
    value = t ? t->value : NULL;

    return value;
}
void _ram_free(void)
{
    unsigned int i;
    struct ram_tuple *t, *next;

    for(i = 0; i < ARRAYSIZE(ram_hash); i++)
    {
        for(t= ram_hash[i]; t; t=next)
        {   
            next = t->next;
            free(t->name);
            free(t->value);
            free(t);
        }   
        ram_hash[i] = NULL;
    }   
}
int _ram_set(const char *name, const char *value)
{
    unsigned int i;
    struct ram_tuple *t, *u, **prev;

    i = hash(name) % ARRAYSIZE(ram_hash);

    for(prev = &ram_hash[i], t = *prev;        t && strcmp(t->name, name);         prev = &(t->next), t = *prev);

    if( (u = _ram_realloc(t, name, value)) == NULL)
    {
        return -12; /* -ENOMEM*/
    }

    if(t && t == u)
    {
        return 0;
    }

    u->next = ram_hash[i];
    ram_hash[i] = u;

    return 0;
}

 

参考：
百度百科
http://www.cnblogs.com/jiewei915/archive/2010/08/09/1796042.html

哈希表


联系
我们