C语言实现的数据结构之------哈希表_哈希表的c语言实现

1 哈希表原理

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

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

void* list_find_by_key(list,key)
{
    for(p=list;p!=NULL; p=p->next){
        if(p->key == key){
            return p;
        }
        return p;
    }
}
1
2
3
4
5
6
7
8
9

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

void* hash_table_find_by_key(table, key)
{
    void* p = hash(key);
    return p;
}
1
2
3
4
5

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

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

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

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

void* hash_table_find_by_key(table, key)
{
    void* list = hash(key);
    return list_find_by_key(list, key);
}
1
2
3
4
5

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

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

2 纯C实现源码

实际工作中，大多数情况下，关键字都是字符串的形式，而大多数教科书上却使用整数关键字来举例，这非常脱离实际。为此，本人决定使用纯C语言开发一个哈希表结构，供大家参考。主要特点：

• 基于接口开发，对外彻底隐藏实现细节
• 具有自动释放客户结构内存的回调功能
• 采用经典的Times33哈希算法
• 采用纯C开发，可供C和C++客户使用

HashTable.h 头文件

#pragma once
typedef struct HashTable HashTable;

#ifdef __cplusplus
extern "C" {
#endif

    /* new an instance of HashTable */
    HashTable* hash_table_new();

    /*
    delete an instance of HashTable,
    all values are removed auotmatically.
    */
    void hash_table_delete(HashTable* ht);

    /*
    add or update a value to ht, 
    free_value(if not NULL) is called automatically when the value is removed.
    return 0 if success, -1 if error occurred.
    */
    #define hash_table_put(ht,key,value) hash_table_put2(ht,key,value,NULL);
    int hash_table_put2(HashTable* ht, char* key, void* value, void(*free_value)(void*));

    /* get a value indexed by key, return NULL if not found. */
    void* hash_table_get(HashTable* ht, char* key);

    /* remove a value indexed by key */
    void hash_table_rm(HashTable* ht, char* key);

#ifdef __cplusplus
}
#endif
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

HashTable.c 实现文件

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

#define TABLE_SIZE (1024*1024)

/* element of the hash table's chain list */
struct kv
{
    struct kv* next;
    char* key;
    void* value;
    void(*free_value)(void*);
};

/* HashTable */
struct HashTable
{
    struct kv ** table;
};

/* constructor of struct kv */
static void init_kv(struct kv* kv)
{
    kv->next = NULL;
    kv->key = NULL;
    kv->value = NULL;
    kv->free_value = NULL;
}
/* destructor of struct kv */
static void free_kv(struct kv* kv)
{
    if (kv) {
        if (kv->free_value) {
            kv->free_value(kv->value);
        }
        free(kv->key);
        kv->key = NULL;
        free(kv);
    }
}
/* the classic Times33 hash function */
static unsigned int hash_33(char* key)
{
    unsigned int hash = 0;
    while (*key) {
        hash = (hash << 5) + hash + *key++;
    }
    return hash;
}

/* new a HashTable instance */
HashTable* hash_table_new()
{
    HashTable* ht = malloc(sizeof(HashTable));
    if (NULL == ht) {
        hash_table_delete(ht);
        return NULL;
    }
    ht->table = malloc(sizeof(struct kv*) * TABLE_SIZE);
    if (NULL == ht->table) {
        hash_table_delete(ht);
        return NULL;
    }
    memset(ht->table, 0, sizeof(struct kv*) * TABLE_SIZE);

    return ht;
}
/* delete a HashTable instance */
void hash_table_delete(HashTable* ht)
{
    if (ht) {
        if (ht->table) {
            int i = 0;
            for (i = 0; i<TABLE_SIZE; i++) {
                struct kv* p = ht->table[i];
                struct kv* q = NULL;
                while (p) {
                    q = p->next;
                    free_kv(p);
                    p = q;
                }
            }
            free(ht->table);
            ht->table = NULL;
        }
        free(ht);
    }
}

/* insert or update a value indexed by key */
int hash_table_put2(HashTable* ht, char* key, void* value, void(*free_value)(void*))
{
    int i = hash_33(key) % TABLE_SIZE;
    struct kv* p = ht->table[i];
    struct kv* prep = p;

    while (p) { /* if key is already stroed, update its value */
        if (strcmp(p->key, key) == 0) {
            if (p->free_value) {
                p->free_value(p->value);
            }
            p->value = value;
            p->free_value = free_value;
            break;
        }
        prep = p;
        p = p->next;
    }

    if (p == NULL) {/* if key has not been stored, then add it */
        char* kstr = malloc(strlen(key) + 1);
        if (kstr == NULL) {
            return -1;
        }
        struct kv * kv = malloc(sizeof(struct kv));
        if (NULL == kv) {
            free(kstr);
            kstr = NULL;
            return -1;
        }
        init_kv(kv);
        kv->next = NULL;
        strcpy(kstr, key);
        kv->key = kstr;
        kv->value = value;
        kv->free_value = free_value;

        if (prep == NULL) {
            ht->table[i] = kv;
        }
        else {
            prep->next = kv;
        }
    }
    return 0;
}

/* get a value indexed by key */
void* hash_table_get(HashTable* ht, char* key)
{
    int i = hash_33(key) % TABLE_SIZE;
    struct kv* p = ht->table[i];
    while (p) {
        if (strcmp(key, p->key) == 0) {
            return p->value;
        }
        p = p->next;
    }
    return NULL;
}

/* remove a value indexed by key */
void hash_table_rm(HashTable* ht, char* key)
{
    int i = hash_33(key) % TABLE_SIZE;

    struct kv* p = ht->table[i];
    struct kv* prep = p;
    while (p) {
        if (strcmp(key, p->key) == 0) {
            free_kv(p);
            if (p == prep) {
                ht->table[i] = NULL;
            }
            else {
                prep->next = p->next;
            }
        }
        prep = p;
        p = p->next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174

3 测试程序

下面是测试程序源码，基于C++。

测试程序test.cpp

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

#include "HashTable.h"

// 要放入哈希表中的结构体
struct Student
{
    int age;
    float score;
    char name[32];
    char data[1024 * 1024* 10];
};

// 结构体内存释放函数
static void free_student(void* stu)
{
    free(stu);
}

// 显示学生信息的函数
static void show_student(struct Student* p)
{
    printf("姓名:%s, 年龄:%d, 学分:%.2f\n", p->name, p->age, p->score);
}

int main()
{
    // 新建一个HashTable实例
    HashTable* ht = hash_table_new();
    if (NULL == ht) {
        return -1;
    }

    // 向哈希表中加入多个学生结构体
    for (int i = 0; i < 100; i++) {
        struct Student * stu = (struct Student*)malloc(sizeof(struct Student));
        stu->age = 18 + rand()%5;
        stu->score = 50.0f + rand() % 100;
        sprintf(stu->name, "同学%d", i);
        hash_table_put2(ht, stu->name, stu, free_student);
    }

    // 根据学生姓名查找学生结构
    for (int i = 0; i < 100; i++) {
        char name[32];
        sprintf(name, "同学%d", i);
        struct Student * stu = (struct Student*)hash_table_get(ht, name);
        show_student(stu);
    }

    // 销毁哈希表实例
    hash_table_delete(ht);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55