C++中Hash表与哈希表实现

在C++中，哈希表（Hash Table）是一种数据结构，它提供了快速的插入、删除和查找操作

以下是一个简单的C++哈希表实现示例：

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

class HashTable {
public:
    HashTable(size_t size) : table(size), num_elements(0) {}

    void insert(int key) {
        if (num_elements >= table.size() * 0.75) {
            resize();
        }

        size_t index = hash(key);
        for (auto& entry : table[index]) {
            if (entry.first == key) {
                return; // Key already exists, do not insert
            }
        }

        table[index].push_back({key, true});
        num_elements++;
    }

    bool remove(int key) {
        size_t index = hash(key);
        for (auto it = table[index].begin(); it != table[index].end(); ++it) {
            if (it->first == key) {
                table[index].erase(it);
                num_elements--;
                return true;
            }
        }
        return false; // Key not found
    }

    bool search(int key) const {
        size_t index = hash(key);
        for (const auto& entry : table[index]) {
            if (entry.first == key) {
                return true;
            }
        }
        return false; // Key not found
    }

private:
    std::vector<std::list<std::pair<int, bool>>> table;
    size_t num_elements;

    size_t hash(int key) const {
        return std::hash<int>{}(key) % table.size();
    }

    void resize() {
        size_t new_size = table.size() * 2;
        std::vector<std::list<std::pair<int, bool>>> new_table(new_size);

        for (const auto& bucket : table) {
            for (const auto& entry : bucket) {
                size_t new_index = std::hash<int>{}(entry.first) % new_size;
                new_table[new_index].push_back(entry);
            }
        }

        table = std::move(new_table);
    }
};

int main() {
    HashTable ht(10);
    ht.insert(1);
    ht.insert(11);
    ht.insert(21);

    std::cout << "Search 1: " << ht.search(1) << std::endl; // Output: Search 1: 1 (true)
    std::cout << "Search 11: " << ht.search(11) << std::endl; // Output: Search 11: 1 (true)
    std::cout << "Search 21: " << ht.search(21) << std::endl; // Output: Search 21: 1 (true)
    std::cout << "Search 31: " << ht.search(31) << std::endl; // Output: Search 31: 0 (false)

    ht.remove(11);
    std::cout << "Search 11 after removal: " << ht.search(11) << std::endl; // Output: Search 11 after removal: 0 (false)

    return 0;
}

这个示例实现了一个简单的哈希表，使用std::vector和std::list来存储数据。哈希函数使用C++标准库中的std::hash。当哈希表的元素数量达到容量的75%时，会自动调整哈希表的大小。