简单实现hash_table

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

template<typename K, typename V>
class HashTable {
private:
    using Node = std::pair<K, V>;
    using Bucket = std::list<Node>;
    std::vector<Bucket> table;
    size_t size;
    size_t capacity;
    size_t hash(const K& key) const {
        return std::hash<K>{}(key) % capacity;
    }

public:
    HashTable(size_t capacity = 10) : table(capacity > 0 ? capacity : 10), 
        size(0), 
        capacity(capacity > 0 ? capacity : 10) {}

    // 拷贝构造函数
    HashTable(const HashTable& other) 
        : table(other.capacity), size(other.size), capacity(other.capacity) {
        // 深拷贝每个bucket
        for (size_t i = 0; i < capacity; ++i) {
            table[i] = other.table[i];
        }
    }

    // 移动构造函数
    HashTable(HashTable&& other) noexcept 
        : table(std::move(other.table)), 
          size(other.size),
          capacity(other.capacity) {
        // 将源对象置为有效但空的状态
        other.size = 0;
        other.capacity = 10;
        other.table = std::vector<Bucket>(10);
    }

    void insert(const K& key, const V& value) {
        if (size >= capacity * 0.75) {
            reserve(capacity * 2);
        }
        size_t index = hash(key);
        for (auto& node : table[index]) {
            if (node.first == key) {
                node.second = value;
                return;
            }
        }
        table[index].emplace_back(key, value);
        size++;
    }

    bool find(const K& key, V& value) const {
        size_t index = hash(key);
        for (const auto& node : table[index]) {
            if (node.first == key) {
                value = node.second;
                return true;
            }
        }
        return false;
    }

    void remove(const K& key) {
        size_t index = hash(key);
        auto& bucket = table[index];
        for (auto iter = bucket.begin(); iter != bucket.end(); iter++) {
            if (iter->first == key) {
                bucket.erase(iter);
                size--;
                return;
            }
        }
    }

    size_t getSize() const {
        return size;
    }

    size_t getCapacity() const {
        return capacity;
    }

    bool isEmpty() const {
        return size == 0;
    }

    void clear() {
        for (auto& bucket : table) {
            bucket.clear();
        }
        size = 0;
    }

    void reserve(size_t newCapacity) {
        std::vector<Bucket> newTable(newCapacity);
        for (auto& bucket : table) {
            for (auto& node : bucket) {
                size_t index = std::hash<K>{}(node.first) % newCapacity;
                newTable[index].emplace_back(node);
            }
        }
        table = std::move(newTable);
        capacity = newCapacity;
    }
};

int main() {
    HashTable<std::string, int> table1(10);
    table1.insert("apple", 1);
    table1.insert("banana", 2);
    
    // 测试拷贝构造
    HashTable<std::string, int> table2(table1);
    table1.insert("cherry", 3);  // 修改table1
    
    int value;
    // 验证table2不受table1修改影响
    if (table2.find("cherry", value)) {
        std::cout << "Error: copy affected by source modification" << std::endl;
    } else {
        std::cout << "Copy test passed" << std::endl;
    }
    
    // 测试移动构造
    HashTable<std::string, int> table3(std::move(table1));
    // 验证table1被移动后是空的
    if (table1.getSize() != 0) {
        std::cout << "Error: source not empty after move" << std::endl;
    }
    
    // 验证table3包含原table1的所有元素
    if (table3.find("apple", value) && value == 1 &&
        table3.find("banana", value) && value == 2 &&
        table3.find("cherry", value) && value == 3) {
        std::cout << "Move test passed" << std::endl;
    } else {
        std::cout << "Error: moved table missing elements" << std::endl;
    }
    
    // 验证table1移动后仍然可用
    table1.insert("new", 4);
    if (table1.find("new", value) && value == 4) {
        std::cout << "Post-move source usability test passed" << std::endl;
    }

    return 0;
}