哈希表底层实现解析

哈希表底层实现（C++版）—— 从4个数组到STL容器

哈希表作为高效的键值对存储结构，核心优势是O(1)级别的增删改查效率，其底层实现依赖冲突解决策略与数据结构设计。本文结合C++实现，从“4个数组手动实现”到“STL容器原理”，完整拆解哈希表的核心逻辑、设计考量及不同实现方案的差异，适配面试与工程实践场景（我基于面试题总结而来的）。

一、基础实现：4个数组构建开放寻址法哈希表

开放寻址法的核心是用连续数组存储键值对，冲突时通过探测规则寻找下一个可用槽位。4个数组的设计是对该方案的结构化拆解，每个数组承担单一核心职责，确保功能完整与性能优化。

1. 4个数组分工与核心作用

• keys数组：存储哈希表的键，作为元素的唯一标识，是查找、删除的核心依据。
• values数组：存储键对应的值，与keys数组索引一一对应，实现键值对的关联存储。
• status数组：标记槽位状态（3种状态），解决开放寻址法中删除元素导致的查找失效问题：
  • 0：槽位从未被使用（初始状态）；
  • 1：槽位正在被占用；
  • 2：槽位曾被占用但已删除。
• hash_indices数组：缓存每个键的哈希值，避免多次查找/插入时重复计算（如长字符串哈希的遍历开销），优化性能。

对于status状态位的考量：考虑一个空哈希表，需要插入两个元素，并且都映射到同一位置，插入后第二个元素线性插入后一个位置，标记状态都是1，现在删除第一个元素，如果只有两种状态（0 未使用 / 1 已占用），删除的位置的状态应为0，但是哈希表中其中还存有这个键对应的值（第二个元素），所以删除第一个元素后需要标记状态为2已删除。

2. 核心辅助逻辑

（1）经典字符串哈希函数

采用多项式滚动哈希，公式为 hash = hash * 31 + c（31为经典质数，可优化为位运算 (x << 5) - x，兼顾效率与分布均匀性），最终取模哈希表容量得到索引。

size_t hashFunction(const string& key) const {
    size_t hash = 0;
    for (char c : key) hash = hash * 31 + c;
    return hash % capacity;
}

（2）线性探测函数（probe）

通过isInsert参数区分插入与查找/删除场景，复用探测逻辑：

• 插入（isInsert=true）：遇到状态0或2的槽位即可返回，优先复用已删除槽位；
• 查找/删除（isInsert=false）：遇到状态0则停止（无此键），遇到状态2需继续探测。

3. 4个数组设计的合理性

• 不能用2个数组（keys+values）：缺失status数组无法处理删除逻辑，缺失hash_indices数组导致性能下降，仅能实现基础插入查找，功能不完整。
• 不能用3个数组（keys+values+status）：功能可行但性能受损，需重复计算哈希值；面试中4个数组的设计更能体现性能优化意识，是基础实现与工程化实现的区分点。
• 无需5个及以上数组：额外数组（如探测步数、访问次数）属于冗余设计，增加内存占用与缓存失效概率，违背“最小必要”原则。

4. 实现代码

#include <iostream>
#include <string>
#include <cstring>
#include <stdexcept>

// 模板类：支持任意键值类型（这里示例用string键，int值，可扩展）
template <typename K, typename V>
class ArrayHashTable {
private:
    K* keys;          // 存储键的数组
    V* values;        // 存储值的数组
    int* status;      // 槽位状态：0=未使用，1=占用，2=已删除
    size_t* hash_indices; // 存储每个键的哈希值（第4个数组）
    size_t capacity;  // 哈希表容量（数组大小）
    size_t size;      // 当前存储的键值对数量

    // 哈希函数：将键转换为数组索引
    size_t hashFunction(const K& key) const {
        if constexpr (std::is_same_v<K, std::string>) {
            size_t hash = 0;
            for (char c : key) {
                hash = hash * 31 + c; // 经典字符串哈希
            }
            return hash % capacity;
        } else {
            // 其他类型（如int）直接取模
            return std::hash<K>()(key) % capacity;
        }
    }

    // 线性探测：找到可用槽位（插入/查找）
    size_t probe(const K& key, bool isInsert = false) {
        size_t index = hashFunction(key);
        size_t start = index;

        // 循环探测，直到找到目标或空槽位
        while (true) {
            // 状态0：未使用，插入时可用；查找时说明键不存在
            if (status[index] == 0) {
                if (isInsert) return index;
                else return capacity; // 表示未找到
            }
            // 状态1：占用，检查是否是目标键
            else if (status[index] == 1) {
                if (keys[index] == key) {
                    return index;
                }
            }
            // 状态2：已删除，插入时可用，查找时继续

            // 下一个索引（循环数组）
            index = (index + 1) % capacity;
            // 探测一圈没找到，插入失败（表满）
            if (index == start) {
                if (isInsert) throw std::runtime_error("Hash table is full");
                else return capacity;
            }
        }
    }

public:
    // 构造函数：初始化4个数组
    ArrayHashTable(size_t cap = 10) : capacity(cap), size(0) {
        keys = new K[capacity];
        values = new V[capacity];
        status = new int[capacity](); // 初始化为0（未使用）
        hash_indices = new size_t[capacity](); // 初始化为0
    }

    // 析构函数：释放数组内存
    ~ArrayHashTable() {
        delete[] keys;
        delete[] values;
        delete[] status;
        delete[] hash_indices;
    }

    // 插入键值对（若键已存在，更新值）
    void insert(const K& key, const V& value) {
        size_t index = probe(key, true); // 查找插入位置
        if (status[index] == 0) {
            // 新插入：初始化4个数组的对应位置
            keys[index] = key;
            values[index] = value;
            status[index] = 1;
            hash_indices[index] = hashFunction(key); // 存储哈希值
            size++;
        } else {
            // 键已存在：更新值
            values[index] = value;
        }
    }

    // 查找键对应的值（找到返回true，值通过引用传出）
    bool find(const K& key, V& value) {
        size_t index = probe(key);
        if (index == capacity) {
            return false; // 未找到
        }
        value = values[index];
        return true;
    }

    // 删除键值对
    bool remove(const K& key) {
        size_t index = probe(key);
        if (index == capacity) {
            return false; // 未找到
        }
        // 标记为已删除（不是直接清空，避免查找失效）
        status[index] = 2;
        size--;
        return true;
    }

    // 打印哈希表（调试用）
    void print() const {
        std::cout << "Hash Table (capacity=" << capacity << ", size=" << size << "):\n";
        for (size_t i = 0; i < capacity; i++) {
            std::cout << "Index " << i << ": ";
            if (status[i] == 1) {
                std::cout << "Key=" << keys[i] << ", Value=" << values[i] 
                          << ", Hash=" << hash_indices[i] << "\n";
            } else if (status[i] == 2) {
                std::cout << "(Deleted)\n";
            } else {
                std::cout << "(Empty)\n";
            }
        }
    }

    // 获取当前元素数量
    size_t getSize() const { return size; }
};

// 测试代码
int main() {
    // 创建哈希表（容量10）
    ArrayHashTable<std::string, int> ht(10);

    // 插入键值对
    ht.insert("apple", 5);
    ht.insert("banana", 3);
    ht.insert("cherry", 8);
    ht.insert("apple", 7); // 更新apple的值

    // 打印哈希表
    ht.print();

    // 查找值
    int value;
    if (ht.find("banana", value)) {
        std::cout << "\nFind banana: " << value << "\n";
    }

    // 删除键
    ht.remove("cherry");
    std::cout << "\nAfter delete cherry:\n";
    ht.print();

    return 0;
}

二、冲突解决的另一种方案：链地址法

链地址法通过“桶数组+链表”解决冲突，相比开放寻址法，数组设计更简化，状态管理更清晰。

1. 核心数组结构（3个数组+桶数组）

• keys/values数组：存储所有节点的键值（按节点索引存储，非槽位索引）；
• next数组：模拟链表指针，存储每个节点的后继节点索引（-1表示无后继）；
• bucket数组：存储每个桶的头节点索引，桶数量对应哈希表容量；
• status数组：仅需2种状态（0=空桶，1=有节点），标记桶是否被使用。

2. 核心优势：状态简化与删除友好

链地址法无需“已删除”状态（status=2），原因是删除的是链表节点而非桶：

• 删除时仅需调整链表指针，清空节点内容，不会中断后续查找逻辑；
• 桶状态仅需区分“空/非空”，结构更简洁，内存碎片化但扩容成本低。

3. 实现代码

#include <iostream>
#include <string>
#include <stdexcept>

template <typename K, typename V>
class ChainedHashTable {
private:
    K* keys;          // 存储所有键（节点级）
    V* values;        // 存储所有值（节点级）
    int* next;        // 链表指针：next[i]表示第i个节点的下一个节点索引
    int* bucket;      // 桶数组：bucket[b]表示第b个桶的头节点索引（-1表示空）
    int* status;      // 桶状态：0=未使用，1=已使用（长度=桶数）
    size_t bucket_count; // 桶的数量（哈希表容量）
    size_t node_count;   // 已使用的节点数
    size_t max_nodes;    // 节点数组的最大容量

    // 哈希函数（同开放寻址法）
    size_t hashFunction(const K& key) const {
        if constexpr (std::is_same_v<K, std::string>) {
            size_t hash = 0;
            for (char c : key) hash = hash * 31 + c;
            return hash % bucket_count;
        } else {
            return std::hash<K>()(key) % bucket_count;
        }
    }

    // 申请一个空节点（返回节点索引）
    int allocateNode() {
        for (size_t i = 0; i < max_nodes; i++) {
            if (keys[i] == K{} && values[i] == V{}) { // 简单判断节点是否空闲
                return i;
            }
        }
        throw std::runtime_error("Node pool is full");
    }

public:
    ChainedHashTable(size_t buckets = 10, size_t max_nodes = 100) 
        : bucket_count(buckets), max_nodes(max_nodes), node_count(0) {
        keys = new K[max_nodes]();
        values = new V[max_nodes]();
        next = new int[max_nodes];
        std::fill(next, next + max_nodes, -1); // 初始化为-1（无后继）
        
        bucket = new int[bucket_count];
        std::fill(bucket, bucket + bucket_count, -1); // 桶初始化为空
        
        status = new int[bucket_count](); // 桶状态初始化为0
    }

    ~ChainedHashTable() {
        delete[] keys;
        delete[] values;
        delete[] next;
        delete[] bucket;
        delete[] status;
    }

    // 插入键值对
    void insert(const K& key, const V& value) {
        size_t b = hashFunction(key);
        int current = bucket[b];

        // 检查桶内是否已有该键（更新值）
        while (current != -1) {
            if (keys[current] == key) {
                values[current] = value;
                return;
            }
            current = next[current];
        }

        // 无该键，新增节点
        int new_node = allocateNode();
        keys[new_node] = key;
        values[new_node] = value;
        next[new_node] = bucket[b]; // 头插法加入链表
        bucket[b] = new_node;
        status[b] = 1; // 标记桶为已使用
        node_count++;
    }

    // 查找键值对
    bool find(const K& key, V& value) {
        size_t b = hashFunction(key);
        int current = bucket[b];
        while (current != -1) {
            if (keys[current] == key) {
                value = values[current];
                return true;
            }
            current = next[current];
        }
        return false;
    }

    // 删除键值对
    bool remove(const K& key) {
        size_t b = hashFunction(key);
        int prev = -1;
        int current = bucket[b];

        while (current != -1) {
            if (keys[current] == key) {
                // 从链表中移除节点
                if (prev == -1) bucket[b] = next[current]; // 删除头节点
                else next[prev] = next[current];
                
                // 清空节点（标记为空闲）
                keys[current] = K{};
                values[current] = V{};
                next[current] = -1;
                node_count--;

                // 检查桶是否为空，更新状态
                if (bucket[b] == -1) status[b] = 0;
                return true;
            }
            prev = current;
            current = next[current];
        }
        return false;
    }
};

三、C++ STL中的哈希表容器

STL中基于哈希表的容器采用链地址法实现（桶+链表/红黑树），核心成员覆盖存储、管理、策略三大维度，接口更完整通用。

1. 核心成员构成

• 存储成员：桶数组（bucket_array）、节点池（node_pool）、大小（size_）、桶数量（bucket_count_）；
• 管理成员：最大负载因子（max_load_factor_，默认0.75）、内存分配器（allocator）；
• 策略成员：哈希函数对象（hasher）、键相等判断函数（key_equal）；
• 迭代器成员：全局迭代器（begin()/end()）、桶内迭代器（local_iterator）。

2. 常用容器及扩展接口

核心容器包括unordered_map（键值对）、unordered_set（集合）、unordered_multimap/unordered_multiset（允许重复键/元素），相比手动实现的数组哈希表，扩展接口包括：

• 容量管理：reserve()（预分配空间）、rehash()（强制扩容）；
• 批量操作：clear()（清空）、范围erase()；
• 工具接口：bucket()（键所在桶索引）、load_factor()（负载因子）、contains()（C++20，键存在性检查）；
• 自定义扩展：支持自定义哈希函数、相等比较器，适配复杂键类型。

四、两种实现方案对比（开放寻址法 vs 链地址法）

对比维度	开放寻址法（4个数组）	链地址法（3个数组+桶）
数组数量	4个（keys/values/status/hash_indices）	3个核心节点数组+桶数组+状态数组
状态类型	3种（0/1/2）	2种（0/1）
删除逻辑	标记为已删除，不释放槽位	删除链表节点，释放节点空间
空间效率	内存连续，缓存友好	内存碎片化，节点池可能浪费
扩容成本	高，需重新哈希所有元素	低，仅新增桶，链表无需调整

五、核心总结

1. 哈希表的核心是“哈希函数+冲突解决”，4个数组实现是开放寻址法的工程化设计，兼顾功能完整性与性能优化，是面试中的高频考点。
2. status数组的“已删除”状态是开放寻址法的必要设计，仅0/1状态会导致删除后查找失效；链地址法因删除逻辑不同，可简化为2种状态。
3. STL哈希容器基于链地址法，提供完整的容量管理、迭代器、自定义策略接口，相比手动实现更通用，但其核心设计思路与手动实现一致。
4. 两种冲突解决方案无优劣之分：开放寻址法适合小数据、高频访问场景；链地址法适合大数据、频繁增删场景，需根据业务需求选择。