C++ Hash表与哈希桶设计

在C++中，哈希表（HashTable）和哈希桶（Hash Bucket）是两种常见的数据结构，用于实现高效的数据存储和查找

1. 哈希表（HashTable）： 哈希表是一种使用哈希函数将键（Key）映射到值（Value）的数据结构。它支持快速插入、删除和查找操作。哈希表的主要优点是在大多数情况下，这些操作的时间复杂度接近O(1)。然而，在最坏的情况下，例如当所有键都发生冲突时，这些操作的时间复杂度可能会退化为O(n)。

2. 哈希桶（Hash Bucket）： 哈希桶是哈希表中存储数据的基本单元。它是一个数组，用于存储具有相同哈希值的键值对。哈希桶的数量决定了哈希表的大小。当插入一个新的键值对时，首先计算其哈希值，然后根据该哈希值将键值对存储到相应的哈希桶中。

哈希桶的设计要点：

• 桶的数量：选择一个合适的桶数量可以降低冲突的概率，从而提高查询效率。通常，可以根据预期的数据量和可接受的负载因子（Load Factor）来确定桶的数量。负载因子是哈希表中已存储元素数量与桶数量的比值。当负载因子过大时，可能需要增加桶的数量以降低冲突概率。

• 动态调整：当哈希表的负载因子超过某个阈值时，可以通过重新哈希（Rehashing）操作来调整哈希表的大小和桶的数量。这样可以降低冲突概率，提高查询效率。重新哈希操作通常涉及创建一个新的哈希表，将原哈希表中的键值对重新计算哈希值并存储到新的哈希桶中。

• 冲突解决策略：当两个或多个键具有相同的哈希值时，会发生冲突。常见的冲突解决策略有开放寻址法（Open Addressing）和链地址法（Separate Chaining）。开放寻址法通过线性探测、二次探测或双散列等方法在哈希表中寻找空闲的桶来存储冲突的键值对。链地址法则是将具有相同哈希值的键值对存储在一个链表中，每个桶对应一个链表。

下面是一个简单的C++哈希表实现示例，使用链地址法解决冲突：

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

template<typename Key, typename Value>
class HashTable {
public:
    HashTable(size_t bucket_count) : buckets(bucket_count), load_factor(0.75) {}

    void insert(const Key& key, const Value& value) {
        if (load_factor * buckets.size() < buckets.size()) {
            rehash();
        }

        size_t index = hash(key) % buckets.size();
        auto& bucket = buckets[index];
        for (auto& entry : bucket) {
            if (entry.first == key) {
                entry.second = value;
                return;
            }
        }
        bucket.emplace_back(key, value);
    }

    bool find(const Key& key, Value& value) const {
        size_t index = hash(key) % buckets.size();
        const auto& bucket = buckets[index];
        for (const auto& entry : bucket) {
            if (entry.first == key) {
                value = entry.second;
                return true;
            }
        }
        return false;
    }

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

private:
    size_t hash(const Key& key) const {
        return std::hash<Key>{}(key);
    }

    void rehash() {
        size_t new_bucket_count = buckets.size() * 2;
        std::vector<std::list<std::pair<Key, Value>>> new_buckets(new_bucket_count);

        for (const auto& bucket : buckets) {
            for (const auto& entry : bucket) {
                size_t new_index = hash(entry.first) % new_bucket_count;
                new_buckets[new_index].push_back(entry);
            }
        }

        buckets = std::move(new_buckets);
    }

    std::vector<std::list<std::pair<Key, Value>>> buckets;
    double load_factor;
};

int main() {
    HashTable<int, std::string> table(10);
    table.insert(1, "one");
    table.insert(11, "eleven");
    table.insert(21, "twenty-one");

    std::string value;
    if (table.find(1, value)) {
        std::cout << "Found: " << value << std::endl;
    } else {
        std::cout << "Not found" << std::endl;
    }

    table.remove(1);

    if (table.find(1, value)) {
        std::cout << "Found: " << value << std::endl;
    } else {
        std::cout << "Not found" << std::endl;
    }

    return 0;
}

这个示例中，我们使用std::list作为哈希桶的数据结构，存储具有相同哈希值的键值对。当需要调整哈希表的大小时，我们创建一个新的哈希表，并将原哈希表中的键值对重新计算哈希值并存储到新的哈希桶中。