哈希表C++实现

引言

哈希表是一种高效的数据结构，用于快速查找、插入和删除操作。通过使用一个哈希函数将键映射到索引位置，可以实现接近常数时间复杂度的操作。在本文中，我们将探讨如何用C++实现一个简单的哈希表。

哈希表的基本概念

什么是哈希表？

哈希表是一种通过哈希函数将键值转换为数组索引的存储结构。其核心思想是利用哈希函数计算出一个特定的内存地址，并在该位置进行数据的存取操作，从而实现高效的查找、插入和删除。

哈希冲突

由于哈希函数的限制，在某些情况下可能会出现不同的键值映射到相同的索引位置上。这种现象称为哈希冲突。常见的解决方法包括开放寻址法（线性探测、二次探测等）和链地址法（使用链表存储碰撞的数据）。

C++实现概述

在C++中，我们可以自定义一个简单的哈希表，并支持插入、删除和查找操作。为了简化示例代码，我们将采用链地址法来处理哈希冲突。

数据结构设计

首先需要定义键值对的结构体（或类），以及哈希表的主体部分：

#include <iostream>
#include <vector>
#include <list>

struct HashPair {
    int key;
    std::string value;

    // 构造函数
    HashPair(int k, const std::string& v) : key(k), value(v) {}
};

class SimpleHashtable {
public:
    SimpleHashtable(size_t capacity = 1024);
    ~SimpleHashtable();
    
    void insert(const int key, const std::string& value);
    bool search(const int key);
    void remove(const int key);

private:
    size_t capacity;
    std::vector<std::list<HashPair>> table;

    // 哈希函数
    size_t hashFunction(int key) const;
};

构造函数与析构函数

在构造函数中初始化哈希表，并根据给定的容量创建一个链表向量。

SimpleHashtable::SimpleHashtable(size_t capacity)
    : capacity(capacity), table(capacity) {}

SimpleHashtable::~SimpleHashtable() {
    // 清理表中的所有数据
    for (auto& chain : table) {
        while (!chain.empty()) {
            HashPair pair = chain.front();
            chain.pop_front();  // 移除第一个元素
        }
    }
}

插入操作

插入新条目时，根据键值计算出哈希索引位置，并将数据插入到对应的链表中。如果发生冲突，则将其添加至链尾。

void SimpleHashtable::insert(const int key, const std::string& value) {
    size_t index = hashFunction(key);
    table[index].push_back({key, value});
}

查找操作

在查找数据时，同样根据键值计算出哈希索引位置，并检查链表中的每个元素直到找到匹配项或遍历完整个链。

bool SimpleHashtable::search(const int key) {
    size_t index = hashFunction(key);
    for (auto& pair : table[index]) {
        if (pair.key == key) {
            return true;
        }
    }
    return false;
}

删除操作

删除条目时，也需要根据键值计算出哈希索引位置，并在链表中查找并移除相应元素。

void SimpleHashtable::remove(const int key) {
    size_t index = hashFunction(key);
    for (auto it = table[index].begin(); it != table[index].end(); ++it) {
        if (it->key == key) {
            table[index].erase(it);  // 删除当前节点
            return;
        }
    }
}

哈希函数实现

为了简单起见，这里采用了一个简单的哈希函数作为示例。实际应用中应根据具体需求选择合适的哈希算法。

size_t SimpleHashtable::hashFunction(int key) const {
    return key % capacity;
}

示例代码

下面是一个完整的C++程序实例：

#include <iostream>
#include <vector>
#include <list>
#include <string>

using namespace std;

struct HashPair {
    int key;
    string value;

    HashPair(int k, const string& v) : key(k), value(v) {}
};

class SimpleHashtable {
public:
    SimpleHashtable(size_t capacity = 1024);
    ~SimpleHashtable();

    void insert(const int key, const string& value);
    bool search(const int key);
    void remove(const int key);

private:
    size_t capacity;
    vector<list<HashPair>> table;

    size_t hashFunction(int key) const;
};

// 构造函数与析构函数实现
// 插入、查找、删除操作实现

int main() {
    SimpleHashtable hashtable;
    
    // 插入数据
    hashtable.insert(1, "One");
    hashtable.insert(2, "Two");
    hashtable.insert(3, "Three");

    // 查找数据
    cout << (hashtable.search(2) ? "Found" : "Not Found") << endl;

    // 删除数据
    hashtable.remove(2);

    // 再次查找已删除的数据
    cout << (hashtable.search(2) ? "Found" : "Not Found") << endl;

    return 0;
}

通过上述代码，我们可以看到一个简单的哈希表的实现过程。当然，在实际应用中还需要考虑更多细节问题，比如更好的哈希函数设计、负载因子管理以及更复杂的冲突解决机制等。