Hash-Table-P03.rst

Part 03 - 哈希函数

目录

• 3.1 - 算法
• 3.2 - 实现
• 3.3 - 不可控数据

在本节中， 我们将编写我们的哈希函数。

我们选择的哈希函数应该：

• 将一个字符串作为输入并返回一个介于 0 和 m 之间的数字， 即我们想要的桶数组长度。
• 为一组平均输入返回桶索引的均匀分布。 如果我们的哈希函数分布不均， 它会在某些桶中放入比其他桶更多的条目。 这将导致更高的碰撞率。 冲突会降低我们哈希表的效率。

3.1 - 算法

我们将使用一个通用的字符串散列函数， 用伪代码表示如下。

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

这个哈希函数有两个步骤：

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

变量 a 应该是一个大于字母表大小的素数。 我们正在散列 ASCII 字符串， 它的字母大小为 128， 所以我们应该选择一个比这更大的素数。

char_code 是一个函数， 它返回一个表示字符的整数。 为此我们将使用 ASCII 字符代码。

让我们试试哈希函数：

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

3.2 - 实现

// 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;
}

3.3 - 不可控数据

理想的散列函数将始终返回均匀分布。 但是对于任何散列函数， 都有一组 "不可控" 输入， 它们都散列到相同的值。 要找到这组输入， 请通过该函数运行大量输入。 散列到特定桶的所有输入形成不可控数据集。

不可控输入集的存在意味着所有输入都没有完美的哈希函数。 我们能做的最好的事情就是创建一个对预期数据集表现良好的函数。

不可控输入也带来了安全问题。 如果某个恶意用户向哈希表提供了一组冲突的键， 那么搜索这些键将花费比正常时间 (O(1)) 更长的时间 (O(n))。 这可以用作针对以哈希表为基础的系统的拒绝服务攻击， 例如 DNS 和某些 Web 服务。

下一节： 处理碰撞