C++简易哈希表基于vector+list实现链地址法，支持int→string映射；核心包括取模哈希函数、桶内查重更新、引用返回查找值、迭代器删除；代码完整可运行，涵盖插入、查找、删除操作。

用C++实现一个简单的哈希表，核心是解决两个问题：哈希函数计算键的索引，以及处理哈希冲突（最常用的是链地址法）。下面是一个基于std::vector + std::list的简易开放寻址式哈希表（简化版，无动态扩容），支持插入、查找和删除。

哈希函数与桶结构设计

选择简单但分布较均匀的哈希函数（如对整数直接取模），用std::vector存储多个桶（每个桶是std::list<:pair value>>），避免指针管理复杂度。

• 哈希函数：对键取模桶数量，例如 hash(key) = std::abs(static_cast(key)) % buckets.size()
• 桶类型：每个桶存一个链表，容纳冲突的键值对
• 不支持泛型键类型（本例以int为键，std::string为值）便于理解；实际可模板化

完整可运行代码（C++11及以上）

// 简单哈希表实现：支持 int → string 映射

#include 
#include 
#include 
#include 
#include 
#include 

class SimpleHashTable {
private:
    static const size_t INITIAL_BUCKETS = 10;
    std::vector>> buckets;

    size_t hash(int key) const {
        return std::abs(key) % buckets.size();
    }

public:
    SimpleHashTable() : buckets(INITIAL_BUCKETS) {}

    void insert(int key, const std::string& value) {
        size_t idx = hash(key);
        auto& bucket = buckets[idx];

        // 先尝试更新已存在键
        for (auto& pair : bucket) {
            if (pair.first == key) {
                pair.second = value;
                return;
            }
        }
        // 否则插入新节点
        bucket.emplace_back(key, value);
    }

    bool find(int key, std::string& out_value) const {
        size_t idx = hash(key);
        const auto& bucket = buckets[idx];
        for (const auto& pair : bucket) {
            if (pair.first == key) {
                out_value = pair.second;
                return true;
            }
        }
        return false;
    }

    bool erase(int key) {
        size_t idx = hash(key);
        auto& bucket = buckets[idx];
        for (auto it = bucket.begin(); it != bucket.end(); ++it) {
            if (it->first == key) {
                bucket.erase(it);
                return true;
            }
        }
        return false;
    }
};

// 使用示例
int main() {
    SimpleHashTable ht;
    ht.insert(10, "apple");
    ht.insert(20, "banana");
    ht.insert(105, "cherry"); // 105 % 10 = 5，与 20 不冲突（20%10=0）

    std::string val;
    if (ht.find(10, val)) std::cout << "10 → " << val << "\n"; // apple
    if (ht.find(20, val)) std::cout << "20 → " << val << "\n"; // banana
    if (!ht.find(99, val)) std::cout << "99 not found\n";

    ht.erase(10);
    if (!ht.find(10, val)) std::cout << "10 removed\n";
}

关键细节说明

哈希冲突处理：采用链地址法（separate chaining），每个桶是链表，插入/查找/删除都在对应链表内操作，逻辑清晰且易于实现。

• 插入时先查重再更新，避免重复键
• 查找失败返回false，成功通过引用输出值
• 删除使用迭代器遍历并擦除，注意及时返回避免越界

可改进点（进阶参考）：

• 添加模板支持任意Key和Value类型（需提供std::hash或自定义哈希）
• 实现负载因子监控和自动扩容（如当平均链长 > 1.5 时重建桶数组）
• 改用开放寻址（线性探测/二次探测），节省内存但删除更复杂

不复杂但容易忽略

哈希表不是“一写就完”，真正实用的版本需要考虑：键的可哈希性、空值处理、异常安全、迭代器支持。但这个基础版本已涵盖核心机制——哈希定位 + 冲突应对。动手写一遍，比看十篇理论更能理解它怎么工作。