C++如何实现一个简单的哈希表（Hash Table）？（代码示例）

尼克

发布时间：2025-12-31 16:50:02

579人浏览过

来源于php中文网

原创

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

c++如何实现一个简单的哈希表（hash table）？（代码示例）

用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";
}