哈希结构的实现

unordered系列关联式容器

哈希的简介

哈希表闭散列实现

哈希表开散列实现

用哈希表来封装map和set

位图

布隆过滤器与哈希切割

全部代码

unordered系列关联式容器

unordered系列关联式容器有四种，****这里主要对unordered_map和unordered_set这两种容器进行介绍

unordered_map

unordered_map是存储<key, value>键值对的关联式容器，其允许通过keys快速的索引到与其对应的value

在内部,unordered_map没有对<kye, value>按照任何特定的顺序排序

unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低

unordered_maps实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问value

unordered_set

unordered_set和unordered_map在性质上差不多，因为底层结构是一致的，都是哈希结构，区别在与，unordered_set不支持[]，因为它存储的是key与value相同，所以无需支持[]

哈希的简介

概念

如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素

哈希函数有多种，这里采用除留余数法

哈希冲突

比如14和4取模后都是4，而4对应的位置只能存储一个数字，那么就出现了哈希冲突，而解决哈希冲突的常见两种方法有闭散列和开散列

哈希表闭散列实现

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去

寻找下一空位置有线性探测和二次探测两种

线性探测

从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止

** 二次探测**

从发生冲突的位置开始，跨越探测，直到寻找到下一个空位置为止

index是哈希表的下标

首先因为有闭散列和开散列两种，所以采用命名空间的形式来防止命名冲突

然后定义一个枚举类型，用来判断该下标的空间的状态，是存在数据，还是删除过数据，或者没有数据，便于插入，删除，及查找数据

封装节点，开始必然为每个下标所在的空间必然为空状态，所以初始化为空状态

因为要是除留取余法，必然要是整数，所以还需要借助仿函数来实现

内置类型

string类型

string类型转整形，可以将字符串的每个字母的ASCII码值加起来，但要是只是顺序不同，那总数也会相同，出现哈希冲突，为了尽量减少哈希冲突，就有了下图的方法，其中31是累乘因子

string类型有下列两种写法，任选其一即可

**对于其它自定义类型，比如日期，则按照特定方式取整即可 **

哈希表同样采用模板的形式实现，另外私有成员有中的_n是有效数据个数，便于后续插入数据扩容使用

查找数据

如果表为空，则直接返回nullptr即可

首先用待查找的key模表的长度取模作为待查找的初始下标，然后一直往后查找，同时往后走时，最后别忘了再取模一次，因为可能会存在初始下标空间的前面空间，找不到时，则直接返回nullptr

删除数据

首先先查找数据，找到数据了有效数据就减少一个，然后将那个节点的状态置为删除状态，删除成功返回true即可，没找到就表示删除失败，返回false

插入数据

首先先查找数据，如果存在，就表示待插入的数据已经有了，所以无需再插入，返回false即可

根据有效数据个数，得到负载因子，如果负载因子大于等于0.7则表示需要扩容了，初始没有空间时，也一样需要扩容

负载因子越小，冲突概率越低，效率越高，空间浪费越多

负载因子越大，冲突概率越高，效率越低，空间浪费越少

如果是初始时则开10个空间，其它情况则直接开原来的2倍空间

创建一个新表，开辟新空间大小的空间，再将其数据拷贝到新表，然后将新表对象中的vector成员与this对象中的vector成员交换即可

如果不需要开辟新空间

则先将key取模，找到对应的下标，如果有空间，则直接插入数据，没有，则继续往后面找，与find()类似，最后有效数据+1，返回true即可

闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷

哈希表开散列实现

概念

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中，开散列中每个桶中放的都是发生哈希冲突的元素，如下图

封装节点，其实就是单链表的节点封装

私有成员与闭散列一致，同时，还是采用除留去余法，所以会用到仿函数，与上面闭散列一致

查找数据

如果哈希表为空，则直接返回nullptr

找到待查找的数据节点的下标，以及声明一个局部变量来保存这条链的头节点

从头开始往后找，找到了返回节点地址，没找到返回nullptr

删除数据

如果哈希表为空，返回false，表示删除失败

找到待删除数据节点的那条链的头节点

如果找到了，则分为两种情况，如果就是头节点，那就直接头删，否则就中间删除

如果没找到，则继续往后面找，找不到则返回false，表示删除失败

** 插入数据**

首先先查找数据，如果存在，就表示待插入的数据已经有了，所以无需再插入，返回false即可

如果负载因子等于1时，则需要扩容，初始开空间时开10个空间，其余情况开原来的2倍空间

然后将原表的数据按头插拷贝到新表，将原表每条链的表头置空，最后再交换this对象的vector成员与新表的vector成员即可

如果不需要扩容，则直接头插，然后将有效数据个数+1，再返回true即可

为了减少哈希冲突，每次扩容后的空间大小都为素数

用哈希表来封装map和set

改善哈希表

因为既要封装map，又要封装set，所以将数据类型从pair类型变为了T类型

迭代器

**因为会用到哈希表，所以提前声明一下 **

因为要封装map和set，所以多加了一个模板参数KeyOfT，采用了仿函数

因为map和set存储的数据不同，一个是pair<key,value>，一个是key所以对*和对->都要重载

判断相不相等，比较的是节点的地址相不相等

重载++运算符

如果这条链上还有节点，即没有遇到nullptr，则直接往后走即可

如果为nullptr，则从哈希表的下一个元素开始找，比如下图，走完11后，则继续往后面走，下一个元素表头为空，所以就走到了13，不为nullptr，则跳出循环

如果是循环自动结束的，即走完整个哈希表了，则直接置nullptr即可

如果是break出来的，则直接返回到那个节点，比如上述所说的13

拷贝构造

别忘了写一个默认构造函数，因为有了拷贝构造之后，编译器不会默认生成了

这里采用的是头插法，所以顺序会有变化

重载赋值运算符

将实参传给形参时会有一次拷贝构造，所以只需将this对象的两个成员与形参的交换即可

析构函数

从哈希表第一个元素开始销毁节点，直到走完哈希表结束

初始节点

如果哈希表第一个元素的头节点不为nullptr，则它就是初始节点，否则直接返回nullptr的迭代器

结尾节点，即nullptr

重载[]运算符

[]可查找value，也可修改或插入

位图

位图的作用：数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在，比如在一堆数据中找5在不在，数据很多时，可以开辟整形最大值那么大的以bit为单位的空间，然后一个整数对应一个比特位，如果5对应的比特位是1，那就在这堆数据中，是0就不在

1byte=8bit，所以开空间数如下图

将某个bit位置为1

将某个bit位置为0

检查某个bit位是否为1

0为假，非0为真

位图：节省空间，效率高，但只能处理整数

布隆过滤器与哈希切割

概念

布隆过滤器是由布隆在1970年提出的一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”，它是用多个哈希函数，将一个数据映射到位图结构中。既可以提升查询效率，也可以节省大量的内存空间

作用：用来解决字符串，自定义类型对象在不在的问题

如果采用将字符串转整数，即将字符串的各个字符加起来取模作为下标，那就可能会存在哈希冲突，比如下图中eat和ate

这种方式，判断不在是准确的，比如eat和ate那个位置的比特位为0，则eat肯定不在，只是判断在会存在误判

解决方式

将一个元素用多个哈希函数映射到一个位图中，比如ate，只要三个种有一个bit位为0，则就表示ate不在，降低了误判率

这里以哈希函数中三个不同的哈希函数为例模板参数

//hashTable-副本
#pragma once
#include<vector>

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

//特化
template<>
struct Hash< string >
{
    size_t operator()(const string& s)
    {
        //BKDR
        size_t value = 0;
        for (auto ch : s)
        {
            value *= 31;
            value += ch;
        }
        return value;
    }
};

namespace CloseHash
{
    enum Status
    {
        EXIST,
        EMPTY,
        DELETE
    };

    template<class K,class V>
    struct HashData
    {
        pair<K, V> _kv;
        Status _status = EMPTY;
    };

    struct HashStr
    {
        size_t operator()(const string& s)
        {
            //BKDR
            size_t value = 0;
            for (auto ch : s)
            {
                value *= 31;
                value += ch;
            }
            return value;
        }
    };

    template<class K,class V,class HashFunc = Hash<K>>
    class HashTable
    {
    public:
        bool Erase(const K& key)
        {
            HashData<K, V>* ret = Find(key);
            if (ret == nullptr)
            {
                return false;
            }
            else
            {
                --_n;
                ret->_status = DELETE;
                return true;
            }
        }

        HashData<K, V>* Find(const K& key)
        {
            if (_tables.size() == 0)
            {
                return nullptr;
            }

            HashFunc hf;
            size_t start = hf(key) % _tables.size();
            size_t i = 0;
            size_t index = start;
            //线性探测 or 二次探测
            while (_tables[index]._status != EMPTY)
            {
                if (_tables[index]._kv.first == key && _tables[index]._status == EXIST)
                {
                    return &_tables[index];
                }

                ++i;
                //index = start + i*i;
                index = start + i;

                index %= _tables.size();
            }

            return nullptr;
        }

        bool Insert(const pair<K, V>& kv)
        {
            HashData<K, V>* ret = Find(kv.first);
            if (ret)
            {
                return false;
            }

            //负载因子到0.7，就扩容
            //负载因子越小，冲突概率越低，效率越高，空间浪费越多
            //负载因子越大，冲突概率越高，效率越低，空间浪费越少
            if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7)
            {
                //扩容
                size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
                //vector<HashData<K,V>> newTables;
                //newTables.resize(newSize);
                //遍历原表，把原表中的数据，重新按newSize映射到新表
                //for(size_t i = 0;i < _tables.size();++i)
                //{
                    //
                //}
                //_tables.swap(newTables);
                HashTable<K, V, HashFunc> newHT;
                newHT._tables.resize(newSize);
                for (size_t i = 0; i < _tables.size(); ++i)
                {
                    if (_tables[i]._status == EXIST)
                    {
                        newHT.Insert(_tables[i]._kv);
                    }
                }

                _tables.swap(newHT._tables);
            }

            HashFunc hf;
            size_t start = hf(kv.first) % _tables.size();
            size_t i = 0;
            size_t index = start;
            //线性探测 or 二次探测
            while (_tables[index]._status == EXIST)
            {
                ++i;
                //index = start + i * i;
                index = start + i;

                index %= _tables.size();
            }

            _tables[index]._kv = kv;
            _tables[index]._status = EXIST;
            ++_n;

            return true;
        }
    private:
        vector<HashData<K, V>> _tables;
        size_t _n = 0;//有效数据个数
    };

    void TestHashTable1()
    {
        //HashTable<int,int,Hash<int>> ht;
        HashTable<int, int> ht;

        int a[] = { 2,12,22,32,42,52,62 };
        for (auto e : a)
        {
            ht.Insert(make_pair(e, e));
        }

        ht.Insert(make_pair(72, 72));
        ht.Insert(make_pair(72, 72));
        ht.Insert(make_pair(-1, -1));
        ht.Insert(make_pair(-999, -999));

        Hash<int> hs;
        cout << hs(9) << endl;
        cout << hs(-9) << endl;

        cout << ht.Find(12) << endl;
        ht.Erase(12);
        cout << ht.Find(12) << endl;
    }

    struct Date
    {

    };

    struct HashDate
    {
        size_t operator()(const Date& d)
        {
            //...
        }
    };

    void TestHashTable2()
    {
        HashStr hs;
        cout << hs("sort") << endl;
        cout << hs("insert") << endl;
        cout << hs("eat") << endl;
        cout << hs("ate") << endl;
        cout << hs("abcd") << endl;
        cout << hs("aadd") << endl;

        HashTable<string, string> ht;
        ht.Insert(make_pair("sort", "排序"));
        ht.Insert(make_pair("string", "字符串"));

        //当key是一个定义类型时，需要配置一个仿函数，将key转成整形
        HashTable<Date, string, HashDate> htds;
    }
}

namespace LinkHash
{
    template<class K,class V>
    struct HashNode
    {
        pair<K, V> _kv;
        HashNode<K, V>* _next;

        HashNode(const pair<K, V>& kv):_kv(kv),_next(nullptr)
        {}
    };

    template<class K,class V,class HashFunc = Hash<K>>
    class HashTable
    {
        typedef HashNode<K, V> Node;
    public:

        bool Erase(const K& key)
        {
            if (_tables.empty())
            {
                return false;
            }

            HashFunc hf;
            size_t index = hf(key) % _tables.size();
            Node* prev = nullptr;
            Node* cur = _tables[index];
            while (cur)
            {
                if (cur->_kv.first == key)
                {
                    if (prev == nullptr) //头删
                    {
                        _tables[index] = cur->_next;
                    }
                    else //中间删除
                    {
                        prev->_next = cur->_next;
                    }

                    --_n;

                    delete cur;

                    return true;
                }
                else
                {
                    prev = cur;
                    cur = cur->_next;
                }
            }

            return false;
        }

        Node* Find(const K& key)
        {
            if (_tables.empty())
            {
                return nullptr;
            }

            HashFunc hf;
            size_t index = hf(key) % _tables.size();
            Node* cur = _tables[index];
            while (cur)
            {
                if (cur->_kv.first == key)
                {
                    return cur;
                }
                else
                {
                    cur = cur->_next;
                }
            }

            return nullptr;
        }

        bool Insert(const pair<K, V>& kv)
        {
            Node* ret = Find(kv.first);
            if (ret)
                return false;

            HashFunc hf;
            if (_n == _tables.size())
            {
                size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
                //...
                vector<Node*> newTables;
                newTables.resize(newSize);
                for (size_t i = 0; i < _tables.size(); ++i)
                {
                    Node* cur = _tables[i];
                    while (cur)
                    {
                        Node* next = cur->_next;

                        size_t index = hf(cur->_kv.first) % newTables.size();
                        //头插
                        cur->_next = newTables[index];
                        newTables[index] = cur;

                        cur = next;
                    }

                    _tables[i] = nullptr;
                }

                _tables.swap(newTables);
            }
            size_t index = hf(kv.first) % _tables.size();
            Node* newnode = new Node(kv);
            //头插
            newnode->_next = _tables[index];
            _tables[index] = newnode;

            ++_n;
            return true;
        }

    private:
        /*struct Data
        {
            forward_list<T> _list;
            set<T> _rbtree;
            size_t len;
        };
        vector<Data> _table;*/
        vector<Node*> _tables;

        size_t _n = 0;//有效数据的个数
    };

    void TestHashTable()
    {
        int a[] = { 4,24,14,7,37,27,57,67,34,14,54 };
        HashTable<int, int> ht;
        for (auto e : a)
        {
            ht.Insert(make_pair(e, e));
        }

        ht.Insert(make_pair(84, 84));
    }
};

//hashTable
#pragma once
#include<vector>
#include<string>

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

//特化
template<>
struct Hash< string >
{
    size_t operator()(const string& s)
    {
        //BKDR
        size_t value = 0;
        for (auto ch : s)
        {
            value *= 31;
            value += ch;
        }
        return value;
    }
};

namespace CloseHash
{
    enum Status
    {
        EXIST,
        EMPTY,
        DELETE
    };

    template<class K, class V>
    struct HashData
    {
        pair<K, V> _kv;
        Status _status = EMPTY;
    };

    //struct HashStr
    //{
    //    size_t operator()(const string& s)
    //    {
    //        //BKDR
    //        size_t value = 0;
    //        for (auto ch : s)
    //        {
    //            value *= 31;
    //            value += ch;
    //        }
    //        return value;
    //    }
    //};

    template<class K, class V, class HashFunc = Hash<K>>
    class HashTable
    {
    public:
        bool Erase(const K& key)
        {
            HashData<K, V>* ret = Find(key);
            if (ret == nullptr)
            {
                return false;
            }
            else
            {
                --_n;
                ret->_status = DELETE;
                return true;
            }
        }

        HashData<K, V>* Find(const K& key)
        {
            if (_tables.size() == 0)
            {
                return nullptr;
            }

            HashFunc hf;
            size_t start = hf(key) % _tables.size();
            size_t i = 0;
            size_t index = start;
            //线性探测 or 二次探测
            while (_tables[index]._status != EMPTY)
            {
                if (_tables[index]._kv.first == key && _tables[index]._status == EXIST)
                {
                    return &_tables[index];
                }

                ++i;
                //index = start + i*i;
                index = start + i;

                index %= _tables.size();
            }

            return nullptr;
        }

        bool Insert(const pair<K, V>& kv)
        {
            HashData<K, V>* ret = Find(kv.first);
            if (ret)
            {
                return false;
            }

            //负载因子到0.7，就扩容
            //负载因子越小，冲突概率越低，效率越高，空间浪费越多
            //负载因子越大，冲突概率越高，效率越低，空间浪费越少
            if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7)
            {
                //扩容
                size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
                //vector<HashData<K,V>> newTables;
                //newTables.resize(newSize);
                //遍历原表，把原表中的数据，重新按newSize映射到新表
                //for(size_t i = 0;i < _tables.size();++i)
                //{
                    //
                //}
                //_tables.swap(newTables);
                HashTable<K, V, HashFunc> newHT;
                newHT._tables.resize(newSize);
                for (size_t i = 0; i < _tables.size(); ++i)
                {
                    if (_tables[i]._status == EXIST)
                    {
                        newHT.Insert(_tables[i]._kv);
                    }
                }

                _tables.swap(newHT._tables);
            }

            HashFunc hf;
            size_t start = hf(kv.first) % _tables.size();
            size_t i = 0;
            size_t index = start;
            //线性探测 or 二次探测
            while (_tables[index]._status == EXIST)
            {
                ++i;
                //index = start + i * i;
                index = start + i;

                index %= _tables.size();
            }

            _tables[index]._kv = kv;
            _tables[index]._status = EXIST;
            ++_n;

            return true;
        }
    private:
        vector<HashData<K, V>> _tables;
        size_t _n = 0;//有效数据个数
    };

    void TestHashTable1()
    {
        //HashTable<int,int,Hash<int>> ht;
        HashTable<int, int> ht;

        int a[] = { 2,12,22,32,42,52,62 };
        for (auto e : a)
        {
            ht.Insert(make_pair(e, e));
        }

        ht.Insert(make_pair(72, 72));
        ht.Insert(make_pair(72, 72));
        ht.Insert(make_pair(-1, -1));
        ht.Insert(make_pair(-999, -999));

        Hash<int> hs;
        cout << hs(9) << endl;
        cout << hs(-9) << endl;

        cout << ht.Find(12) << endl;
        ht.Erase(12);
        cout << ht.Find(12) << endl;
    }

    struct Date
    {

    };

    struct HashDate
    {
        size_t operator()(const Date& d)
        {
            //...
        }
    };

    void TestHashTable2()
    {
        /*HashStr hs;
        cout << hs("sort") << endl;
        cout << hs("insert") << endl;
        cout << hs("eat") << endl;
        cout << hs("ate") << endl;
        cout << hs("abcd") << endl;
        cout << hs("aadd") << endl;*/

        HashTable<string, string> ht;
        ht.Insert(make_pair("sort", "排序"));
        ht.Insert(make_pair("string", "字符串"));

        //当key是一个定义类型时，需要配置一个仿函数，将key转成整形
        HashTable<Date, string, HashDate> htds;
    }
}

namespace LinkHash
{
    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 HashFunc>
    class HashTable;

    template<class K,class T,class Ref,class Ptr,class KeyOfT,class HashFunc>
    struct __HTIterator
    {
        typedef HashNode<T> Node;
        typedef __HTIterator<K, T, Ref, Ptr, KeyOfT, HashFunc> Self;

        Node* _node;
        HashTable<K, T, KeyOfT, HashFunc>* _pht;

        __HTIterator(Node* node,HashTable<K,T,KeyOfT,HashFunc>* 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;
                HashFunc hf;
                size_t index = hf(kot(_node->_data)) % _pht->_tables.size();
                ++index;
                //找下一个不为空的值
                while (index < _pht->_tables.size())
                {
                    if (_pht->_tables[index])
                    {
                        break;
                    }
                    else
                    {
                        ++index;
                    }
                }

                //表走完了，都没有找到下一个桶
                if (index == _pht->_tables.size())
                {
                    _node = nullptr;
                }
                else
                {
                    _node = _pht->_tables[index];
                }
            }
            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 HashFunc>
    class HashTable
    {
        typedef HashNode<T> Node;
        
        template<class K,class T,class Ref,class Ptr,class KeyOfT,class HashFunc>
        friend struct __HTIterator;
        typedef HashTable<K, T, KeyOfT, HashFunc> self;
    public:
        typedef __HTIterator<K, T, T&, T*, KeyOfT, HashFunc> iterator;

        HashTable()
        {}
        //显示指定编译器去生成默认构造函数
        //HashTable() = default;

        HashTable(const self& ht)
        {
            _tables.resize(ht._tables.size());
            for (size_t i = 0; i < ht._tables.size(); ++i)
            {
                Node* cur = ht._tables[i];
                while (cur)
                {
                    Node* copy = new Node(cur->_data);
                    copy->_next = _tables[i];
                    _tables[i] = copy;

                    cur = cur->_next;
                }
            }
        }

        //ht1 = ht2
        self& operator=(self copy)
        {
            swap(_n, copy._n);
            _tables.swap(copy._tables);
            return *this;
        }

        ~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;
            }
        }

        iterator begin()
        {
            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);
        }

        bool Erase(const K& key)
        {
            if (_tables.empty())
            {
                return false;
            }

            HashFunc hf;
            size_t index = hf(key) % _tables.size();
            Node* prev = nullptr;
            Node* cur = _tables[index];
            KeyOfT kot;
            while (cur)
            {
                if (kot(cur->_data) == key)
                {
                    if (prev == nullptr) //头删
                    {
                        _tables[index] = cur->_next;
                    }
                    else //中间删除
                    {
                        prev->_next = cur->_next;
                    }

                    --_n;

                    delete cur;

                    return true;
                }
                else
                {
                    prev = cur;
                    cur = cur->_next;
                }
            }

            return false;
        }

        iterator Find(const K& key)
        {
            if (_tables.empty())
            {
                return end();
            }

            HashFunc hf;
            size_t index = hf(key) % _tables.size();
            Node* cur = _tables[index];
            KeyOfT kot;
            while (cur)
            {
                if (kot(cur->_data) == key)
                {
                    return iterator(cur,this);
                }
                else
                {
                    cur = cur->_next;
                }
            }

            return end();
        }

        size_t GetNextPrime(size_t num)
        {
            static const unsigned long __stl_prime_list[28] =
            {
                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
            };

            for(size_t i = 0;i < 28;++i)
            {
                if (__stl_prime_list[i] > num)
                {
                    return __stl_prime_list[i];
                }
            }
            return __stl_prime_list[27];
        }

        pair<iterator,bool> Insert(const T& data)
        {
            KeyOfT kot;
            iterator ret = Find(kot(data));
            if (ret != end())
                return make_pair(ret,false);

            HashFunc hf;

            //负载因子 == 1时扩容
            if (_n == _tables.size())
            {
                //size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
                //...
                size_t newSize = GetNextPrime(_tables.size());
                /*if (newSize == _tables.size())
                {
                    break;
                }*/
                vector<Node*> newTables;
                newTables.resize(newSize);
                for (size_t i = 0; i < _tables.size(); ++i)
                {
                    Node* cur = _tables[i];
                    while (cur)
                    {
                        Node* next = cur->_next;

                        size_t index = hf(kot(cur->_data)) % newTables.size();
                        //头插
                        cur->_next = newTables[index];
                        newTables[index] = cur;

                        cur = next;
                    }

                    _tables[i] = nullptr;
                }

                _tables.swap(newTables);
            }
            size_t index = hf(kot(data)) % _tables.size();
            Node* newnode = new Node(data);
            //头插
            newnode->_next = _tables[index];
            _tables[index] = newnode;

            ++_n;
            return make_pair(iterator(newnode,this),false);
        }

    private:
        /*struct Data
        {
            forward_list<T> _list;
            set<T> _rbtree;
            size_t len;
        };
        vector<Data> _table;*/
        vector<Node*> _tables;

        size_t _n = 0;//有效数据的个数
    };
}

//unordered-map
#pragma once
#include"HashTable.h"

namespace bit
{
    template<class K,class V,class hash = Hash<K>>
    class unordered_map
    {
        struct MapKeyOfT
        {
            const K& operator()(const pair<K, V>& kv)
            {
                return kv.first;
            }
        };
    public:
        typedef typename LinkHash::HashTable<K, pair<K, V>, MapKeyOfT, hash>::iterator iterator;
        iterator begin()
        {
            return _ht.begin();
        }

        iterator end()
        {
            return _ht.end();
        }

        V& operator[](const K& key)
        {
            auto ret = _ht.Insert(make_pair(key, V()));
            return ret.first->second;
        }

        pair<iterator,bool> insert(const pair<K, V>& kv)
        {
            return _ht.Insert(kv);
        }

    private:
        LinkHash::HashTable<K, pair<K,V>, MapKeyOfT, hash > _ht;
    };

    void test_unordered_map()
    {
        unordered_map<string, string> dict;
        dict.insert(make_pair("sort", "排序"));
        dict.insert(make_pair("string", "字符串"));
        dict.insert(make_pair("map", "地图、映射"));
        /*cout << dict["sort"] << endl;
        cout << dict["string"] << endl;
        cout << dict["map"] << endl;*/

        //dict["right"] = "右边";

        unordered_map<string, string>::iterator it = dict.begin();
        while (it != dict.end())
        {
            cout << it->first << ":" << it->second << endl;
            ++it;
        }
        cout << endl;

        unordered_map<string, string> copy(dict);
        for (auto& kv : copy)
        {
            cout << kv.first << ":" << kv.second << endl;
        }
        cout << endl;
    }
}

//unordered-set
#pragma once
namespace bit
{
    template<class K,class hash = Hash<K>>
    class unordered_set
    {
        struct SetKeyOfT
        {
            const K& operator()(const K& key)
            {
                return key;
            }
        };
    public:
        typedef typename LinkHash::HashTable<K, K, SetKeyOfT, hash>::iterator iterator;
        iterator begin()
        {
            return _ht.begin();
        }

        iterator end()
        {
            return _ht.end();
        }

        pair<iterator,bool> insert(const K& key)
        {
            return _ht.Insert(key);
        }
    private:
        LinkHash::HashTable<K, K, SetKeyOfT, hash> _ht;
    };

    void test_unordered_set()
    {
        unordered_set<int> us;
        us.insert(4);
        us.insert(14);
        us.insert(34);
        us.insert(7);
        us.insert(24);
        us.insert(17);
        unordered_set<int>::iterator it = us.begin();
        while (it != us.end())
        {
            cout << *it << " ";
            ++it;
        }
        cout << endl;

        unordered_set<int> uss(us);
        unordered_set<int>::iterator It = uss.begin();
        while (It != uss.end())
        {
            cout << *It << " ";
            ++It;
        }
        cout << endl;

        /*unordered_set<string> uss;
        uss.insert("sort");
        uss.insert("hash");*/

        /*unordered_set<int> us;
        for (size_t i = 0; i < 100; ++i)
        {
            us.insert(i);
        }*/
    }
}

//bitSet
#pragma once
#include<vector>

namespace bit
{
    template<size_t N>
    class bitset
    {
    public:
        bitset()
        {
            _bits.resize(N / 8 + 1, 0);
        }

        void set(size_t x)
        {
            size_t i = x / 8;
            size_t j = x % 8;

            _bits[i] |= (1 << j);
        }

        void reset(size_t x)
        {
            size_t i = x / 8;
            size_t j = x % 8;

            _bits[i] &= (~(1 << j));
        }

        bool test(size_t x)
        {
            size_t i = x / 8;
            size_t j = x % 8;

            return _bits[i] & (1 << j);
        }

    private:
        std::vector<char> _bits;
        //std::vector<int> _bits;
    };

    void test_bitset()
    {
        bitset<100> bs;
        bs.set(5);
        bs.set(4);
        bs.set(10);
        bs.set(20);

        cout << bs.test(5) << endl;
        cout << bs.test(4) << endl;
        cout << bs.test(10) << endl;
        cout << bs.test(20) << endl;
        cout << bs.test(21) << endl;
        cout << bs.test(6) << endl << endl;

        bs.reset(20);
        bs.reset(10);
        bs.reset(5);

        cout << bs.test(5) << endl;
        cout << bs.test(4) << endl;
        cout << bs.test(10) << endl;
        cout << bs.test(20) << endl;
        cout << bs.test(21) << endl;
        cout << bs.test(6) << endl;

        //bitset<0xffffffff> bs;
        //bitset<-1> bs;
    }
}

template<size_t N>
class TwoBitSet
{
public:
    void Set(size_t x)
    {
        if (!_bs1.test(x) && !_bs2.test(x)) //00 -> 01
        {
            _bs2.set(x);
        }
        else if (!_bs1.test(x) && _bs2.test(x)) //01 -> 10
        {
            _bs1.set(x);
            _bs2.reset(x);
        }
        //10 表示已经出现2次或以上，不用处理
    }

    void PrintOnceNum()
    {
        for (size_t i = 0; i < N; ++i)
        {
            if (!_bs1.test(i) && _bs2.test(i)) // 01
            {
                cout << i << endl;
            }
        }
    }
private:
    bit::bitset<N> _bs1;
    bit::bitset<N> _bs2;
};

void TestTwoBitSet()
{
    int a[] = { 99,0,4,50,33,44,2,5,99,0,50,99,50,2 };
    TwoBitSet<100> bs;
    for (auto e : a)
    {
        bs.Set(e);
    }
    bs.PrintOnceNum();
}

void TestFindIntersection()
{
    int a1[] = { 5,30,1,99,10 };
    int a2[] = { 8,10,11,9,30,10,30 };
}

//BloomFilter
#pragma once

#include<bitset>
#include<string>
#include<time.h>

struct BKDRHash
{
    size_t operator()(const string& s)
    {
        //BKDR
        size_t value = 0;
        for (auto ch : s)
        {
            value *= 3;
            value += ch;
        }
        return value;
    }
};
struct APHash
{
    size_t operator()(const string& s)
    {
        size_t hash = 0;
        for (long i = 0; i < s.size(); i++)
        {
            if ((i & 1) == 0)
            {
                hash ^= ((hash << 7) ^ s[i] ^ (hash >> 3));
            }
            else
            {
                hash ^= (~((hash << 11) ^ s[i] ^ (hash >> 5)));
            }
        }
        return hash;
    }
};

struct DJBHash
{
    size_t operator()(const string& s)
    {
        size_t hash = 5381;
        for(auto ch : s)
        {
            hash += (hash << 5) + ch;
        }
        return hash;
    }
};

template<size_t N,
size_t X = 8,
class K = string,
class HashFunc1 = BKDRHash,
class HashFunc2 = APHash,
class HashFunc3 = DJBHash>
class BloomFilter
{
public:
    void Set(const K& key)
    {
        size_t len = X * N;
        size_t index1 = HashFunc1()(key) % len;
        size_t index2 = HashFunc2()(key) % len;
        size_t index3 = HashFunc3()(key) % len;
        cout << index1 << endl;
        cout << index2 << endl;
        cout << index3 << endl << endl;

        _bs.set(index1);
        _bs.set(index2);
        _bs.set(index3);
    }

    bool Test(const K& key)
    {
        size_t len = X * N;
        size_t index1 = HashFunc1()(key) % len;
        if (_bs.test(index1) == false)
            return false;

        size_t index2 = HashFunc2()(key) % len;
        if (_bs.test(index2) == false)
            return false;

        size_t index3 = HashFunc3()(key) % len;
        if (_bs.test(index3) == false)
            return false;

        return true;  //存在误判的
    }

    //不支持删除，删除可能会影响其它值。
    void Reset(const K& key);
private:
    bitset<X* N> _bs;
};

void TestBloomFilter1()
{
    BloomFilter<100> bm;
    bm.Set("sort");
    bm.Set("left");
    bm.Set("right");
    bm.Set("eat");
    bm.Set("ate");
    bm.Set("https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html");

}

void TestBloomFilter2()
{
    BloomFilter<100> bf;
    bf.Set("张三");
    bf.Set("李四");
    bf.Set("牛魔王");
    bf.Set("红孩儿");
    bf.Set("eat");

    cout << bf.Test("张三") << endl;
    cout << bf.Test("李四") << endl;
    cout << bf.Test("牛魔王") << endl;
    cout << bf.Test("红孩儿") << endl;
    cout << bf.Test("孙悟空") << endl;
    cout << bf.Test("二郎神") << endl;
    cout << bf.Test("猪八戒") << endl;
    cout << bf.Test("ate") << endl;

    //BloomFilter<100> bf;

    srand(time(0));
    size_t N = 100;
    std::vector<std::string> v1;
    for (size_t i = 0; i < N; ++i)
    {
        std::string ur1 = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
        ur1 += std::to_string(1234 + i);
        v1.push_back(ur1);
    }

    for (auto& str : v1)
    {
        bf.Set(str);
    }

    for (auto& str : v1)
    {
        cout << bf.Test(str) << endl;
    }
    cout << endl << endl;

    std::vector<std::string> v2;
    for (size_t i = 0; i < N; ++i)
    {
        std::string ur1 = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
        ur1 += std::to_string(6789 + i);
        v2.push_back(ur1);
    }

    size_t n2 = 0;
    for (auto& str : v2)
    {
        if (bf.Test(str))
        {
            ++n2;
        }
    }
    cout << "相似字符串误判率:" << (double)n2 / (double)N << endl;

    std::vector<std::string> v3;
    for (size_t i = 0; i < N; ++i)
    {
        string ur1 = "zhihu.com";
        //std::string ur1 = "https://mail.qq.com/cgi-bin/frame_html?sid=0QvJ6bvfhn3EC1Iw&r=5976c09322eae24513a5ff315428cd86&lang=zh";
        //std::string ur1 = "https://www.sogou.com/tx?query=%E5%88%98%E5%BC%BA%E4%B8%9C%E4%BA%8B%E4%BB%B6%20%E5%A5%B3%E6%96%B9%E7%A7%B0%E8%87%AA%E6%84%BF%E5%8F%91%E7%94%9F%E5%85%B3%E7%B3%BB&hdq=sogou-site-706608cfdbcc1886&ekv=3&ie=utf8&";
        //std::string ur1 = "https://www.sogou.com/sogou?ie=utf8&pid=sogou-wsse-af64b05ee108fa0c&query=%E4%BA%BA%E6%B0%91%E7%BD%91%3A%E5%BE%B7%E4%BA%91%E7%A4%BE%E8%AF%A5%E8%87%AA%E6%88%91%E6%A3%80%E8%A7%86%E4%BA%86";
        ur1 += std::to_string(rand());
        v3.push_back(ur1);
    }

    size_t n3 = 0;
    for (auto& str : v3)
    {
        if (bf.Test(str))
        {
            ++n3;
        }
    }
    cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;
}