使用Hash桶封装unorder_map和unorder_set

[bosthhe1]

由于线性插入和二次插入都会引发线性冲突和二次冲突，所以我选择的时以链表的形式

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<vector>
#include<iostream>
#include<assert.h>
using namespace std;

namespace hxh
{
    template<class T>
    struct Hash
    {
        Hash<T>* next;
        T _data;
        Hash(const T& data)
        {
            next = nullptr;
            _data = data;
        }
        Hash()
            :next(nullptr)
        {}
    };
    template<class K>
    struct tmp
    {
        size_t operator()(const K& key)
        {
            return (size_t)key;
        }
    };
    template<>
    struct tmp<string>
    {
        size_t operator()(const string& key)
        {
            size_t k = 0;
            for (size_t i = 0; i < key.size(); i++)
            {
                k *= 31;
                k += key[i];
            }
            return k;
        }
    };
    template<class K, class T, class KeyOfT, class HashFunc>
    class ListHash;//在这里加入声明，解决互相引用的问题
    template<class K,class T,class Sef,class Ptr,class KeyOfT,class HashFunc>
    struct LHIterator
    {
        typedef LHIterator<K ,T, Sef, Ptr, KeyOfT, HashFunc> Self;

        Hash<T>* _node;
        ListHash<K, T, KeyOfT, HashFunc>* _LH;//需要注意这里互相引用的问题
               //由于需要位置关系图来控制迭代器，所以我们需要拿到原指针数组的指针，所以需要浅拷贝拿到原指针数组的指针
        LHIterator(Hash<T>* node,ListHash<K, T, KeyOfT, HashFunc>* LH)
            :_node(node)
            ,_LH(LH)
        {}
        Sef operator*()
        {
            return _node->_data;
        }
        Ptr operator->()
        {
            return &_node->_data;
        }
        bool operator!=(const Self& k)const
        {
            return _node != (k._node);
        }
        bool operator==(const Self& k)const
        {
            return _node == (k._node);
        }
        Self& operator++()
        {
            KeyOfT kt;
            HashFunc tmp;
            if (_node->next != nullptr)
                _node = _node->next;
            else
            {
                size_t index = tmp(kt(_node->_data)) % _LH->arr.size();
                while (++index < _LH->arr.size())
                {
                    if (_LH->arr[index] != nullptr)
                    {
                        _node = _LH->arr[index];
                        break;
                    }
                }
                if (index ==_LH->arr.size())
                    _node = nullptr;
            }
            return *this;
        }
    };
    template<class K, class T,class KeyOfT,class HashFunc>
    class ListHash
    {
        friend LHIterator<K, T, T&, T*, KeyOfT, HashFunc>;
    public:
        typedef Hash<T> Hash;
        typedef LHIterator<K, T, T&, T*, KeyOfT, HashFunc> iterator;//需要注意这里互相引用的问题
        iterator begin()
        {
            for (size_t i = 0; i < _size; i++)
            {
                if (arr[i] != nullptr)
                    return iterator(arr[i],this);//由于第二个参数是原指针数组的指针，所以传this刚刚好
            }
            return iterator(nullptr, this);
        }
        iterator end()
        {
            return iterator(nullptr,this);
        }
        Hash* find(const K& k)
        {
            if (arr.size() == 0)
                return nullptr;
            KeyOfT kt;
            tmp<K> tmp1;
            size_t size = tmp1(k) % arr.size();
            Hash* tmp = arr[size];
            while (tmp&&tmp1(kt(tmp->_data)) != tmp1(k))
            {
                tmp = tmp->next;
            }
            return tmp;
        }
        bool earse(const K& k)
        {
            assert(arr.size() != 0);
            tmp<K> tmp1;
            size_t size = tmp1(k) % arr.size();
            Hash* prev = nullptr;
            Hash* tmp = arr[size];
            KeyOfT kt;
            while (tmp&&tmp1(kt(tmp->_data)) != tmp1(k))
            {
                prev = tmp;
                tmp = tmp->next;
            }
            if (tmp == nullptr)
                return false;
            else
            {
                if (prev == nullptr)
                {
                    arr[size] = tmp->next;
                }
                else
                {
                    prev->next = tmp->next;
                }

                delete tmp;
                _size--;
                return true;
            }
        }
        pair<iterator, bool> insert(const T& data)
        {
            KeyOfT kt;
            Hash* node = find(kt(data));
            if (arr.size() != 0 && node != nullptr)
                return make_pair(iterator(node,this), false);
            if (arr.size() == 0||_size/arr.size()==1)
            {
                size_t newsize = _size == 0 ? 10 : _size * 2;
                vector<Hash*> arr1;
                arr1.resize(newsize);
                for (auto& e : arr)
                {
                    if (e != nullptr)
                    {
                        Hash* cur = e;
                        e = nullptr;
                        while (cur)
                        {
                            tmp<K> tmp1;
                            Hash* newNode = cur;
                            cur = cur->next;
                            size_t size = tmp1(kt(newNode->_data)) % arr1.size();
                            newNode->next = arr1[size];
                            arr1[size] = newNode;
                        }
                    }
                }
                arr.swap(arr1);
            }
            tmp<K> tmp1;
            Hash* newNode = new Hash(data);
            size_t size = tmp1(kt(newNode->_data)) % arr.size();
            newNode->next = arr[size];
            arr[size] = newNode;
            _size++;
            return make_pair(iterator(arr[size], this), true);
        }
    private:
        vector<Hash*> arr;
        size_t _size = 0;
    };
};

[bosthhe1]

set.h

#define _CRT_SECURE_NO_WARNINGS 1
#include"ListHash.h"
namespace hxh
{
    template<class K>
    class unordered_set
    {
        struct SetKeyOfT
        {
            const K& operator()(const K& key)
            {
                return key;
            }
        };
        public:
            const K& operator[](const K& key)
            {
                return *((ht.insert(key)).first);
            }
            typedef typename ListHash<K, K, SetKeyOfT, tmp<K>>::iterator Siterator;
            Siterator begin()
            {
                return ht.begin();
            }
            Siterator end()
            {
                return ht.end();
            }
            pair<Siterator, bool> insert(const K& key)
            {
                return ht.insert(key);
            }
        private:
            ListHash<K, K, SetKeyOfT,tmp<K>> ht;
    };
}

[bosthhe1]

map.h

#define _CRT_SECURE_NO_WARNINGS 1
#include"ListHash.h"
namespace hxh
{
    template<class K, class V>
    class unordered_map
    {
        struct MapKeyOfT
        {
            const K& operator()(const pair<K,V>& kv)
            {
                return kv.first;
            }
        };
    public:
        typedef typename ListHash<K, pair<K, V>, MapKeyOfT, tmp<K>>::iterator Miterator;
        V& operator[](const pair<K, V>& _kv)
        {
            return (*((kv.insert(_kv)).first)).second;
        }
        Miterator begin()
        {
            return kv.begin();
        }
        Miterator end()
        {
            return kv.end();
        }
        pair<Miterator, bool> insert(const pair<K, V>& _kv)
        {
            return kv.insert(_kv);
        }
    private:
        ListHash<K, pair<K, V>, MapKeyOfT,tmp<K>> kv;
    };
}