数据结构(4)：哈希表

前言

有时也翻译为散列表。之前介绍原子表的时候提到过这个数据结构。

使用线性表逐个查找时，平均查找复杂度为 O(n)。在不考虑计算哈希值本身开销的情况下，一个工作良好的哈希表平均查找复杂度为 O(1)。这也是我们使用哈希表的主要原因。

哈希表有很多种实现，这里只介绍我知道的几种常见实现。

实现

链地址法

使用桶数组 + 链表的方式进行组织，如下：

struct Entry *buckets[2048];

每个 Entry 就是一个键值记录或者其它的东西，如下：

struct Entry {
    const void *key;
    void *value;
    struct Entry *next;
};

在内存中的布局示意图如下：

┌───────┐
│ [0] ──────> Entry -> Entry -> ...
│ [1] ──────> Entry -> ...
│ [2] ──────> NULL
│ [3] ──────> Entry -> Entry -> ...
| ...
| [n] ──────> Entry -> Entry -> ...
└───────┘

每当要插入或者寻找一个键值对时，会对输入的 key 计算哈希值，然后对哈希表的 buckets 长度取模，如下：

siza_t h = hash(key) % NELEMS(buckets);

当然，如果能确保 buckets 的长度为 2^N，那么也能用下面的位操作方法：

siza_t h = hash(key) & ( NELEMS(buckets) - 1 );

然后遍历一次对 buckets[h] 链表各个元素的 key 进行对比，找到目标。如果遍历完了也没有找到，返回错误值或者创建新的元素插入到 buckets[h]。

hash(key) 的实现

这个要根据具体 key 的数据类型来决定。对于一些常见的数据类型，前人已经总结了不少计算哈希值的方法。

这里以 key 的类型为一个显式记录长度的字符串为例，演示一种古老但是简单的方法，如下：

size_t hash_string(const void *key) {
    const struct string *str = (const struct string *)key;
    size_t i = 0, h = 0;
    for( i = 0; i < str->len ; i++ ) 
        h = (h << 1) + scatter[(uint8_t)str->buffer[i]];
    return h;
}

这里 scatter 为一个数组，具有 256 个非负整数随机值元素，比如：

static unsigned long scatter[256] = {
    // 这里省略 256 个随机值
    ...
};

实验表明，这种简单的方法有助于生成分布更加均匀的哈希值。

开放寻址

这个我暂时还没了解，先按下不表。

挖坑

结语

练习 LeetCode Hot 100 时一直用 std::unordered_set 和 std::unordered_map 之类的 STL，一直不明白为什么能根据 key 去查找信息。虽然我写出的这个实现相比于 STL 肯定过于简陋了，很可能不是一个算法，不过算是加深了我对这个数据结构的理解。

参考资料

• 《C Interfaces and Implementations》第三章

---