C++中Hash表扩容机制

在C++中，哈希表（Hash Table）是一种非常重要的数据结构，它提供了快速的插入、删除和查找操作。然而，当哈希表中的元素数量增加到一定程度时，为了保持操作的效率，我们需要对哈希表进行扩容。下面是一个简单的C++哈希表扩容机制的实现：

1. 首先，定义一个哈希表类（HashTable）：

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

class HashTable {
public:
    HashTable(size_t size);
    ~HashTable();

    void insert(int key);
    bool remove(int key);
    bool search(int key) const;

private:
    struct Entry {
        int key;
        bool occupied;
        Entry() : occupied(false) {}
    };

    size_t size_;
    size_t capacity_;
    std::vector<std::list<Entry>> table_;

    size_t hash(int key) const;
    void rehash(size_t new_capacity);
};

2. 实现哈希表类的构造函数和析构函数：

HashTable::HashTable(size_t size) : size_(0), capacity_(size), table_(size) {}

HashTable::~HashTable() {}

3. 实现插入操作：

void HashTable::insert(int key) {
    if (search(key)) {
        return;
    }

    size_t index = hash(key);
    for (auto& entry : table_[index]) {
        if (!entry.occupied) {
            entry.key = key;
            entry.occupied = true;
            size_t new_capacity = capacity_ * 2;
            rehash(new_capacity);
            return;
        }
    }

    table_[index].push_back({key, true});
    size_t new_capacity = capacity_ * 2;
    rehash(new_capacity);
}

4. 实现删除操作：

bool HashTable::remove(int key) {
    size_t index = hash(key);
    for (auto it = table_[index].begin(); it != table_[index].end(); ++it) {
        if (it->key == key) {
            it->occupied = false;
            size_t new_capacity = capacity_ / 2;
            rehash(new_capacity);
            return true;
        }
    }
    return false;
}

5. 实现查找操作：

bool HashTable::search(int key) const {
    size_t index = hash(key);
    for (const auto& entry : table_[index]) {
        if (entry.key == key) {
            return true;
        }
    }
    return false;
}

6. 实现哈希函数和扩容操作：

size_t HashTable::hash(int key) const {
    return key % capacity_;
}

void HashTable::rehash(size_t new_capacity) {
    std::vector<std::list<Entry>> new_table(new_capacity);
    for (const auto& bucket : table_) {
        for (const auto& entry : bucket) {
            if (entry.occupied) {
                size_t new_index = hash(entry.key);
                new_table[new_index].push_back(entry);
            }
        }
    }

    capacity_ = new_capacity;
    table_ = std::move(new_table);
}

这个简单的实现中，当哈希表的负载因子（已存储元素数量与总容量的比值）超过0.5时，就会触发扩容操作。扩容操作会将哈希表的总容量加倍，并将所有元素重新插入新的哈希表中。这样可以确保哈希表的性能在元素数量增加时保持在一个较高的水平。