乐趣区

[译]C语言实现一个简易的Hash table(3)

上一章,我们讲了 hash 表的数据结构,并简单实现了 hash 表的初始化与删除操作,这一章我们会讲解 Hash 函数和实现算法,并手动实现一个 Hash 函数。
Hash 函数
本教程中我们实现的 Hash 函数将会实现如下操作:

输入一个字符串,然后返回一个 0 到 m(Hash 表的大小) 的数字
为一组平常的输入返回均匀的 bucket 索引。如果 Hash 函数不是均匀分布的,就会将多个记录插入到相同的 bucket 中,这就回提高冲突的几率,而这个冲突就会影响到我们的 Hash 表的效率。

Hash 算法
我们将会设计一个普通的字符串 Hash 函数,在伪代码中表示如下:
function hash(string, a, num_buckets):
hash = 0
string_len = length(string)
for i = 0, 1, …, string_len:
hash += (a ** (string_len – (i+1))) * char_code(string[i])
hash = hash % num_buckets
return hash
这个 Hash 函数主要分为两步:

将字符串转为大整型
通过取余数 mod m 将整数的大小减小到固定范围

变量 a 是一个素数,并且要大于英文字母,我们正在散列 ASCII 字符串,其字母大小为 128,因此我们应该选择大于此的素数。
char_code 这个函数会返回字母对应的整数,使用的是 ASCII 中的字母。
如下使用这个 Hash 函数:
hash(“cat”, 151, 53)

// 函数拆解
hash = (151**2 * 99 + 151**1 * 97 + 151**0 * 116) % 53
hash = (2257299 + 14647 + 116) % 53
hash = (2272062) % 53
hash = 5
如果改变 a 我们会得到不同的结果:
hash(“cat”, 163, 53) = 3
代码实现
// hash_table.c
static int ht_hash(const char* s, const int a, const int m) {
long hash = 0;
const int len_s = strlen(s);
for (int i = 0; i < len_s; i++) {
hash += (long)pow(a, len_s – (i+1)) * s[i];
hash = hash % m;
}
return (int)hash;
}
什么是冲突?
理想中的散列函数返回的结果都是均匀分布的,但是,对于任意一个散列函数,总会有一些输入经过散列后,得到相同的值。如果要找到这组输入,我们就需要测试大量的输入数据。
因为上面提到的有不好的输入存在,意味着所有输入都没有完美的散列函数。所以在设计散列函数时,针对预期输入,我们的散列函数需要表现最好。
不好的输入也存在安全问题,如果某个恶意用户向哈希表提供了一组冲突密钥,那么搜索这些密钥将比正常情况(O(1))花费更长时间(O(n))。这可以用作针对以哈希表为基础的系统(例如 DNS 和某些 Web 服务)的拒绝服务攻击。
上一章:Hash table 数据结构下一章:冲突处理

退出移动版