D14. 集合与映射表

4.1 哈希散列是映射表的基础

目标：理解哈希表如何通过散列函数实现快速查找。

4.1.1 哈希表的核心机制

哈希表（Hash Table）通过散列函数将键（Key）映射为存储地址，实现**O(1)**时间复杂度的增删改查。其核心公式：

hash_address = hash_function(key) % table_size

关键概念：

• 散列函数：将任意类型键转换为整数（如JavaScript的hashCode()）。
• 模运算：将哈希值限制在表长范围内（如table_size=10时，哈希值123 → 123%10=3）。
• 桶（Bucket）：存储数据的单元，每个地址对应一个桶。

示例：手机通讯录的哈希实现

// 假设通讯录用哈希表存储，键为姓名，模数为26（对应26个字母）
const tableSize = 26;
function hash(key) {
    return key.charCodeAt(0) % tableSize; // 取首字母ASCII码模26
}
// "Zhang" → Z的ASCII是90 → 90%26=12 → 存储在桶12

4.2 对哈希值取模使数据近似均匀分布

目标：理解模运算如何优化哈希表的空间利用。

4.2.1 模运算的作用

通过hash(key) % tableSize，将任意大的哈希值映射到0到tableSize-1的地址范围。

• 均匀性要求：理想情况下，不同键的哈希值应均匀分布，减少冲突。
• 模数选择：通常选择质数（如7、13、31），以减少哈希值分布的周期性。

示例：模数选择的影响

// 错误示例：模数为10（非质数）
hash("apple") = 97 → 97%10 = 7
hash("banana") = 98 → 98%10 = 8
hash("cherry") = 99 → 99%10 = 9 → 易出现聚集

// 正确示例：模数为13（质数）
hash("apple") = 97 → 97%13 = 12
hash("banana") = 98 → 98%13 = 0 → 更均匀分布

4.3 映射表中哈希碰撞的处理

目标：掌握两种主流的碰撞解决方法及其实现。

4.3.1 碰撞的定义

当不同键k1≠k2满足hash(k1)=hash(k2)时，称为哈希碰撞。需通过冲突解决策略处理：

4.3.2 链地址法（Chaining）

• 思想：每个桶存储一个链表，碰撞的键存入同一链表。
• 优点：实现简单，性能稳定。
• 缺点：需额外内存存储指针。

class HashTable {
    constructor(size=10) {
        this.table = new Array(size).fill(null); // 初始化桶数组
    }
    _hash(key) {
        return key % this.table.length; // 简化哈希函数
    }
    set(key, value) {
        const index = this._hash(key);
        if (!this.table[index]) { // 桶为空，新建链表
            this.table[index] = [];
        }
        // 遍历链表更新或添加
        for (let i = 0; i < this.table[index].length; i++) {
            if (this.table[index][i].key === key) {
                this.table[index][i].value = value;
                return;
            }
        }
        this.table[index].push({key, value});
    }
}

4.3.3 开放寻址法（Open Addressing）

• 思想：碰撞时线性探测空桶，如hash(key) + 1, hash(key) + 2等。
• 优点：无需额外内存存储指针。
• 缺点：可能引发聚集问题（连续填充导致查找变慢）。

class OpenAddressHashTable {
    constructor(size=10) {
        this.table = new Array(size); // 空桶初始化为null
    }
    _hash(key) {
        return key % this.table.length;
    }
    set(key, value) {
        let index = this._hash(key);
        while (this.table[index] !== null && this.table[index].key !== key) {
            index = (index + 1) % this.table.length; // 线性探测
        }
        this.table[index] = {key, value};
    }
}

4.4 集合与映射表大幅降低时间复杂度

目标：通过JavaScript示例对比集合/映射与数组的性能差异。

4.4.1 集合（Set）

• 定义：无重复元素的集合，底层基于哈希表实现（键即值，无存储值）。
• JavaScript实现：Set对象。

const mySet = new Set();
mySet.add(1);           // O(1)
mySet.has(1);           // O(1)
mySet.delete(1);        // O(1)

与数组对比：

操作	Set	数组
添加/删除	O(1)	O(n)（需遍历）
查找	O(1)	O(n)

4.4.2 映射表（Map）

• 定义：键值对集合，键唯一，底层基于哈希表。
• JavaScript实现：Map对象。

const myMap = new Map();
myMap.set("name", "Alice"); // O(1)
myMap.get("name");          // O(1)
myMap.delete("name");       // O(1)

与对象对比：

特性	Map	对象（Object）
键类型	支持任意类型	仅字符串/符号
遍历顺序	插入顺序	无严格顺序（ES5前）
大小控制	明确长度	需手动维护

4.4.3 时间复杂度对比总结

操作	哈希表/集合	数组/对象
查找	O(1)	O(n)
插入/删除	O(1)	O(n)（中间操作）/O(1)（尾部）
适用场景	高频增删改查	顺序存储或需随机访问

知识回顾

1. 哈希表：通过散列函数将键映射为地址，结合模运算实现均匀分布。
2. 碰撞处理：链地址法（链表）和开放寻址法（线性探测）是主流策略。
3. 集合（Set）：无重复键的哈希表，时间复杂度O(1)。
4. 映射表（Map）：键值对的哈希表，支持任意类型键和顺序遍历。
5. 性能优势：哈希结构在增删改查上远优于数组/对象。

课后练习

1. 选择题：以下哪种方法能减少哈希碰撞的概率？

   • A. 减小模数
   • B. 使用质数作为模数
   • C. 扩大键的取值范围

2. 代码题：实现一个基于链地址法的简单哈希表，支持set和get操作。

3. 分析题：假设哈希表的负载因子（填充率）超过0.7时，需扩容至2倍。分析扩容对性能的影响。

扩展阅读

• 哈希函数设计：
  • Java的hashCode()：对象哈希值的计算逻辑。
  • 一致性哈希：分布式系统中均衡数据分布的算法。
• 高级冲突处理：
  • 双重哈希：二次探测法（探测步长动态变化）。
• 真实场景应用：
  • 数据库索引：B+树与哈希索引的对比。
  • 缓存系统：Redis的哈希表实现（结合链表和红黑树）。