C语言实现简单的哈希表

这是一个简单的哈希表的实现，用c语言做的。

哈希表原理

这里不讲高深理论，只说直观感受。哈希表的目的就是为了根据数据的部分内容（关键字），直接计算出存放完整数据的内存地址。

试想一下，如果从链表中根据关键字查找一个元素，那么就需要遍历才能得到这个元素的内存地址，如果链表长度很大，查找就需要更多的时间.

void* list_find_by_key(list,key)
{
    for(p=list;p!=NULL; p=p->next){
        if(p->key == key){
            return p;
        }
        return p;
    }
}

为了解决根据关键字快速找到元素的存放地址，哈希表应运而生。它通过某种算法（哈希函数）直接根据关键字计算出元素的存放地址，由于无需遍历，所以效率很高。

void* hash_table_find_by_key(table, key)
{
    void* p = hash(key);
    return p;
}

当然，上面的伪代码忽略了一个重要的事实：那就是不同的关键字可能产生出同样的hash值。

hash("张三") = 23;
hash("李四") = 30;
hash("王五") = 23;

这种情况称为“冲突”，为了解决这个问题，有两种方法：一是链式扩展；二是开放寻址。这里只讲第一种：链式扩展。

也就是把具有相同hash值的元素放到一起，形成一个链表。这样在插入和寻找数据的时候就需要进一步判断。

void* hash_table_find_by_key(table, key)
{
    void* list = hash(key);
    return list_find_by_key(list, key);
}

需要注意的是，只要hash函数合适，这里的链表通常都长度不大，所以查找效率依然很高。

下图是一个哈希表运行时内存布局：

C语言实现简单的哈希表

先说一下原理。
先是有一个bucket数组，也就是所谓的桶。

哈希表的特点就是数据与其在表中的位置存在相关性，也就是有关系的，通过数据应该可以计算出其位置。

这个哈希表是用于存储一些键值对(key -- value)关系的数据，其key也就是其在表中的索引，value是附带的数据。

通过散列算法，将字符串的key映射到某个桶中，这个算法是确定的，也就是说一个key必然对应一个bucket。

然后是碰撞问题，也就是说多个key对应一个索引值。举个例子：有三个key:key1,key3,key5通过散列算法keyToIndex得到的索引值都为2，也就是这三个key产生了碰撞，对于碰撞的处理，采取的是用链表连接起来，而没有进行再散列。

C语言实现简单的哈希表

包含的头文件

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define BUCKETCOUNT 16

哈希表和节点数据结构的定义

struct hashEntry
{
    const char* key;
    char* value;
    struct hashEntry* next;
};

typedef struct hashEntry entry;

struct hashTable
{
    entry bucket[BUCKETCOUNT];  //先默认定义16个桶
};

typedef struct hashTable table;

初始化和释放哈希表

//初始化哈希表
void initHashTable(table* t)
{
    int i;
    if (t == NULL)return;

    for (i = 0; i < BUCKETCOUNT; ++i) {
        t->bucket[i].key = NULL;
        t->bucket[i].value = NULL;
        t->bucket[i].next = NULL;
    }
}

//释放哈希表
void freeHashTable(table* t)
{
    int i;
    entry* e,*ep;
    if (t == NULL)return;
    for (i = 0; i<BUCKETCOUNT; ++i) {
        e = &(t->bucket[i]);
        while (e->next != NULL) {
            ep = e->next;
            e->next = ep->next;
            free(ep->key);
            free(ep->value);
            free(ep);
        }
    }
}

哈希散列算法

//哈希散列方法函数
int keyToIndex(const char* key)
{
    int index , len , i;
    if (key == NULL)return -1;

    len = strlen(key);
    index = (int)key[0];
    for (i = 1; i<len; ++i) {
        index *= 1103515245 + (int)key[i];
    }
    index >>= 27;
    index &= (BUCKETCOUNT - 1);
    return index;
}

辅助函数strDup

这是比较多余的做法，因为C标准库中string.h中有一系列这样的函数。

//在堆上分配足以保存str的内存
//并拷贝str内容到新分配位置
char* strDup(const char* str)
{
    int len;
    char* ret;
    if (str == NULL)return NULL;

    len = strlen(str);
    ret = (char*)malloc(len + 1);
    if (ret != NULL) {
        memcpy(ret , str , len);
        ret[len] = '

哈希表原理

相关推荐