## 哈希表容器封装：unordered_map与unordered_set的实现解析

在C++标准库中，unordered_map和unordered_set作为基于哈希表的关联容器，提供了高效的查找和插入操作。本文将深入探讨如何通过哈希表封装实现这两个核心容器，分析其内部机制和设计模式。

### 基础架构设计：模板化哈希表实现

哈希表封装的核心在于设计一个通用的哈希表基础结构，支持不同类型的键值对存储。我们首先构建一个可复用的哈希表模板。

```cpp

#include <vector>

#include <list>

#include <functional>

#include <memory>

// 前向声明哈希表类

template<typename T>

class HashTable;

// 哈希节点基类模板

template<typename T>

struct HashNode {

    T data;

    HashNode* next;

    

    HashNode(const T& val) : data(val), next(nullptr) {}

    virtual ~HashNode() = default;

};

// 特化版本：用于unordered_map的键值对节点

template<typename Key, typename Value>

struct HashNode<std::pair<Key, Value>> {

    std::pair<Key, Value> data;

    HashNode* next;

    

    HashNode(const std::pair<Key, Value>& val) : data(val), next(nullptr) {}

    HashNode(Key k, Value v) : data(std::make_pair(k, v)), next(nullptr) {}

};

```

### 通用哈希表模板实现

```cpp

template<typename T, typename Hash = std::hash<T>, typename KeyEqual = std::equal_to<T>>

class HashTable {

protected:

    using NodeType = HashNode<T>;

    

    std::vector<NodeType*> buckets;

    size_t bucket_count;

    size_t element_count;

    float max_load_factor;

    

    Hash hasher;

    KeyEqual key_equal;

    

    // 获取桶索引

    size_t get_bucket_index(const T& value) const {

        return hasher(get_key(value)) % bucket_count;

    }

    

    // 提取键的通用方法（通过特化实现）

    virtual const auto& get_key(const T& value) const {

        return value;  // 默认情况下，值本身就是键

    }

    

public:

    HashTable(size_t initial_buckets = 16, 

              float load_factor = 0.75f)

        : bucket_count(initial_buckets), 

          element_count(0),

          max_load_factor(load_factor) {

        buckets.resize(bucket_count, nullptr);

    }

    

    virtual ~HashTable() {

        clear();

    }

    

    // 插入元素

    bool insert(const T& value) {

        check_load_factor();

        

        size_t index = get_bucket_index(value);

        NodeType* current = buckets[index];

        

        // 检查是否已存在

        while (current) {

            if (key_equal(get_key(current->data), get_key(value))) {

                return false;  // 已存在

            }

            current = current->next;

        }

        

        // 创建新节点并插入到链表头部

        NodeType* newNode = create_node(value);

        newNode->next = buckets[index];

        buckets[index] = newNode;

        element_count++;

        

        return true;

    }

    

    // 查找元素

    NodeType* find(const T& value) const {

        size_t index = get_bucket_index(value);

        NodeType* current = buckets[index];

        

        while (current) {

            if (key_equal(get_key(current->data), get_key(value))) {

                return current;

            }

            current = current->next;

        }

        

        return nullptr;

    }

    

    // 删除元素

    bool erase(const T& value) {

        size_t index = get_bucket_index(value);

        NodeType* current = buckets[index];

        NodeType* prev = nullptr;

        

        while (current) {

            if (key_equal(get_key(current->data), get_key(value))) {

                if (prev) {

                    prev->next = current->next;

                } else {

                    buckets[index] = current->next;

                }

                

                delete_node(current);

                element_count--;

                return true;

            }

            prev = current;

            current = current->next;

        }

        

        return false;

    }

    

    // 清空哈希表

    void clear() {

        for (size_t i = 0; i < bucket_count; ++i) {

            NodeType* current = buckets[i];

            while (current) {

                NodeType* next = current->next;

                delete_node(current);

                current = next;

            }

            buckets[i] = nullptr;

        }

        element_count = 0;

    }

    

    size_t size() const { return element_count; }

    bool empty() const { return element_count == 0; }

    float load_factor() const { 

        return static_cast<float>(element_count) / bucket_count; 

    }

    

protected:

    virtual NodeType* create_node(const T& value) {

        return new NodeType(value);

    }

    

    virtual void delete_node(NodeType* node) {

        delete node;

    }

    

private:

    void check_load_factor() {

        if (load_factor() >= max_load_factor) {

            rehash(bucket_count * 2);

        }

    }

    

    void rehash(size_t new_bucket_count) {

        std::vector<NodeType*> new_buckets(new_bucket_count, nullptr);

        

        for (size_t i = 0; i < bucket_count; ++i) {

            NodeType* current = buckets[i];

            while (current) {

                NodeType* next = current->next;

                

                size_t new_index = hasher(get_key(current->data)) % new_bucket_count;

                current->next = new_buckets[new_index];

                new_buckets[new_index] = current;

                

                current = next;

            }

            buckets[i] = nullptr;

        }

        <"5j.acbf.cn"><"y9.adgp.cn"><"e2.adgp.cn">

        buckets = std::move(new_buckets);

        bucket_count = new_bucket_count;

    }

};

```

### unordered_set的实现

unordered_set是存储唯一元素的容器，基于哈希表实现集合操作。

```cpp

template<typename Key, 

         typename Hash = std::hash<Key>, 

         typename KeyEqual = std::equal_to<Key>>

class UnorderedSet : public HashTable<Key, Hash, KeyEqual> {

public:

    using Base = HashTable<Key, Hash, KeyEqual>;

    using iterator = typename Base::iterator;

    using const_iterator = typename Base::const_iterator;

    

    UnorderedSet(size_t initial_buckets = 16, float load_factor = 0.75f)

        : Base(initial_buckets, load_factor) {}

    

    // 集合特有操作

    bool contains(const Key& key) const {

        return this->find(key) != nullptr;

    }

    

    // 插入键（重写基类方法）

    std::pair<iterator, bool> insert(const Key& key) {

        bool inserted = Base::insert(key);

        // 这里需要返回迭代器，简化实现

        return std::make_pair(iterator(), inserted);

    }

    

    // 擦除键

    size_t erase(const Key& key) {

        return Base::erase(key) ? 1 : 0;

    }

    

    // 迭代器支持

    class iterator {

    private:

        using NodeType = typename Base::NodeType;

        NodeType* current;

        const UnorderedSet* container;

        size_t bucket_index;

        

        void advance_to_next() {

            if (!current) return;

            

            // 先尝试移动到链表下一个节点

            if (current->next) {

                current = current->next;

                return;

            }

            

            // 当前链表已结束，查找下一个非空桶

            for (size_t i = bucket_index + 1; i < container->bucket_count; ++i) {

                if (container->buckets[i]) {

                    current = container->buckets[i];

                    bucket_index = i;

                    return;

                }

            }

            

            // 没有更多元素

            current = nullptr;

        }

        

    public:

        iterator(NodeType* node = nullptr, 

                 const UnorderedSet* cont = nullptr, 

                 size_t index = 0)

            : current(node), container(cont), bucket_index(index) {}

        

        Key& operator*() const {

            return current->data;

        }

        

        Key* operator->() const {

            return &(current->data);

        }

        

        iterator& operator++() {

            advance_to_next();

            return *this;

        }

        

        bool operator==(const iterator& other) const {

            return current == other.current;

        }

        

        bool operator!=(const iterator& other) const {

            return !(*this == other);

        }

    };

    

    iterator begin() {

        for (size_t i = 0; i < this->bucket_count; ++i) {

            if (this->buckets[i]) {

                return iterator(this->buckets[i], this, i);

            }

        }

        return end();

    }

    

    iterator end() {

        return iterator(nullptr, this, this->bucket_count);

    }

};

```

### unordered_map的实现

unordered_map存储键值对，需要扩展哈希表以支持键值分离。

```cpp

template<typename Key, typename Value,

         typename Hash = std::hash<Key>,

         typename KeyEqual = std::equal_to<Key>>

class UnorderedMap : public HashTable<std::pair<Key, Value>, Hash, KeyEqual> {

private:

    using Base = HashTable<std::pair<Key, Value>, Hash, KeyEqual>;

    using NodeType = typename Base::NodeType;

    

    // 重写基类的get_key方法

    const Key& get_key(const std::pair<Key, Value>& value) const override {

        return value.first;

    }

    

protected:

    NodeType* create_node(const std::pair<Key, Value>& value) override {

        return new HashNode<std::pair<Key, Value>>(value);

    }

    

public:

    UnorderedMap(size_t initial_buckets = 16, float load_factor = 0.75f)

        : Base(initial_buckets, load_factor) {}

    

    // 插入或更新键值对

    std::pair<iterator, bool> insert(const std::pair<Key, Value>& kv) {

        return insert_impl(kv.first, kv.second);

    }

    

    // 使用键值对插入

    std::pair<iterator, bool> insert(const Key& key, const Value& value) {

        return insert_impl(key, value);

    }

    

    // 下标操作符

    Value& operator[](const Key& key) {

        NodeType* node = this->find(std::make_pair(key, Value()));

        if (!node) {

            auto result = insert_impl(key, Value());

            node = result.first.current;  // 简化处理

        }

        return node->data.second;

    }

    

    // at方法（带边界检查）

    Value& at(const Key& key) {

        NodeType* node = this->find(std::make_pair(key, Value()));

        if (!node) {

            throw std::out_of_range("Key not found in unordered_map");

        }

        return node->data.second;

    }

    

    const Value& at(const Key& key) const {

        NodeType* node = this->find(std::make_pair(key, Value()));

        if (!node) {

            throw std::out_of_range("Key not found in unordered_map");

        }

        return node->data.second;

    }

    

    // 查找键

    iterator find(const Key& key) {

        NodeType* node = this->find(std::make_pair(key, Value()));

        if (node) {

            // 需要找到对应的桶索引

            size_t index = this->get_bucket_index(std::make_pair(key, Value()));

            return iterator(node, this, index);

        }

        return end();

    }

    

    // 擦除键

    size_t erase(const Key& key) {

        return this->erase(std::make_pair(key, Value())) ? 1 : 0;

    }

    

private:

    std::pair<iterator, bool> insert_impl(const Key& key, const Value& value) {

        this->check_load_factor();

        

        size_t index = this->get_bucket_index(std::make_pair(key, value));

        NodeType* current = this->buckets[index];

        

        // 检查是否已存在相同键

        while (current) {

            if (this->key_equal(get_key(current->data), key)) {

                // 已存在，更新值

                current->data.second = value;

                return std::make_pair(iterator(current, this, index), false);

            }

            current = current->next;

        }

        <"u5.adgp.cn"><"b1.adgp.cn"><"x8.adgp.cn">

        // 创建新节点

        NodeType* newNode = create_node(std::make_pair(key, value));

        newNode->next = this->buckets[index];

        this->buckets[index] = newNode;

        this->element_count++;

        

        return std::make_pair(iterator(newNode, this, index), true);

    }

    

public:

    // 迭代器类

    class iterator {

    private:

        NodeType* current;

        const UnorderedMap* container;

        size_t bucket_index;

        

        void advance_to_next() {

            if (!current) return;

            

            if (current->next) {

                current = current->next;

                return;

            }

            

            for (size_t i = bucket_index + 1; i < container->bucket_count; ++i) {

                if (container->buckets[i]) {

                    current = container->buckets[i];

                    bucket_index = i;

                    return;

                }

            }

            

            current = nullptr;

        }

        

    public:

        iterator(NodeType* node = nullptr, 

                 const UnorderedMap* cont = nullptr, 

                 size_t index = 0)

            : current(node), container(cont), bucket_index(index) {}

        

        std::pair<Key, Value>& operator*() const {

            return current->data;

        }

        

        std::pair<Key, Value>* operator->() const {

            return &(current->data);

        }

        

        iterator& operator++() {

            advance_to_next();

            return *this;

        }

        

        bool operator==(const iterator& other) const {

            return current == other.current;

        }

        

        bool operator!=(const iterator& other) const {

            return !(*this == other);

        }

    };

    

    iterator begin() {

        for (size_t i = 0; i < this->bucket_count; ++i) {

            if (this->buckets[i]) {

                return iterator(this->buckets[i], this, i);

            }

        }

        return end();

    }

    

    iterator end() {

        return iterator(nullptr, this, this->bucket_count);

    }

};

```

### 优化与扩展功能

**自定义内存分配器支持**

```cpp

template<typename T, typename Allocator = std::allocator<T>>

class CustomAllocatorHashTable : public HashTable<T> {

private:

    using Base = HashTable<T>;

    using NodeAllocator = typename Allocator::template rebind<HashNode<T>>::other;

    

    NodeAllocator node_allocator;

    

protected:

    typename Base::NodeType* create_node(const T& value) override {

        typename Base::NodeType* node = node_allocator.allocate(1);

        node_allocator.construct(node, value);

        return node;

    }

    

    void delete_node(typename Base::NodeType* node) override {

        node_allocator.destroy(node);

        node_allocator.deallocate(node, 1);

    }

};

```

**并发访问支持**

```cpp

#include <shared_mutex>

template<typename T>

class ThreadSafeHashTable : public HashTable<T> {

private:

    using Base = HashTable<T>;

    

    mutable std::vector<std::shared_mutex> bucket_mutexes;

    

public:

    ThreadSafeHashTable(size_t initial_buckets = 16, float load_factor = 0.75f)

        : Base(initial_buckets, load_factor) {

        bucket_mutexes.resize(initial_buckets);

    }

    

    bool thread_safe_insert(const T& value) {

        size_t index = this->get_bucket_index(value);

        

        {

            std::unique_lock lock(bucket_mutexes[index]);

            return Base::insert(value);

        }

    }

    

    typename Base::NodeType* thread_safe_find(const T& value) const {

        size_t index = this->get_bucket_index(value);

        

        {

            std::shared_lock lock(bucket_mutexes[index]);

            return Base::find(value);

        }

    }

};

```

### 使用示例与测试

```cpp

void test_containers() {

    // 测试UnorderedSet

    UnorderedSet<int> intSet;

    intSet.insert(1);

    intSet.insert(2);

    intSet.insert(3);

    

    std::cout << "Set contains 2: " << intSet.contains(2) << std::endl;

    std::cout << "Set size: " << intSet.size() << std::endl;

    

    // 测试UnorderedMap

    UnorderedMap<std::string, int> wordCount;

    wordCount["apple"] = 5;

    wordCount["banana"] = 3;

    wordCount["cherry"] = 7;

    

    // 使用下标操作符访问

    wordCount["apple"] += 1;

    

    // 使用at方法访问（带边界检查）

    try {

        int count = wordCount.at("apple");

        std::cout << "Apple count: " << count << std::endl;

    } catch (const std::out_of_range& e) {

        std::cerr << e.what() << std::endl;

    }

    

    // 遍历map

    std::cout << "\nWord counts:" << std::endl;

    for (auto it = wordCount.begin(); it != wordCount.end(); ++it) {

        std::cout << it->first << ": " << it->second << std::endl;

    }

    

    // 使用C++11范围for遍历

    std::cout << "\nUsing range-based for loop:" << std::endl;

    for (const auto& [key, value] : wordCount) {

        std::cout << key << ": " << value << std::endl;

    }

}

```

### 性能分析与优化建议

1. **负载因子调优**：根据实际使用场景调整最大负载因子

2. **初始桶数量**：预先分配合理数量的桶减少rehash次数

3. **哈希函数选择**：为自定义类型提供高质量的哈希函数

4. **内存局部性**：考虑使用开放定址法改善缓存命中率

5. **批量操作**：添加批量插入和删除的优化版本

### 总结

通过哈希表封装实现unordered_map和unordered_set，不仅加深了对这两个重要容器的理解，也展示了如何设计可复用、可扩展的数据结构。关键设计点包括：

1. **模板化设计**：支持任意类型的键和值

2. **继承与特化**：通过继承重用代码，通过特化处理不同类型

3. **迭代器支持**：提供标准的迭代器接口

4. **内存管理**：支持自定义分配器

5. **线程安全**：可选的并发访问支持

这种封装方法展示了如何将底层数据结构转化为符合STL标准的容器，为理解和设计复杂数据结构的封装提供了宝贵参考。在实际应用中，可以根据具体需求进一步优化和扩展这些实现。