哈希表-用动态数组实现

原理

哈希表是一种数据结构，用于实现键-值对的存储和检索。其原理基于哈希函数的运算。

  1. 哈希函数：哈希函数是哈希表的核心。它将不同长度的输入数据映射为固定长度的输出，通常称为哈希码或哈希值。哈希函数应具有以下特性：

    • 相同的输入始终产生相同的哈希值。
    • 不同的输入尽可能产生不同的哈希值。
    • 哈希值的计算速度应尽可能快。

  2. 哈希表结构：哈希表通常是一个数组，每个元素称为哈希桶（bucket）。每个桶可以存储一个或多个键-值对。哈希表的大小通常是固定的，但也可以动态调整。

  3. 存储过程：将键通过哈希函数转换为哈希值，然后根据哈希值将键-值对存储到相应的桶中。如果两个不同的键通过哈希函数得到相同的哈希值，就会发生哈希冲突。

  4. 解决冲突：哈希冲突是指两个不同的键映射到了相同的哈希值。常见的解决冲突的方法有：

    • 开放寻址法：当发生冲突时，依次探测下一个空桶，直到找到空桶为止。
    • 链表法：每个桶存储一个链表或其他数据结构，将哈希冲突的键-值对链接在一起。

  5. 检索过程：通过哈希函数计算键的哈希值，然后定位到对应的桶，最终在该桶中进行搜索。如果使用链表法解决冲突，可能需要遍历链表来找到目标键。

哈希表的时间复杂度通常为O(1)，但在发生哈希冲突时，最坏情况下可能退化为O(n)，其中n是哈希表中的元素数量。因此，选择合适的哈希函数和解决冲突的方法对哈希表的性能至关重要。

本文采用的哈希表结构可以动态调整，根据负载因子的值决定是否进行扩容，负载因子是通过哈希表目前存储的元素的个数除以哈希表目前的容量，如果负载因子大于等于0.75，则进行扩容

本来采用的解决冲突的办法使用了拉链法，即把每个键值对当做一个结点，链接到对应哈希数组的下标处

图示

拉链法

代码实现

头文件Hash_map.h提供对外暴露的接口

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
#ifndef HASH_MAP_H
#define HASH_MAP_H


#include <stdint.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#define CAPACITY 8

typedef char* K;
typedef char* V;

typedef struct node_s {
	K key;
	V val;
	struct node_s* next;
} KeyValueNode;

typedef struct {
	KeyValueNode** buckets;   // 此时哈希桶是一个动态数组
	int size;       // 键值对的个数
	int capacity;   // 数组的长度
	uint32_t hash_seed;  // 哈希函数需要的种子值
} HashMap;

// 基础的操作则可以保持一致

// 创建一个固定容量的哈希表
HashMap* create_hashmap();
// 销毁一个哈希表
void destroy_hashmap(HashMap* map);

// 插入一个键值对
V put(HashMap* map, K key, V val);
// 查询一个键值对
V get(HashMap* map, K key);
// 删除某个键值对
bool map_remove(HashMap* map, K key);

#endif // !HASH_MAP_H

源文件Hash_map.c实现细节

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
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
#include "Hash_map.h"
#include <string.h>
#define THRESHOLD 1000
#define UNSUCCESSFUL_ALLOACTION(p,condition,msg)\
do{\
if (p == condition) {\
	printf(msg);\
	exit(-1); \
	}\
}while(0)

/* murmur_hash2 */
static uint32_t hash(const void* key, int len, uint32_t seed) {
    const uint32_t m = 0x5bd1e995;
    const int r = 24;
    uint32_t h = seed ^ len;
    const unsigned char* data = (const unsigned char*)key;

    while (len >= 4) {
        uint32_t k = *(uint32_t*)data;
        k *= m;
        k ^= k >> r;
        k *= m;
        h *= m;
        h ^= k;
        data += 4;
        len -= 4;
    }

    switch (len) {
    case 3: h ^= data[2] << 16;
    case 2: h ^= data[1] << 8;
    case 1: h ^= data[0];
        h *= m;
    };

    h ^= h >> 13;
    h *= m;
    h ^= h >> 15;

    return h;
}

int get_index(HashMap* map,K key) {
    return hash(key, strlen(key), map->hash_seed) % (map->capacity);
}

HashMap* create_hashmap() {
	HashMap* hash = calloc(1, sizeof(HashMap));
	UNSUCCESSFUL_ALLOACTION(hash, NULL, "this memory allocat unsuccessful.");
	hash->capacity = CAPACITY;
	hash->buckets = calloc(CAPACITY , sizeof(KeyValueNode*));
	UNSUCCESSFUL_ALLOACTION(hash->buckets, NULL, "this memory allocat unsuccessful.");
    hash->hash_seed = time(NULL);
	return hash;
}
//
//void rehash(HashMap* map,int old_capacity,KeyValueNode** old_keyvalue,int new_capacity) {
//    //重新hash
//    uint32_t hash_seed = time(NULL);//重新设置种子值
//
//    for (size_t i = 0; i < old_capacity; ++i) {
//        KeyValueNode* keyvalue = old_keyvalue[i];
//        KeyValueNode* pre_keyvalue = NULL;
//        while (keyvalue != NULL) {
//            pre_keyvalue = keyvalue;
//            int new_index = hash(keyvalue->key, strlen(keyvalue->key), hash_seed) % new_capacity;
//            KeyValueNode* new_node = calloc(1, sizeof(KeyValueNode));
//            UNSUCCESSFUL_ALLOACTION(new_node, NULL, "this memory alloact unsuccessful.");
//            new_node->key = keyvalue->key;
//            new_node->val = keyvalue->val;
//
//            if (map->buckets[new_index] == NULL) {
//                map->buckets[new_index] = new_node;
//            }
//            else {
//                new_node->next = map->buckets[new_index]->next;
//                map->buckets[new_index] = new_node;
//            }
//            keyvalue = keyvalue->next;
//        }
//    }
//    map->hash_seed = hash_seed;
//}

static void resize(HashMap* map) {
    //扩容
	int old_capacity = map->capacity;
	int new_capacity = old_capacity > THRESHOLD ? (old_capacity + (old_capacity >> 1)) : (old_capacity << 1);
    KeyValueNode** old_keyvalue = map->buckets;
    map->buckets = calloc(new_capacity, sizeof(KeyValueNode*));
   
    //rehash(map, old_capacity, old_keyvalue, new_capacity);
    //重新hash
    map->hash_seed = time(NULL);//重新设置种子值
    map->capacity = new_capacity;
    for (size_t i = 0; i < old_capacity; ++i) {
        KeyValueNode* keyvalue = old_keyvalue[i];
        KeyValueNode* pre_keyvalue = NULL;
        while (keyvalue != NULL) {
            pre_keyvalue = keyvalue;
            int new_index = hash(keyvalue->key, strlen(keyvalue->key), map->hash_seed) % new_capacity;
            KeyValueNode* new_node = calloc(1, sizeof(KeyValueNode));
            UNSUCCESSFUL_ALLOACTION(new_node, NULL, "this memory alloact unsuccessful.");
            new_node->key = keyvalue->key;
            new_node->val = keyvalue->val;

            if (map->buckets[new_index] == NULL) {
                map->buckets[new_index] = new_node;
            }
            else {
                new_node->next = map->buckets[new_index];
                map->buckets[new_index] = new_node;
            }
            keyvalue = keyvalue->next;
        }
    }
   
    
}



V put(HashMap* map, K key, V val) {
	if (map->size/(float)map->capacity >= 0.75) {
		resize(map);
	}
    //如果原来节点存在
    KeyValueNode* search_node = map->buckets[get_index(map,key)];
    while (search_node != NULL) {
        if (!strcmp(search_node->key, key)) {
            V res_val = search_node->val;
            search_node->val = val;
            return res_val;
        }
        search_node = search_node->next;
    }
   //没退出程序说明原来节点不存在

    KeyValueNode* node = calloc(1, sizeof(KeyValueNode));
    node->key = key;
    node->val = val;

    if (map->buckets[get_index(map, key)] == NULL) {
        map->buckets[get_index(map, key)] = node;
        map->size++;
        return NULL;
    }
    node->next = map->buckets[get_index(map, key)];
    map->buckets[get_index(map, key)] = node;
    map->size++;
    return NULL;
}


V get(HashMap* map, K key) {
    int index = hash(key, strlen(key), map->hash_seed) % (map->capacity);
    KeyValueNode* node = map->buckets[index];
    while (node != NULL) {
        if (!strcmp(node->key , key)) {
            return node->val;
        }
        node = node->next;
    }
    return NULL;
}

bool map_remove(HashMap* map, K key) {
    int index = hash(key, strlen(key), map->hash_seed) % (map->capacity);
    KeyValueNode* search_node = map->buckets[index];
    KeyValueNode* pre_search_node = NULL;
    while (search_node != NULL) {
        if (search_node->key == key) {
            if (pre_search_node == NULL) {//该链表上只挂着一个节点 需要特殊处理
                map->buckets[index] = NULL;
                free(search_node);
                map->size--;
                return;
            }
            pre_search_node->next = search_node->next;
            free(search_node);
            map->size--;
            return true;
        }
        pre_search_node = search_node;
        search_node = search_node->next;
    }
    return false;

}

void destroy_hashmap(HashMap* map) {
    for (size_t i = 0; i < map->capacity; ++i) {
        while (map->buckets[i] != NULL) {
            KeyValueNode* node = map->buckets[i];
            map->buckets[i] = node->next;
            map->size--;
            free(node);
        }
    }
    free(map);
}

测试用例1

用于测试基本功能

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
int test(void) {
    // 创建哈希表
    HashMap* map = create_hashmap();
    if (map == NULL) {
        printf("哈希表创建失败。\n");
        return 1;
    }

    // 插入一些键值对
    put(map, "key1", "value1");  // 首次插入，预期成功
    put(map, "key2", "value2");  // 再插入一个新键值对，预期成功
    V old_value = put(map, "key1", "value3");  // 更新已存在的键值对，预期返回"value1"
    printf("更新'key1'的值时返回的旧值应为'value1'，实际返回: %s\n", old_value);

    // 查询键值对
    V value = get(map, "key1");
    printf("查询'key1'，预期得到'value3'，实际得到：%s\n", value);
    value = get(map, "key2");
    printf("查询'key2'，预期得到'value2'，实际得到：%s\n", value);
    value = get(map, "key3");
    if (value == NULL) {
        printf("如预期，'key3'未找到\n");
    }

    // 删除键值对
    bool deleted = map_remove(map, "key1");  // 删除'key1'，预期删除成功
    if (deleted) {
        printf("'key1'成功删除。\n");
        // 验证删除后，'key1'不应该被找到
        value = get(map, "key1");
        if (value == NULL) {
            printf("删除后，'key1'不再存在，符合预期。\n");
        }
    }
    deleted = map_remove(map, "key3");  // 尝试删除不存在的'key3'，预期删除失败
    if (!deleted) {
        printf("'key3'未找到且未删除，符合预期。\n");
    }

    // 销毁哈希表
    destroy_hashmap(map);

    return 0;
}

测试用例2

用于测试能否扩容成功

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
#define N 100 // 初始容量是8，设置为10足以触发一次扩容

int test2() {
	// 创建哈希表
	HashMap* map = create_hashmap();
	if (map == NULL) {
		printf("哈希表创建失败。\n");
		return 1;
	}

	 //插入多个键值对以触发扩容
	char tmp_key[1024], tmp_val[1024];
	for (int i = 0; i < N; i++) {
		/*
			sprintf是一个将格式化的数据输出到一个字符数组中，并最终保存为字符串的标准库函数
			第一个参数是输出的目的地字符串
			后面的参数则和printf使用方式一样
		*/
		sprintf(tmp_key, "key%d", i);
		sprintf(tmp_val, "value%d", i);

		// 使用 calloc 分配和复制键值对
		K key = calloc(strlen(tmp_key) + 1, sizeof(char));
		V val = calloc(strlen(tmp_val) + 1, sizeof(char));
		strcpy(key, tmp_key);
		strcpy(val, tmp_val);

		put(map, key, val);
		printf("插入 %s: %s\n", key, val);
	}
	/*put(map, "key0", "value0");
	put(map, "key1", "value1");
	put(map, "key2", "value2");
	put(map, "key3", "value3");
	put(map, "key4", "value4");
	put(map, "key5", "value5");
	V res = get(map, "key0");
	V res1 = get(map, "key1");
	V res2 = get(map, "key2");
	V res3 = get(map, "key3");
	V res4 = get(map, "key4");*/
	// 检查扩容前后的数据一致性
	bool flag = true;
	for (int i = 0; i < N; i++) {
		sprintf(tmp_key, "key%d", i);
		V ret_val = get(map, tmp_key);
		sprintf(tmp_val, "value%d", i);
		if (ret_val == NULL || strcmp(ret_val, tmp_val) != 0) {
			printf("错误：数据不一致，键 %s 应有的值为 %s，检索得到的值为 %s\n",
				tmp_key, tmp_val,
				((ret_val != NULL) ? ret_val : "null"));
			flag = false;	// 若数据插入有问题，则修改标志为false
		}
	}

	if (flag) {
		printf("所有数据在扩容后仍正确无误。\n");
	}

	// free所有堆上分配的字符串
	for (int i = 0; i < map->capacity; i++) {
		KeyValueNode* curr = map->buckets[i];
		while (curr != NULL) {
			free(curr->key);   // 释放键字符串
			free(curr->val);   // 释放值字符串
			curr = curr->next; // 移动到下一个节点
		}
	}

	// 销毁哈希表
	destroy_hashmap(map);
	return 0;
}

使用说明

需要在main函数内引入哈希表头文件,便可以使用该哈希表提供的功能

1
#include "Hash_map.h"

测试结果

测试扩容没有问题

测试基本功能没有问题