6.1 哈希表
哈希表(hash table),又称散列表,它通过建立键 key
与值 value
之间的映射,实现高效的元素查询。具体而言,向哈希表中输入一个键 key
,则可以在 \(𝑂(1)\) 时间内获取对应的值 value
。
\(f(key) = value\)
哈希表中进行增删查改的时间复杂度都是 \(𝑂(1)\)
6.1.2 哈希表简单实现
仅用一个数组来实现哈希表
在哈希表中,将数组中的每个空位称为桶(bucket),每个桶可存储一个键值对。因此,查询操作就是找到 key
对应的桶,并在桶中获取 value
通过哈希函数(hash function)实现基于 key
定位对应的桶
哈希函数
将一个较大的输入空间映射到一个较小的输出空间。 什么是哈希函数? (nervos.org) 散列函数 - 维基百科,自由的百科全书 (wikipedia.org)
在哈希表中,输入空间是所有 key
,输出空间是所有桶(数组索引)。换句话说,输入一个 key
,我们可以通过哈希函数得到该 key
对应的键值对在数组中的存储位置。
输入一个 key
,哈希函数的计算过程分为以下两步。
- 通过某种哈希算法
hash()
计算得到哈希值。 - 将哈希值对桶数量(数组长度)
capacity
取模,从而获取该key
对应的数组索引index
。
随后,利用 index
在哈希表中访问对应的桶,从而获取 value
。
设数组长度 capacity = 100
、哈希算法 hash(key) = key
,易得哈希函数为 key % 100
。图 以 key
学号和 value
姓名为例,展示了哈希函数的工作原理。
/* 键值对 int->string */
typedef struct {
int key;
char *val;
} Pair;
/* 基于数组实现的哈希表 */
typedef struct {
Pair *buckets[MAX_SIZE];
} ArrayHashMap;
/* 构造函数 */
ArrayHashMap *newArrayHashMap() {
ArrayHashMap *hmap = malloc(sizeof(ArrayHashMap));
for (int i=0; i < MAX_SIZE; i++) {
hmap->buckets[i] = NULL;
}
return hmap;
}
/* 析构函数 */
void delArrayHashMap(ArrayHashMap *hmap) {
for (int i = 0; i < MAX_SIZE; i++) {
if (hmap->buckets[i] != NULL) {
free(hmap->buckets[i]->val);
free(hmap->buckets[i]);
}
}
free(hmap);
}
/* 添加操作 */
void put(ArrayHashMap *hmap, const int key, const char *val) {
Pair *Pair = malloc(sizeof(Pair));
Pair->key = key;
Pair->val = malloc(strlen(val) + 1);
strcpy(Pair->val, val);
int index = hashFunc(key);
hmap->buckets[index] = Pair;
}
/* 删除操作 */
void removeItem(ArrayHashMap *hmap, const int key) {
int index = hashFunc(key);
free(hmap->buckets[index]->val);
free(hmap->buckets[index]);
hmap->buckets[index] = NULL;
}
/* 获取所有键值对 */
void pairSet(ArrayHashMap *hmap, MapSet *set) {
Pair *entries;
int i = 0, index = 0;
int total = 0;
/* 统计有效键值对数量 */
for (i = 0; i < MAX_SIZE; i++) {
if (hmap->buckets[i] != NULL) {
total++;
}
}
entries = malloc(sizeof(Pair) * total);
for (i = 0; i < MAX_SIZE; i++) {
if (hmap->buckets[i] != NULL) {
entries[index].key = hmap->buckets[i]->key;
entries[index].val = malloc(strlen(hmap->buckets[i]->val) + 1);
strcpy(entries[index].val, hmap->buckets[i]->val);
index++;
}
}
set->set = entries;
set->len = total;
}
/* 获取所有键 */
void keySet(ArrayHashMap *hmap, MapSet *set) {
int *keys;
int i = 0, index = 0;
int total = 0;
/* 统计有效键值对数量 */
for (i = 0; i < MAX_SIZE; i++) {
if (hmap->buckets[i] != NULL) {
total++;
}
}
keys = malloc(total * sizeof(int));
for (i = 0; i < MAX_SIZE; i++) {
if (hmap->buckets[i] != NULL) {
keys[index] = hmap->buckets[i]->key;
index++;
}
}
set->set = keys;
set->len = total;
}
/* 获取所有值 */
void valueSet(ArrayHashMap *hmap, MapSet *set) {
char **vals;
int i = 0, index = 0;
int total = 0;
/* 统计有效键值对数量 */
for (i = 0; i < MAX_SIZE; i++) {
if (hmap->buckets[i] != NULL) {
total++;
}
}
vals = malloc(total * sizeof(char *));
for (i = 0; i < MAX_SIZE; i++) {
if (hmap->buckets[i] != NULL) {
vals[index] = hmap->buckets[i]->val;
index++;
}
}
set->set = vals;
set->len = total;
}
/* 打印哈希表 */
void print(ArrayHashMap *hmap) {
int i;
MapSet set;
pairSet(hmap, &set);
Pair *entries = (Pair *)set.set;
for (i = 0; i < set.len; i++) {
printf("%d -> %s\n", entries[i].key, entries[i].val);
}
free(set.set);
}
6.1.3 哈希冲突与扩容
从本质上看,哈希函数的作用是将所有 key
构成的输入空间映射到数组所有索引构成的输出空间,而输入空间往往远大于输出空间。因此,理论上一定存在“多个输入对应相同输出”的情况。
哈希冲突(hash collision)。
通过扩容哈希表来减少哈希冲突。
负载因子(load factor)是哈希表的一个重要概念,其定义为哈希表的元素数量除以桶数量,用于衡量哈希冲突的严重程度,也常作为哈希表扩容的触发条件。例如在 Java 中,当负载因子超过 0.75 时,系统会将哈希表扩容至原先的 2 倍。