C++ 哈希表封装 myunordered_map 与 unordered_set：底层原理及实现

C++ 哈希表封装 myunordered_map 与 unordered_set：底层原理及实现 | 极客日志

unordered_set

key-value

key-only

// stl_hash_set
template<class Value, class HashFcn = hash<Value>, class EqualKey = equal_to<Value>, class Alloc = alloc>
class hash_set {
private:
    typedef hashtable<Value, Value, HashFcn, identity<Value>, EqualKey, Alloc> ht;
    ht rep;
public:
    typedef typename ht::key_type key_type;
    typedef typename ht::value_type value_type;
    typedef typename ht::hasher hasher;
    typedef typename ht::key_equal key_equal;
    typedef typename ht::const_iterator iterator;
    typedef typename ht::const_iterator const_iterator;
    hasher hash_funct() const { return rep.hash_funct(); }
    key_equal key_eq() const { return rep.key_eq(); }
};

// stl_hash_map
template<class Key, class T, class HashFcn = hash<Key>, class EqualKey = equal_to<Key>, class Alloc = alloc>
class hash_map {
private:
    typedef hashtable<pair<const Key, T>, Key, HashFcn, select1st<pair<const Key, T>>, EqualKey, Alloc> ht;
    ht rep;
public:
    typedef typename ht::key_type key_type;
    typedef T data_type;
    typedef T mapped_type;
    typedef typename ht::value_type value_type;
    typedef typename ht::hasher hasher;
    typedef typename ht::key_equal key_equal;
    typedef typename ht::iterator iterator;
    typedef typename ht::const_iterator const_iterator;
};

// stl_hashtable.h
template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
class hashtable {
public:
    typedef Key key_type;
    typedef Value value_type;
    typedef HashFcn hasher;
    typedef EqualKey key_equal;
private:
    hasher hash;
    key_equal equals;
    ExtractKey get_key;
    typedef __hashtable_node<Value> node;
    vector<node*, Alloc> buckets;
    size_type num_elements;
public:
    typedef __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> iterator;
    pair<iterator, bool> insert_unique(const value_type& obj);
    const_iterator find(const key_type& key) const;
};
template<class Value>
struct __hashtable_node {
    __hashtable_node* next;
    Value val;
};

template<class K, class T, class KeyofT, class Hash>
class HashTable {
    // K：哈希和查找时的 key 类型（myunordered_set 为 K，myunordered_map 为 K）
    // T：哈希表节点存储的实际数据类型（myunordered_set 为 K，myunordered_map 为 pair<const K, V>）
    // Hash：哈希函数仿函数（将 K 转为整形用于计算桶位置）
    // KeyOfT：从 T 中提取 K 的仿函数（适配 T 的不同类型）
};

// MyUnorderedSet.h
namespace Lotso {
template<class K, class Hash = HashFunc<K>>
class unordered_set {
    struct SetKeyofT {
        // 仿函数：从 T（pair<const K, V>）中提取 key
        const K& operator()(const K& key) {
            return key;
        }
    };
public:
    bool insert(const K& key) {
        return _ht.Insert(key);
    }
private:
    hash_bucket::HashTable<K, const K, SetKeyofT, Hash> _ht;
};
}

// MyUnorderedMap.h
namespace Lotso {
template<class K, class V, class Hash = HashFunc<K>>
class unordered_map {
    struct MapKeyofT {
        // 仿函数：从 T（pair<const K, V>）中提取 key
        const K& operator()(const pair<const K, V>& kv) {
            return kv.first;
        }
    };
public:
    bool insert(const pair<K, V>& kv) {
        return _ht.Insert(kv);
    }
private:
    hash_bucket::HashTable<K, pair<const K, V>, MapKeyofT, Hash> _ht;
};
}

// HashTable.h
#pragma once
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

// 质数表 (SGI STL 同款，用于扩容)
static const int __stl_num_primes = 28;
static const unsigned long __stl_prime_list[__stl_num_primes] = {
    53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317,
    196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843,
    50331653, 100663319, 201326611, 402653189, 805306457, 1610612741,
    3221225473, 4294967291
};

inline unsigned long __stl_next_prime(unsigned long n) {
    const unsigned long* first = __stl_prime_list;
    const unsigned long* last = __stl_prime_list + __stl_num_primes;
    const unsigned long* pos = lower_bound(first, last, n);
    return pos == last ? *(last - 1) : *pos;
}

// 哈希函数仿函数
template<class K>
struct HashFunc {
    size_t operator()(const K& key) {
        return (size_t)key; // 默认直接转换
    }
};

// 特化 string 类型的哈希函数
template<>
struct HashFunc<string> {
    // BKDR 字符串哈希算法
    size_t operator()(const string& key) {
        size_t hash = 0;
        for (auto ch : key) {
            hash += ch; // 累加字符 ASCII 码
            hash *= 131; // 乘质数 131，减少冲突
        }
        return hash;
    }
};

namespace hash_bucket {
template<class T>
struct HashNode {
    T _data;
    HashNode<T>* _next;
    HashNode(const T& data) : _data(data), _next(nullptr) {}
};

template<class K, class T, class KeyofT, class Hash = HashFunc<K>>
class HashTable {
    typedef HashNode<T> Node;
    HashTable() : _tables(__stl_next_prime(1), nullptr), _n(0) {}
    ~HashTable() {
        for (size_t i = 0; i < _tables.size(); i++) {
            Node* cur = _tables[i];
            while (cur) {
                Node* next = cur->_next;
                delete cur;
                cur = next;
            }
            _tables[i] = nullptr;
        }
        _n = 0;
    }
    bool Insert(const T& data) {
        KeyofT kot;
        Hash hs;
        // 先查找，避免重复插入
        if (Find(kot(data))) return false;
        // 负载因子 == 1 就开始扩容
        if (_n == _tables.size()) {
            std::vector<Node*> newtables(__stl_next_prime(_tables.size() + 1), nullptr);
            for (size_t i = 0; i < _tables.size(); i++) {
                // 遍历旧表，旧表节点重新映射，挪动到新表
                Node* cur = _tables[i];
                while (cur) {
                    Node* next = cur->_next;
                    // 头插
                    size_t hashi = hs(kot(cur->_data)) % newtables.size();
                    cur->_next = newtables[hashi];
                    newtables[hashi] = cur;
                    cur = next;
                }
                _tables[i] = nullptr;
            }
            _tables.swap(newtables);
        }
        size_t hashi = hs(kot(data)) % _tables.size();
        // 头插
        Node* newnode = new Node(data);
        newnode->_next = _tables[hashi];
        _tables[hashi] = newnode;
        ++_n;
        return true;
    }
private:
    std::vector<Node*> _tables;
    size_t _n;
};
}

// 哈希表迭代器
template<class K, class T, class Hash, class KeyOfT, class Equal>
struct HashTableIterator {
    typedef HashNode<T> Node;
    typedef HashTable<K, T, Hash, KeyOfT, Equal> HashTable;
    typedef HashTableIterator Self;
    Node* _node; // 当前指向的节点
    HashTable* _ht; // 指向哈希表，用于桶切换

    // 构造函数
    HashTableIterator(Node* node, HashTable* ht) : _node(node), _ht(ht) {}

    // 解引用运算符（返回节点数据引用）
    T& operator*() {
        return _node->_data;
    }

    // 箭头运算符（支持->访问成员，如 map 的 first/second）
    T* operator->() {
        return &_node->_data;
    }

    // 前置++（核心：遍历当前桶所有节点后，切换到下一个非空桶）
    Self& operator++() {
        if (_node->_next) {
            // 当前桶还有下一个节点，直接移动
            _node = _node->_next;
        } else {
            // 当前桶遍历完毕，找下一个非空桶
            K key = _ht->_kot(_node->_data);
            size_t hashi = _ht->_hash(key) % _ht->_tables.size();
            // 从当前桶的下一个桶开始查找
            ++hashi;
            while (hashi < _ht->_tables.size()) {
                if (_ht->_tables[hashi]) {
                    _node = _ht->_tables[hashi];
                    return *this;
                }
                ++hashi;
            }
            // 所有桶遍历完毕，迭代器失效（指向 nullptr）
            _node = nullptr;
        }
        return *this;
    }

    // 相等判断
    bool operator==(const Self& s) const {
        return _node == s._node;
    }

    // 不相等判断
    bool operator!=(const Self& s) const {
        return _node != s._node;
    }
};

#pragma once
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

// 质数表 (SGI STL 同款，用于扩容)
static const int __stl_num_primes = 28;
static const unsigned long __stl_prime_list[__stl_num_primes] = {
    53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317,
    196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843,
    50331653, 100663319, 201326611, 402653189, 805306457, 1610612741,
    3221225473, 4294967291
};

inline unsigned long __stl_next_prime(unsigned long n) {
    const unsigned long* first = __stl_prime_list;
    const unsigned long* last = __stl_prime_list + __stl_num_primes;
    const unsigned long* pos = lower_bound(first, last, n);
    return pos == last ? *(last - 1) : *pos;
}

// 哈希函数仿函数
template<class K>
struct HashFunc {
    size_t operator()(const K& key) {
        return (size_t)key; // 默认直接转换
    }
};

// 特化 string 类型的哈希函数
template<>
struct HashFunc<string> {
    // BKDR 字符串哈希算法
    size_t operator()(const string& key) {
        size_t hash = 0;
        for (auto ch : key) {
            hash += ch; // 累加字符 ASCII 码
            hash *= 131; // 乘质数 131，减少冲突
        }
        return hash;
    }
};

namespace hash_bucket {
template<class T>
struct HashNode {
    T _data;
    HashNode<T>* _next;
    HashNode(const T& data) : _data(data), _next(nullptr) {}
};

// 前置声明
template<class K, class T, class KeyofT, class Hash>
class HashTable;
template<class K, class T, class Ref, class Ptr, class KeyofT, class Hash>
struct HTIterator {
    typedef HashNode<T> Node;
    typedef HashTable<K, T, KeyofT, Hash> HT;
    typedef HTIterator<K, T, Ref, Ptr, KeyofT, Hash> Self;
    Node* _node;
    const HT* _pht;

    HTIterator(Node* node, const HT* pht) : _node(node), _pht(pht) {}

    Ref operator*() {
        return _node->_data;
    }

    Ptr operator->() {
        return &_node->_data;
    }

    Self& operator++() {
        if (_node->_next) // 当前桶没走完
        {
            _node = _node->_next;
        }
        else // 当前桶走完了，找到下一个桶的第一个结点
        {
            KeyofT kot;
            Hash hs;
            // 算出当前位置
            size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size();
            // ++到下一个位置
            ++hashi;
            while (hashi < _pht->_tables.size()) {
                if (_pht->_tables[hashi]) // 找到下一个不为空的桶
                {
                    _node = _pht->_tables[hashi];
                    break;
                }
                else {
                    ++hashi;
                }
            }
            if (hashi == _pht->_tables.size()) // 最后一个桶走完了，要++到 end() 位置
            {
                // end() 中_node 是空
                _node = nullptr;
            }
        }
        return *this;
    }

    bool operator!=(const Self& s) const {
        return _node != s._node;
    }

    bool operator==(const Self& s) const {
        return _node == s._node;
    }
};

template<class K, class T, class KeyofT, class Hash = HashFunc<K>>
class HashTable {
    // 友元声明
    template<class K, class T, class Ref, class Ptr, class KeyofT, class Hash>
    friend struct HTIterator;

    typedef HashNode<T> Node;
public:
    typedef HTIterator<K, T, T&, T*, KeyofT, Hash> Iterator;
    typedef HTIterator<K, T, const T&, const T*, KeyofT, Hash> ConstIterator;

    Iterator Begin() {
        if (_n == 0) {
            return End();
        }
        for (size_t i = 0; i < _tables.size(); i++) {
            if (_tables[i]) {
                return Iterator(_tables[i], this);
            }
        }
        return End();
    }

    Iterator End() {
        return Iterator(nullptr, this);
    }

    ConstIterator Begin() const {
        if (_n == 0) {
            return End();
        }
        for (size_t i = 0; i < _tables.size(); i++) {
            if (_tables[i]) {
                return ConstIterator(_tables[i], this);
            }
        }
        return End();
    }

    ConstIterator End() const {
        return ConstIterator(nullptr, this);
    }

    HashTable() : _tables(__stl_next_prime(1), nullptr), _n(0) {}

    ~HashTable() {
        for (size_t i = 0; i < _tables.size(); i++) {
            Node* cur = _tables[i];
            while (cur) {
                Node* next = cur->_next;
                delete cur;
                cur = next;
            }
            _tables[i] = nullptr;
        }
        _n = 0;
    }

    pair<Iterator, bool> Insert(const T& data) {
        KeyofT kot;
        Hash hs;
        // 先查找，避免重复插入
        if (auto it = Find(kot(data)); it != End()) return {it, false};
        // 负载因子 == 1 就开始扩容
        if (_n == _tables.size()) {
            std::vector<Node*> newtables(__stl_next_prime(_tables.size() + 1), nullptr);
            for (size_t i = 0; i < _tables.size(); i++) {
                // 遍历旧表，旧表节点重新映射，挪动到新表
                Node* cur = _tables[i];
                while (cur) {
                    Node* next = cur->_next;
                    // 头插
                    size_t hashi = hs(kot(cur->_data)) % newtables.size();
                    cur->_next = newtables[hashi];
                    newtables[hashi] = cur;
                    cur = next;
                }
                _tables[i] = nullptr;
            }
            _tables.swap(newtables);
        }
        size_t hashi = hs(kot(data)) % _tables.size();
        // 头插
        Node* newnode = new Node(data);
        newnode->_next = _tables[hashi];
        _tables[hashi] = newnode;
        ++_n;
        return {Iterator(newnode, this), true};
    }

    Iterator Find(const K& key) {
        KeyofT kot;
        Hash hs;
        size_t hashi = hs(key) % _tables.size();
        Node* cur = _tables[hashi];
        while (cur) {
            if (kot(cur->_data) == key) {
                return {cur, this};
            }
            cur = cur->_next;
        }
        return {nullptr, this};
    }

    bool Erase(const K& key) {
        KeyofT kot;
        Hash hs;
        size_t hashi = hs(key) % _tables.size();
        Node* prev = nullptr;
        Node* cur = _tables[hashi];
        while (cur) {
            if (kot(cur->_data) == key) {
                // 删除
                if (prev == nullptr) {
                    // 桶中第一个节点
                    _tables[hashi] = cur->_next;
                } else {
                    prev->_next = cur->_next;
                }
                --_n;
                delete cur;
                return true;
            }
            prev = cur;
            cur = cur->_next;
        }
        return false;
    }

private:
    std::vector<Node*> _tables;
    size_t _n;
};
}

#pragma once
#include"HashTable.h"
namespace Lotso {
template<class K, class Hash = HashFunc<K>>
class unordered_set {
    struct SetKeyofT {
        // 仿函数：从 T（pair<const K, V>）中提取 key
        const K& operator()(const K& key) {
            return key;
        }
    };
public:
    typedef typename hash_bucket::HashTable<K, const K, SetKeyofT, Hash>::Iterator iterator;
    typedef typename hash_bucket::HashTable<K, const K, SetKeyofT, Hash>::ConstIterator const_iterator;

    iterator begin() {
        return _ht.Begin();
    }
    iterator end() {
        return _ht.End();
    }
    const_iterator begin() const {
        return _ht.Begin();
    }
    const_iterator end() const {
        return _ht.End();
    }
    pair<iterator, bool> insert(const K& key) {
        return _ht.Insert(key);
    }
    iterator find(const K& key) {
        return _ht.Find(key);
    }
    bool erase(const K& key) {
        return _ht.Erase(key);
    }
private:
    hash_bucket::HashTable<K, const K, SetKeyofT, Hash> _ht;
};
}

#pragma once
#include"HashTable.h"
namespace Lotso {
template<class K, class V, class Hash = HashFunc<K>>
class unordered_map {
    struct MapKeyofT {
        // 仿函数：从 T（pair<const K, V>）中提取 key
        const K& operator()(const pair<const K, V>& kv) {
            return kv.first;
        }
    };
public:
    typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyofT, Hash>::Iterator iterator;
    typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyofT, Hash>::ConstIterator const_iterator;

    iterator begin() {
        return _ht.Begin();
    }
    iterator end() {
        return _ht.End();
    }
    const_iterator begin() const {
        return _ht.Begin();
    }
    const_iterator end() const {
        return _ht.End();
    }
    pair<iterator, bool> insert(const pair<K, V>& kv) {
        return _ht.Insert(kv);
    }
    V& operator[](const K& key) {
        pair<iterator, bool> ret = insert({key, V()});
        return ret.first->second;
    }
    iterator find(const K& key) {
        return _ht.Find(key);
    }
    bool erase(const K& key) {
        return _ht.Erase(key);
    }
private:
    hash_bucket::HashTable<K, pair<const K, V>, MapKeyofT, Hash> _ht;
};
}

#define _CRT_SECURE_NO_WARNINGS 1
#include"HashTable.h"
#include"unordered_set.h"
#include"unordered_map.h"

void Print(const Lotso::unordered_set<int>& s) {
    Lotso::unordered_set<int>::const_iterator it = s.begin();
    while (it != s.end()) {
        //*it = 1;
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

int main() {
    Lotso::unordered_set<int> us;
    us.insert(3);
    us.insert(1000);
    us.insert(2);
    us.insert(102);
    us.insert(2111);
    us.insert(22);
    Lotso::unordered_set<int>::iterator it = us.begin();
    while (it != us.end()) {
        //*it = 1;
        cout << *it << " ";
        ++it;
    }
    cout << endl;
    Print(us);

    Lotso::unordered_map<string, string> dict;
    dict.insert({"string", "字符串"});
    dict.insert({"string", "字符串"});
    dict.insert({"left", "左边"});
    dict.insert({"right", "右边"});
    // 修改
    dict["left"] = "左边，剩余";
    // 插入
    dict["insert"];
    // 插入 + 修改
    dict["map"] = "地图";
    for (auto& [k, v] : dict) {
        //k += 'x';
        //v += 'x';
        cout << k << ":" << v << endl;
    }
    return 0;
}

C++ 哈希表封装 myunordered_map 与 unordered_set：底层原理及实现

前言

一。源码及框架分析

二。核心设计思路：哈希表的泛型复用

2.1 哈希表模板参数设计

三。实现出复用哈希表的框架，并支持 insert

四。实现 iterator 和 map 支持 [] 的功能

4.1 迭代器实现：支持哈希桶遍历

4.2 map 支持 []

五。完整代码实现

5.1 HashTable.h

5.2 unordered_set.h

5.3 unordered_map.h

5.4 测试代码 (test.cpp)

结语

更多推荐文章

相关免费在线工具

C++ 哈希表封装 myunordered_map 与 unordered_set：底层原理及实现

前言

一。源码及框架分析

二。核心设计思路：哈希表的泛型复用

2.1 哈希表模板参数设计

三。实现出复用哈希表的框架，并支持 insert

四。实现 iterator 和 map 支持 [] 的功能

4.1 迭代器实现：支持哈希桶遍历

4.2 map 支持 []

五。完整代码实现

5.1 HashTable.h

5.2 unordered_set.h

5.3 unordered_map.h

5.4 测试代码 (test.cpp)

结语

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具