C++ 哈希表封装实现 unordered_set 与 unordered_map

简单了解一下源码：这里hashtable实现的是<V,K>结构，第一个参数V表示存储的数据类型，第二个参数K表示关键值key。

结构上依然是unordered_set和unordered_map使用同一个哈希表实现Key和Key/Value结构；unordered_set传<Key,Key>、unordered_map传<pair<Key,Value>,Key>。

我们在实现的时候依然按照<Key,Value>来实现。

二、封装实现unordered_set和unordered_map

1. 复用哈希表框架，实现insert

根据我们上篇博客实现的哈希表，我们要复用这个框架，写出来unordered_set和unordered_map的大致框架并支持insert操作。

这里我们就按照红黑树封装实现set和map的逻辑，Key参数就用K，Value参数就用V来实现；对于哈希表存储的数据类型，就用T来表示。

这里我们将数据类型用T来表示，就导致了我们在HashTable中不知道T是K还是pair<K,V>，所以我们要像实现set和map那样，用一个模版参数KeyOfT来让我们在HashTable中能通过T取到K。

那这个KeyOfT就只能从unordered_set和unordered_map中传（因为在unordered_set和unordered_map中才知道数据类型是K还是pair<K,V>）。

再重述一下为什么要用KeyOfT：因为我们不知道T到底是K还是pair<K,V>。 如果是K那可以直接进行转换成整型然后取模操作。 但如果是pair<K,V>，pair<K,V>是不支持转换成整型的，所以我们要实现KeyOfT通过T取出K，然后对K进行转化整型然后取模操作。

逻辑理清楚了，现在来代码（这里有了KeyOfT，那每次使用Key转整型并取模操作之前都要套上一层取Key操作）。

先来看我们的HashTable.h

template<class K>
struct HashFunc {
    size_t operator()(const K& key) {
        return (size_t)key;
    }
};

template<>
struct HashFunc<string> {
    size_t operator()(const string& str) {
        size_t ret = 1;
        int i = 1;
        for (auto& ch : str) {
            ret += ch * i;
            i++;
        }
        return ret;
    }
};

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

template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
class HashTable {
    typedef HashNode<K, T> Node;
public:
    HashTable() {
        _table.resize(__stl_next_prime(0));
    }
    bool insert(const T& data) {
        KeyOfT kof;
        if (find(kof(data)) != nullptr) return false;
        Hash hs;
        //扩容
        if ((double)_n / (double)_table.size() >= 1) {
            size_t newsize = __stl_next_prime(_table.size() + 1);
            vector<Node*> newtable;
            newtable.resize(newsize);
            for (int i = 0; i < _table.size(); i++) {
                Node* cur = _table[i];
                while (cur) {
                    Node* next = cur->_next;
                    size_t hash0 = hs(kof(cur->_data)) % newsize;
                    cur->_next = newtable[hash0];
                    newtable[hash0] = cur;
                    cur = next;
                }
            }
            _table.swap(newtable);
        }
        //插入
        size_t hash0 = hs(kof(data)) % _table.size();
        //头插到当前位置
        Node* newnode = new Node(data);
        newnode->_next = _table[hash0];
        _table[hash0] = newnode;
        _n++;
        return true;
    }
    Node* find(const K& key) {
        Hash hs;
        KeyOfT kof;
        size_t hashi = hs(key) % _table.size();
        Node* cur = _table[hashi];
        while (cur) {
            if (kof(cur->_data) == key) return cur;
            cur = cur->_next;
        }
        return nullptr;
    }
    bool erase(const K& key) {
        KeyOfT kof;
        for (int i = 0; i < _table.size(); i++) {
            Node* cur = _table[i];
            Node* prve = nullptr;
            while (cur) {
                if (key == kof(cur->_data)) {
                    if (prve == nullptr) {
                        _table[i] = cur->_next;
                    } else {
                        prve->_next = cur->_next;
                    }
                    delete cur;
                    --_n;
                    return true;
                }
                prve = cur;
                cur = cur->_next;
            }
        }
    }
    ~HashTable() {
        for (int i = 0; i < _table.size(); i++) {
            Node* cur = _table[i];
            while (cur) {
                Node* next = cur->_next;
                delete cur;
                cur = next;
            }
            _table[i] = nullptr;
        }
    }
private:
    vector<Node*> _table;
    size_t _n = 0;
};

再来看unordered_set.h

namespace HL {
template<class K>
class unordered_set {
    struct SetKeyOfT {
        const K& operator()(const K& key) {
            return key;
        }
    };
public:
    bool insert(const K& key) {
        return _hash.insert(key);
    }
private:
    HashTable<K, const K, SetKeyOfT> _hash;
};
void test_set() {
    unordered_set<int> ust;
    for (int i = 0; i <= 54; i++) {
        int x = rand();
        ust.insert(x);
    }
}
}

最后再来看unordered_map.h

namespace HL {
template<class K, class V>
class unordered_map {
    struct MapKeyOfT {
        const K& operator()(const pair<K, V>& kv) {
            return kv.first;
        }
    };
public:
    bool insert(const pair<K, V>& kv) {
        return _hash.insert(kv);
    }
private:
    HashTable<K, pair<const K, V>, MapKeyOfT> _hash;
};
void test_map() {
    unordered_map<int, int> ump;
    for (int i = 0; i <= 54; i++) {
        int x = rand();
        ump.insert({ x, i });
    }
}
}

2. 实现iterator迭代器，完成unordered_set和unordered_map的迭代器遍历

HashTable的迭代器

对于我们这里实现的链式结构的HashTable，它的迭代器显而易见是单向的；unordered_set和unordered_map的迭代器也是单向的。

这里我们HashTable的迭代器，和list大致是一样的，都是封装节点的指针，再通过运算符重载实现；让迭代器像指针一种访问。

对于HashTable的迭代器中==、!=、*、->，实现这些运算符重载都好说；那operator++呢？

那operator++如何实现呢？我们迭代器是对节点指针的封装，但是我们节点HashNode中只存放了数据_data和下一个位置的指针_next。如果我们当前节点下一个位置不为空（当前桶（位置）还有节点），那就直接指向下一个节点即可。那如果我们当前位置下一个位置为空（当前桶遍历完了），我们就要想办法找大下一个不为空的桶。

那如何去找下一个桶呢？如果我们单纯的对节点的指针进行封装，显然是不能解决这个问题的；参照源码我们可以发现，在iterator中除了节点的指针，还存在一个哈希表对象的指针。

有了哈希表对象的指针，我们走完当前桶那就很容易找到下一个桶了。

这里我们找到下一个桶位置需要用到KeyOfT进行取Key操作，也要用到Hash对Key取模操作；所以我们iterator的模版参数就不只是原来的template<class T,classRef,class Ptr>了。而是template<class K,class T,classRef,class Ptr,class KeyOfT,class Hash>。

那现在问题又出现了：我们HashIterator是定义在HashTable前面的，而我们HashIterator中还要使用HashTable，并且在HashIterator中还用访问HashTable的私有成员，那怎么办呢？**首先我们要对HashTable进行前置声明，让我们在HashIterator中知道有HashTable这个类。**然后就是友元，让HashIterator成为HashTable类的友元。

const迭代器

对于const迭代器实现起来就好很多了，只需要在HashIterator第二和第三个参数位置传const T&,const T*即可。

那这样我们大体就清楚了，现在来实现代码

//前置声明
template<class K, class T, class KeyOfT, class Hash>
class HashTable;

template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
class HashIterator {
    typedef HashNode<T> Node;
    typedef HashTable<K, T, KeyOfT, Hash> HT;
    typedef HashIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;
public:
    bool operator==(const Self& it) {
        return _node == it._node;
    }
    bool operator!=(const Self& it) {
        return _node != it._node;
    }
    Ref operator*() {
        return _node->_data;
    }
    Ptr operator->() {
        return &_node->_data;
    }
    Self& operator++() {
        if (_node->_next != nullptr) {
            _node = _node->_next;
        } else {
            //当前桶走完了，找到下一个桶
            KeyOfT kof;
            Hash hs;
            size_t hashi = hs(kof(_node->_data)) % _ht->_table.size();
            hashi++;
            while (hashi < _ht->_table.size()) {
                if (_ht->_table[hashi]) {
                    _node = _ht->_table[hashi];
                    break;
                }
                hashi++;
            }
            if (hashi == _ht->_table.size()) _node = nullptr;
        }
        return *this;
    }
    HashIterator(Node* node, const HT* ht) : _node(node), _ht(ht) {}
private:
    Node* _node;
    const HT* _ht;
};

当然不要忘了在HashTable中声明友元

这里就只展示出了HashTable中新增的部分。

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 class HashIterator;
public:
    typedef HashIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;
    typedef HashIterator<K, T, const T&, const T*, KeyOfT, Hash> ConstIterator;
    //迭代器部分
    Iterator begin() {
        //找到第一个迭代器的位置
        for (int i = 0; i < _table.size(); i++) {
            if (_table[i] != nullptr) return { _table[i], this };
        }
        return { nullptr, this };
    }
    Iterator end() {
        return { nullptr, this };
    }
    ConstIterator begin() const {
        //找到第一个迭代器的位置
        for (int i = 0; i < _table.size(); i++) {
            if (_table[i] != nullptr) return { _table[i], this };
        }
        return { nullptr, this };
    }
    ConstIterator end() const {
        return { nullptr, this };
    }
};

unordered_set和unordered_map迭代器

对于unordered_set和unordered_map迭代器对HashTable的迭代器进行复用即可。

unordered_set迭代器

typedef typename HashTable<K, const K, SetKeyOfT>::Iterator iterator;
typedef typename HashTable<K, const K, SetKeyOfT>::ConstIterator const_iterator;
iterator begin() {
    return _hash.begin();
}
iterator end() {
    return _hash.end();
}
const_iterator begin() const {
    return _hash.begin();
}
const_iterator end() const {
    return _hash.end();
}

unordered_map迭代器

typedef typename HashTable<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;
typedef typename HashTable<K, pair<const K, V>, MapKeyOfT>::ConstIterator const_iterator;
iterator begin() {
    return _hash.begin();
}
iterator end() {
    return _hash.end();
}
const_iterator begin() const {
    return _hash.begin();
}
const_iterator end() const {
    return _hash.end();
}

3. 实现unordered_map的operator[]

对于unordered_map的operator[]，其功能和map的operator[]一样，如果key值存在就返回key对应的value的引用；如果key不存在就先插入key（value是缺省值），再返回value的引用。

那我们要实现operator[]就要依赖于insert，所以我们要对insert进行修改（将其返回值修改为pair<Iterator,bool>。这里我们insert又依赖于find判断数据是否存在，所以对find也要进行一点点修改）。

HashTable的insert和find：

//bool insert(const T& data)
pair<Iterator, bool> insert(const T& data) {
    KeyOfT kof;
    //if (find(kof(data)) != nullptr)// return false;
    Iterator it = find(kof(data));
    if (it != end()) return { it, false };
    Hash hs;
    //扩容
    if ((double)_n / (double)_table.size() >= 1) {
        size_t newsize = __stl_next_prime(_table.size() + 1);
        vector<Node*> newtable;
        newtable.resize(newsize);
        for (int i = 0; i < _table.size(); i++) {
            Node* cur = _table[i];
            while (cur) {
                Node* next = cur->_next;
                size_t hash0 = hs(kof(cur->_data)) % newsize;
                cur->_next = newtable[hash0];
                newtable[hash0] = cur;
                cur = next;
            }
        }
        _table.swap(newtable);
    }
    //插入
    size_t hash0 = hs(kof(data)) % _table.size();
    //头插到当前位置
    Node* newnode = new Node(data);
    newnode->_next = _table[hash0];
    _table[hash0] = newnode;
    _n++;
    //return true;
    return {{newnode, this}, true};
}

//Node* find(const K& key)
Iterator find(const K& key) {
    Hash hs;
    KeyOfT kof;
    size_t hashi = hs(key) % _table.size();
    Node* cur = _table[hashi];
    while (cur) {
        if (kof(cur->_data) == key) return { cur, this };//return cur;
        cur = cur->_next;
    }
    //return nullptr;
    return { nullptr, this };
}

unordered_set的insert：

//bool insert(const K& key)
pair<iterator, bool> insert(const K& key) {
    return _hash.insert(key);
}

unordered_map的insert和operator[]：

//bool insert(const pair<K, V>& kv)
pair<iterator, bool> insert(const pair<K, V>& kv) {
    return _hash.insert(kv);
}
V& operator[](const K& key) {
    pair<iterator, bool> p = insert({ key, V() });
    return p.first->second;
}

4. 构造函数和析构函数

这里我们HashTable是写了构造函数和析构函数的，而unordered_set和unordered_map都只是对HashTable的封装复用，所以这里不需要写unordered_set和unordered_map的析构函数的。

三、简单总结

这里erase函数也是直接复用HashTable的erase函数，这里就不演示了。

简单总结一下：这里我们通过复用HashTable，实现了unordered_set和unordered_map的insert、find和 迭代器以及unordered_map的operator[]。首先就是复用HashTable，实现unordered_set和unordered_map的框架；然后实现HashTable的迭代器Iterator，并完成复用实现unordered_set和unordered_map的iterator；接着就是unordered_map的operator[]操作；最后呢就是构造函数和析构函数这些（虽然不需要写unordered_set的unordered_map）。这里对于size、empty等这些简单的方法这里并没有实现（也是直接复用的好吧）。

到这里本篇内容就结束了，希望对你有所帮助。