第5章：散列（Hashing）

一、导读

1.1 本章学习目标

第5章介绍散列表——一种能在平均 O(1) 时间内完成查找、插入和删除操作的数据结构。散列表是实际应用中最常用的数据结构之一，从编译器的符号表到数据库的索引，从缓存系统到集合的实现，散列无处不在。

本章的核心学习目标包括：

理解散列的基本思想：如何通过散列函数将键映射到数组位置？
掌握散列函数的设计原则：什么样的散列函数是"好"的？
学会处理冲突的两种方法：链地址法和开放寻址法各有什么优缺点？
理解装载因子的影响：什么时候需要重新散列？
了解散列的实际应用：集合、字典、缓存、布隆过滤器

1.2 为什么第五章如此重要

散列表是计算机科学中最重要的数据结构之一。它的平均 O(1) 查找性能使其成为需要快速查找的场景的首选。C++ 的 unordered_map、Python 的 dict、Java 的 HashMap 底层都使用散列表。

理解散列的原理对于解决实际问题至关重要：如何选择合适的散列函数？如何处理冲突？何时需要扩容？这些问题的答案直接影响程序的性能。

1.3 核心问题引导

散列函数如何将任意大小的键映射到固定范围的索引？

为什么"除留余数法"中表的大小通常选择素数？

链地址法和开放寻址法在性能和内存使用上有什么区别？

什么是"聚集"现象？如何避免？

为什么装载因子达到某个阈值时需要重新散列？

布隆过滤器为什么能节省空间？它的假阳性是什么意思？

二、核心概念详解

5.1 散列的基本思想

散列表的核心思想是：通过一个散列函数 h(key)，将键 key 映射到数组的一个位置（桶），然后在该位置存储对应的值。理想情况下，不同的键映射到不同的位置，查找只需 O(1)。

键:     "apple"  "banana"  "cherry"  "date"
         ↓         ↓         ↓        ↓
h(key):  3         7         1        9
         ↓         ↓         ↓        ↓
数组:   [0][1][2][3][4][5][6][7][8][9]
        [ ][c][ ][a][ ][ ][ ][b][ ][d]

5.2 散列函数

5.2.1 简单散列函数

// 除留余数法：h(key) = key mod TableSize
// TableSize 通常选择素数，避免键的规律性导致聚集
int hash1(int key, int tableSize) {
    return key % tableSize;
}

// 乘法散列：h(key) = floor(m * (key * A mod 1))
// A 通常取 (√5 - 1) / 2 ≈ 0.6180339887
int hash2(int key, int m) {
    double A = 0.6180339887;
    return (int)(m * (key * A - (int)(key * A)));
}

// 字符串散列函数
unsigned int hashString(const char *key, int tableSize) {
    unsigned int hash = 0;
    while (*key)
        hash = hash * 31 + (unsigned char)(*key++);
    return hash % tableSize;
}
// 乘以31的好处：
// 1. 31是素数，分布均匀
// 2. 31 = 32 - 1，可以用位移优化：hash * 31 = (hash << 5) - hash
// 3. Java的String.hashCode()就使用这种方法

5.3 冲突解决

5.3.1 链地址法（Separate Chaining）

每个桶维护一个链表，所有散列到同一位置的元素都在这个链表中。

#define TABLE_SIZE 101

typedef struct ListNode {
    int key;
    int value;
    struct ListNode *next;
} ListNode;

typedef struct HashTable {
    ListNode *lists[TABLE_SIZE];
    int size;
} HashTable;

HashTable *createTable() {
    HashTable *H = (HashTable *)malloc(sizeof(HashTable));
    H->size = 0;
    for (int i = 0; i < TABLE_SIZE; i++)
        H->lists[i] = NULL;
    return H;
}

int hash(int key) {
    return key % TABLE_SIZE;
}

// 查找 - 平均O(1)，最坏O(n)
ListNode *find(HashTable *H, int key) {
    int idx = hash(key);
    ListNode *pos = H->lists[idx];
    while (pos != NULL && pos->key != key)
        pos = pos->next;
    return pos;
}

// 插入 - 平均O(1)
void insert(HashTable *H, int key, int value) {
    int idx = hash(key);
    // 检查是否已存在
    ListNode *pos = H->lists[idx];
    while (pos != NULL) {
        if (pos->key == key) {
            pos->value = value;  // 更新
            return;
        }
        pos = pos->next;
    }
    // 插入到链表头部
    ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));
    newNode->key = key;
    newNode->value = value;
    newNode->next = H->lists[idx];
    H->lists[idx] = newNode;
    H->size++;
}

// 删除 - 平均O(1)
void delete(HashTable *H, int key) {
    int idx = hash(key);
    ListNode *curr = H->lists[idx];
    ListNode *prev = NULL;
    while (curr != NULL) {
        if (curr->key == key) {
            if (prev) prev->next = curr->next;
            else H->lists[idx] = curr->next;
            free(curr);
            H->size--;
            return;
        }
        prev = curr;
        curr = curr->next;
    }
}

链地址法的分析：

装载因子 λ = n / TableSize（n为元素个数）
查找 unsuccessful 的平均比较次数 ≈ λ
查找 successful 的平均比较次数 ≈ 1 + λ/2
空间复杂度：O(n + TableSize)

5.3.2 开放寻址法（Open Addressing）

所有元素都存储在散列表数组中。发生冲突时，按照某种探测序列寻找下一个空位。

#define OPEN_TABLE_SIZE 101
#define EMPTY 0
#define OCCUPIED 1
#define DELETED 2

typedef struct OpenEntry {
    int key;
    int value;
    int state;  // EMPTY, OCCUPIED, DELETED
} OpenEntry;

typedef struct OpenHashTable {
    OpenEntry entries[OPEN_TABLE_SIZE];
    int size;
} OpenHashTable;

void initOpen(OpenHashTable *H) {
    H->size = 0;
    for (int i = 0; i < OPEN_TABLE_SIZE; i++)
        H->entries[i].state = EMPTY;
}

// 线性探测
int hashOpen(OpenHashTable *H, int key) {
    int idx = key % OPEN_TABLE_SIZE;
    while (H->entries[idx].state == OCCUPIED && 
           H->entries[idx].key != key) {
        idx = (idx + 1) % OPEN_TABLE_SIZE;
    }
    return idx;
}

// 插入
void insertOpen(OpenHashTable *H, int key, int value) {
    int idx = hashOpen(H, key);
    if (H->entries[idx].state == OCCUPIED) {
        H->entries[idx].value = value;  // 更新
    } else {
        H->entries[idx].key = key;
        H->entries[idx].value = value;
        H->entries[idx].state = OCCUPIED;
        H->size++;
    }
}

// 查找
int *findOpen(OpenHashTable *H, int key) {
    int idx = key % OPEN_TABLE_SIZE;
    int start = idx;
    do {
        if (H->entries[idx].state == EMPTY)
            return NULL;
        if (H->entries[idx].state == OCCUPIED && 
            H->entries[idx].key == key)
            return &H->entries[idx].value;
        idx = (idx + 1) % OPEN_TABLE_SIZE;
    } while (idx != start);
    return NULL;
}

// 删除（懒删除：标记为DELETED）
void deleteOpen(OpenHashTable *H, int key) {
    int idx = key % OPEN_TABLE_SIZE;
    int start = idx;
    do {
        if (H->entries[idx].state == EMPTY)
            return;
        if (H->entries[idx].state == OCCUPIED && 
            H->entries[idx].key == key) {
            H->entries[idx].state = DELETED;
            H->size--;
            return;
        }
        idx = (idx + 1) % OPEN_TABLE_SIZE;
    } while (idx != start);
}

开放寻址法的探测方式：

线性探测：h(k), h(k)+1, h(k)+2, ... → 容易产生"一次聚集"
二次探测：h(k), h(k)+1², h(k)+2², ... → 减少聚集
双重散列：h(k), h(k)+h₂(k), h(k)+2h₂(k), ... → 最好

5.4 重新散列

当装载因子超过某个阈值（通常0.5-0.75），需要扩大表的容量并重新插入所有元素。

// 重新散列
void rehash(HashTable *H) {
    int oldSize = TABLE_SIZE;
    ListNode **oldLists = H->lists;
    
    // 分配新表（通常为原来的2倍，取素数）
    int newSize = oldSize * 2 + 1;  // 简化
    // 实际中需要分配新的数组...
    
    // 重新插入所有元素
    for (int i = 0; i < oldSize; i++) {
        ListNode *pos = oldLists[i];
        while (pos != NULL) {
            // insert into new table with new hash function
            ListNode *next = pos->next;
            // ...
            pos = next;
        }
    }
}
// 重新散列的代价是 O(n)，但摊还到每次插入上仍是 O(1)

三、实战案例

3.1 用散列表实现集合

typedef struct IntSet {
    HashTable *table;
} IntSet;

IntSet *createSet() {
    IntSet *S = (IntSet *)malloc(sizeof(IntSet));
    S->table = createTable();
    return S;
}

void setAdd(IntSet *S, int key) {
    insert(S->table, key, 1);
}

int setContains(IntSet *S, int key) {
    return find(S->table, key) != NULL;
}

void setRemove(IntSet *S, int key) {
    delete(S->table, key);
}
// 所有操作平均O(1)

3.2 布隆过滤器

布隆过滤器是一种空间高效的概率数据结构，用于判断元素是否在集合中。

#define BF_SIZE 1000
#define NUM_HASH 3

typedef struct BloomFilter {
    int bits[BF_SIZE / 32 + 1];
} BloomFilter;

// 简单的多个散列函数
int hash_i(int key, int i) {
    return (key * (i + 1) * 31) % BF_SIZE;
}

void bfSetBit(BloomFilter *bf, int pos) {
    bf->bits[pos / 32] |= (1 << (pos % 32));
}

int bfGetBit(BloomFilter *bf, int pos) {
    return (bf->bits[pos / 32] >> (pos % 32)) & 1;
}

void bfAdd(BloomFilter *bf, int key) {
    for (int i = 0; i < NUM_HASH; i++)
        bfSetBit(bf, hash_i(key, i));
}

int bfMaybeContains(BloomFilter *bf, int key) {
    for (int i = 0; i < NUM_HASH; i++)
        if (!bfGetBit(bf, hash_i(key, i)))
            return 0;  // 一定不在
    return 1;          // 可能在（有假阳性）
}
// 布隆过滤器不会漏报（false negative），但可能误报（false positive）
// 空间效率远高于散列表

四、本章小结

散列表在平均 O(1) 时间内支持查找、插入和删除操作。

散列函数的设计目标是使键均匀分布到各个桶中。

链地址法实现简单，对装载因子不敏感，但需要额外指针空间。

开放寻址法不需要额外空间，但对装载因子敏感，容易产生聚集。

重新散列在装载因子过高时进行，摊还代价为 O(1)。

布隆过滤器用极小的空间实现概率性的成员检测。

五、思考与练习

思考题

为什么散列表的表大小通常选择素数？

链地址法和开放寻址法，哪种更适合频繁删除的场景？

设计一个散列函数，用于将IP地址映射到数组索引。

编程练习

实现一个完整的散列表（链地址法），支持插入、查找、删除和遍历。

实现布隆过滤器，测试不同参数下的假阳性率。

用散列表实现一个简单的拼写检查器。