unordered_map和unordered_set的使用

map和set底层是红黑树实现的，map是KV模型，set是K模型，而unordered_map和unordered_set底层是哈希表实现的，unordered_set是K模型，unordered_map是KV模型

unordered_map和unordered_set的命名体现特点，在功能和map/set是一样的，区别在于，它遍历出来是无序的，另外，它们的迭代器是单向迭代器

unordered_map的文档

unordered_map是存储<key, value>键值对的关联式容器，其允许通过keys快速的索引到与其对应的
value。
在unordered_map中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键
和映射值的类型可能不同。
在内部,unordered_map没有对<kye, value>按照任何特定的顺序排序, 为了能在常数范围内找到key所
对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。
unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率
较低。
unordered_maps实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问value。
它的迭代器至少是前向迭代器。

下面我们来看一下unordered_map和unordered_set的使用：

#include<iostream>
#include<unordered_set>
#include<unordered_map>
using namespace std;

void test_unordered_set()
{
    unordered_set<int> s;
    s.insert(3);
    s.insert(4);
    s.insert(5);
    s.insert(3);
    s.insert(1);
    s.insert(2);
    s.insert(6);
    unordered_set<int>::iterator it = s.begin();
    while (it != s.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

int main()
{
    test_unordered_set();
    return 0;
}

可以看到它遍历出来是无序的，并且相同的数只会插入一次

#include<iostream>
#include<unordered_map>
using namespace std;
void test_unordered_map()
{
    unordered_map<string, string> dict;
    dict.insert(make_pair("string", "字符串"));
    dict.insert(make_pair("sort", "排序"));
    dict.insert(make_pair("string", "字符串"));
    dict.insert(make_pair("string", "字符串"));
    auto it = dict.begin();
    while (it != dict.end())
    {
        cout << it->first << ":" << it->second << endl;
        it++;
    }
}
int main()
{
    test_unordered_map();
    return 0;
}

它遍历出来也是无序的，并且相同的数只会插入一次

unordered_set和unordered_map的两个OJ题

两个数组的交集

题目思路：
用unordered_set对nums1中的元素去重，然后用unordered_set对nums2中的元素去重，最后遍历s1，如果s1中某个元素在s2中出现过，即为交集

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        // 用unordered_set对nums1中的元素去重
        unordered_set<int> s1;
        for (auto e : nums1)
        s1.insert(e);
        // 用unordered_set对nums2中的元素去重
        unordered_set<int> s2;
        for (auto e : nums2)
        s2.insert(e);
        // 遍历s1，如果s1中某个元素在s2中出现过，即为交集
        vector<int> vRet;
        for (auto e : s1)
        {
        if (s2.find(e) != s2.end())
        vRet.push_back(e);
        }
        return vRet;
    }
};

两个数组的交集二

题目思路：
1、两个位置的值相等，则是交集，同时++

2、两个位置的值不相等，则不是交集值，小的++

set和undered_set的性能比较

void test_op()
{
    set<int> s;
    unorder_set<int> us;
    const int n = 100000;
    vector<int> v;
    srand(time(0));
    for(size_t i = 0;i<n;++i)
    {
        v.push_back(rand());
    }
    //插入性能比较
    size_t begin1 = clock();
    for(auto e:v)
    {
        us.insert(e);
    }
    size_t end1 = clock();
    cout<<end1-begin1<<endl;
    
    size_t begin2 = clock();
    for(auto e:v)
    {
        s.insert(e);
    }
    size_t end2 = clock();
    cout<<end2-begin2<<endl;
    
    //查找性能比较
    size_t begin3 = clock();
    for(auto e:v)
    {
        us.find(e);
    }
    size_t end3 = clock();
    cout<<end1-begin1<<endl;
    
    size_t begin4 = clock();
    for(auto e:v)
    {
        s.find(e);
    }
    size_t end4 = clock();
    cout<<end2-begin2<<endl;
    
    //删除效率比较
    size_t begin5 = clock();
    for(auto e:v)
    {
        us.erase(e);
    }
    size_t end5 = clock();
    cout<<end5-begin5<<endl;
    
    size_t begin6 = clock();
    for(auto e:v)
    {
        s.erase(e);
    }
    size_t end6 = clock();
    cout<<end6-begin6<<endl;
}

发现不管运行多少次，都是哈希表比较优，unordered系列的关联式容器之所以效率比较高，是因为其底层使用了哈希结构。

哈希

哈希概念

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经
过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(log2N)，搜索的效率取决
于搜索过程中元素的比较次数。

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结构，通过
某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函
数可以很快找到该元素。

当向该哈希结构中：

插入元素

根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放

搜索元素

对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比
较，若关键码相等，则搜索成功

该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表
(Hash Table)(或者称散列表)

例如：我们有数据集合{1，7，6，4，5，9}；

哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小。

用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快问题：按照上述哈希方式，向集合中
插入元素44，会出现什么问题？发现4这个位置已经被占用了

哈希冲突

对于两个数据元素的关键字和 (i != j)，有 != ，但有：Hash( ) == Hash( )，即：不同关键字通过
相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。
把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。
发生哈希冲突该如何处理呢？

常见哈希函数

直接定址法

缺点：需要事先知道关键字的分布情况

使用场景：适合查找比较小且连续的情况

除留余数法

设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函
数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址

哈希冲突的解决

解决哈希冲突两种常见的方法是：闭散列和开散列

闭散列

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

线性探测：index+i (i = 1,2,3,4…)
从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止
二次探测：index+i^2(i = 1,2,3,4…)
线性探测的缺陷是产生冲突的数据堆积在一块，相比线性探测的好处，如果一个位置有很多值映射，冲突剧烈，那么它们存储时相对会比较分散，不会引发一片一片的冲突

开散列

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

闭散列的实现

我们实现哈希表，那么数据怎么存储呢？数据的结构又是什么呢？数据的存储很好想到，可以用一个vector存就好了，那么数据的结构出来存储数据还需要什么呢？比如我们有以下数据：

我们查找一个值时，按照哈希函数求得位置，如果当前位置不是，则可能遇到了冲突，所以一直往后找，当遇到空位置时说明这个值肯定不存在了，因为如果存在，肯定存储在了第一个空位置，那么当我们删除一个值，直接删除的话这个位置变成了空，但是这样有问题：使得查找一个值提早遇到空，那么就找不到这个值

比如删除333，直接删除后变成了空位置，我们再查找14会怎么样？我们先求得14的位置是4，发现4这个位置是空，所以直接就返回不存在，导致14存在，但是查找不到14

解决方案：每个位置存储值得同时再存储一个状态标记：空、满、删除

如果一个值删除了，将该位置标记为删除，查找一个值如果遇到了删除，那么不停止继续查找，插入一个值时遇到了空和删除都可以插入

所以还需要该存储位置的当前状态：

EMPTY(空数据的位置)
EXIST(已存储数据)
DELETE(以前有数据，但是删除了)

enum Status
{
    EMPTY,//空
    EXIST,//存在
    DELETE//删除
};

数据的存储结构

我们实现KV模型，所以数据弄成pair，另外还需要状态：

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

哈希表的结构

vector来存储HashData，_n用来存储有效数据的个数

template<class K,class V>
class HashTable
{
public:
private:
    vector<HashData<K,V>> _tables;//vector来存储HashData
    size_t _n = 0;//存储有效数据的个数
};

哈希表的插入

我们为了避免哈希冲突变多，我们引入一个负载因子，当负载因子过大时需要对哈希表进行增容

如果哈希表中已经存在该键值对，则插入失败返回false
判断该哈希表的大小以及负载因子，确定是否需要增容
将键值对插入哈希表
++_n

首先我们解决增容的问题，首先我们确定的是_table.size() == 0时需要增容，其次我们设置负载因子=有效数据/表的大小，如果负载因子大于0.7时就增容。

那么怎么增容呢？

有一种方法是创建一个新vector，resize新空间大小，然后将旧表中的数据复制到新表当中

//方法一
size_t newSize = _table.size()==0? 10:_table.size()*2;
vector<HashData<K,V>> newTable;
newTable.resize(newSize);
for(size_t i =0;i<_tables.size();++i)
{
    if(_table[i]._status == EXIST)
    {
        //将存在的数据复制到新表中
        size_t index = _table[i]._kv.first % newTable.size();
        //...
    }
}

比较好的方法是建立一个临时新表，给新表开扩容后的空间，然后遍历旧表将旧表的数据插入新表，最后将新表和旧表交换：

//方法二：
size_t newSize = _table.size()==0? 10 : _table.size()*2;
HashTable<K,V> newHT;//建立一个临时新表
newHT._tables.resize(newSize);//给新表开扩容后的空间
for(auto& e:_tables)
{
    if(e._status == EXIST)
    {
        newHT.Insert(e._kv);//将旧表的数据插入新表
    }
}
_table.swap(newHT._tables);//将新表和旧表交换

插入哈希表的代码(首先计算出插入的位置，如果该位置存在的话就遍历后面的位置，遍历的过程中如果等于的表的末尾，则返回起始位置继续遍历，直到遇到空或者删除)：

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

    if(index == _tables.size())
    {
        //当index到达最后的时候,让它回到起始
        index = 0;
    }
}
//走到这里要么是空要么是删除
_tables[index]._kv = kv;
_tables[index]._status = EXIST;
++_n;

插入的完整代码：

//插入
bool Insert(const pair<K,V>& kv)
{
    if(Find(kv.first))
    {
        return false;
    }
    if(_table.size() == 0 || (double)(_n / _table.size()) > 0.7)
    {
        //扩容
        size_t newSize = _table.size()==0? 10 : _table.size()*2;
        HashTable<K,V> newHT;//建立一个临时新表
        newHT._tables.resize(newSize);//给新表开扩容后的空间
        for(auto& e:_tables)
        {
            if(e._status == EXIST)
            {
                newHT.Insert(e._kv);//将旧表的数据插入新表
            }
        }
        _table.swap(newHT._tables);//将新表和旧表交换
    }

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

        if(index == _tables.size())
        {
            //当index到达最后的时候,让它回到起始
            index = 0;
        }
    }
    //走到这里要么是空要么是删除
    _tables[index]._kv = kv;
    _tables[index]._status = EXIST;
    ++_n;

    return true;
}

哈希表的查找

哈希表的查找逻辑很简单：先计算出查找的key的位置，当这个位置不等于空时，判断key值是不是相等并且状态位存在，如果是的话返回，不是的话进行线性探测或者二次探测，直到遇到位置为空状态

HashData<K,V>* Find(const K& key)
{
    if(_table.size() == 0)
    {
        //防止除0错误
        return nullptr;
    }
    size_t start = key % _table.size();
    size_t i = 0;
    size_t index = start + i;
    while(_tables[index]._status != EMPTY)
    {
        if(_tabled[index]._kv.first == key && _table[index]._status == EXIST)
        {
            return &_tabled[index];
        }
        else
        {
            ++i;
            //index = start +i;
            index = start + i*i;//二次探测
            index %= _tables.size();
        }
    }
    return nullptr;
}

哈希表的删除

首先找到这个节点，进行伪删除，将该节点的状态设置成删除然后–_n即可

bool Erase(const K& key)
 {
     HashData<K,V>* ret = Find(key);
     if(ret == nullptr)
     {
         //没有这个值
         return false;
     }
     else
     {
         //伪删除
         ret->_status = DELETE;
         _n--;
         return true;
     }
 }

哈希表闭散列的代码

#pargma once
namespace close_hash
{
    enum Status
    {
        EMPTY,//空
        EXIST,//存在
        DELETE//删除
    };
    template<class K,class V>
    struct HashData
    {
        pair<K,V> _kv;
      	Status _status = EMPTY; //状态
    }
    template<class K,class V>
   	class HashTable
    {
    public:
        bool Erase(const K& key)
        {
            HashData<K,V>* ret = Find(key);
            if(ret == nullptr)
            {
                //没有这个值
                return false;
            }
            else
            {
                //伪删除
                ret->_status = DELETE;
                _n--;
                return true;
            }
        }
        HashData<K,V>* Find(const K& key)
        {
            if(_table.size() == 0)
            {
                //防止除0错误
                return nullptr;
            }
            size_t start = key % _table.size();
            size_t i = 0;
            size_t index = start + i;
            while(_tables[index]._status != EMPTY)
            {
                if(_tabled[index]._kv.first == key && _table[index]._status == EXIST)
                {
                    return &_tabled[index];
                }
                else
                {
                    ++i;
                    //index = start +i;
                   	index = start + i*i;//二次探测
                    index %= _tables.size();
                }
            }
            return nullptr;
        }
        //插入
        bool Insert(const pair<K,V>& kv)
        {
            if(Find(kv.first))
            {
                return false;
            }
            if(_table.size() == 0 || (double)(_n / _table.size()) > 0.7)
            {
                //扩容
                //方法一
                size_t newSize = _table.size()==0? 10:_table.size()*2;
                vector<HashData<K,V>> newTable;
                newTable.resize(newSize);
                for(size_t i =0;i<_tables.size();++i)
                {
                    if(_table[i]._status == EXIST)
                    {
                        //将存在的数据复制到新表中
                        size_t index = _table[i]._kv.first % newTable.size();
                        //...
                    }
                }
                //方法二：
                size_t newSize = _table.size()==0? 10 : _table.size()*2;
                HashTable<K,V> newHT;//建立一个临时新表
                newHT._tables.resize(newSize);//给新表开扩容后的空间
                for(auto& e:_tables)
                {
                    if(e._status == EXIST)
                    {
                        newHT.Insert(e._kv);//将旧表的数据插入新表
                    }
                }
                _table.swap(newHT._tables);//将新表和旧表交换
            }
            
            size_t start = kv.first % _tables.size();
            size_t i = 0;
            size_t index = start + i;
            while(_table[index]._status == EXIST)
            {
                ++i;
                //index = start+i;//线性探测
                index = start+i*i;//二次探测
                
                if(index == _tables.size())
                {
                    //当index到达最后的时候,让它回到起始
                    index = 0;
                }
                //插满的时候会死循环
            }
            //走到这里要么是空要么是删除
            _tables[index]._kv = kv;
            _tables[index]._status = EXIST;
            ++_n;
            
            return true;
        }
    private:
        vector<HashData<K,V>> _tables;//vector来存储HashData
        size_t _n = 0;//存储有效数据的个数
    }
}

我们上面的代码有些问题：

如果是key是string，上面的代码是编不过去的，因为key是string，无法计算位置，所以此时就用到了仿函数，仿函数通过重载方法将string转化为整形用来做key，这里运用了BKDR Hash思想来完成string到key的转换，发生冲突的概率很小

template<class K>
struct HashFunc
{
    size_t operator()(const K&key)
    {
        return key;
    }
};    
struct HashFuncString
{
    size_t operator()(const string& key)
    {
        //BKDR Hash思想
        size_t hash = 0;
        for(size_t i = 0;i<key.size();++i)
        {
            hash*=131;
            hash += key[i];//转成整形
        }
        return hash;
    }
};

如果我们写成这样我们创建string为key的哈希表的时候就需要这样写，将HashFuncString仿函数传进去：

HashTable<string, string, HashFuncString> dict;

而我们使用unordered_map时是不需要传这个仿函数进去的，这里用到了模板的特化：

template<class K>
struct HashFunc
{
    size_t operator()(const K&key)
    {
        return key;
    }
}; 
template<>
struct HashFunc<string>
{
    size_t operator()(const string& key)
    {
        //BKDR Hash思想
        size_t hash = 0;
        for(size_t i = 0;i<key.size();++i)
        {
            hash*=131;
            hash += key[i];//转成整形
        }
        return hash;
    }
};

此时哈希表的模板参数也就要发生变化：

template<class K, class V, class Hash = HashFunc<K>>

不传仿函数过去，它会自己推演，是K是int类型就调用HashFunc<int>，是string就调用更匹配的HashFunc<string>

哈希表闭散列的完整代码

#pargma once
namespace close_hash
{
    enum Status
    {
        EMPTY,//空
        EXIST,//存在
        DELETE//删除
    };
    template<class K,class V>
    struct HashData
    {
        pair<K,V> _kv;
      	Status _status = EMPTY; //状态
    };
    template<class K>
    struct HashFunc
    {
        size_t operator()(const K&key)
        {
            return key;
        }
    };    
    //特化
    template<>
    struct HashFunc<string>
    {
        size_t operator()(const string& key)
        {
            //BKDR Hash思想
            size_t hash = 0;
            for(size_t i = 0;i<key.size();++i)
            {
                hash*=131;
                hash += key[i];//转成整形
            }
            return hash;
        }
    };  
    template<class K,class V,class Hash = HashFunc<K>>
   	class HashTable
    {
    public:
        bool Erase(const K& key)
        {
            HashData<K,V>* ret = Find(key);
            if(ret == nullptr)
            {
                //没有这个值
                return false;
            }
            else
            {
                //伪删除
                ret->_status = DELETE;
                _n--;
                return true;
            }
        }
        HashData<K,V>* Find(const K& key)
        {
            if(_table.size() == 0)
            {
                //防止除0错误
                return nullptr;
            }
            Hash hf;
            size_t index = hf(key) % _table.size();
            size_t i = 0;
            size_t index = start + i;
            while(_tables[index]._status != EMPTY)
            {
                if(_tabled[index]._kv.first == key && _table[index]._status == EXIST)
                {
                    return &_tabled[index];
                }
                else
                {
                    ++i;
                    //index = start+i;//线性探测
                    index = start+i*i;//二次探测
                    index %= _tables.size();
                }
            }
            return nullptr;
        }
        //插入
        bool Insert(const pair<K,V>& kv)
        {
            if(Find(kv.first))
            {
                return false;
            }
            if(_table.size() == 0 || (double)(_n / _table.size()) > 0.7)
            {
                //扩容
                //方法二：
                size_t newSize = _table.size()==0? 10 : _table.size()*2;
                HashTable<K,V> newHT;//建立一个临时新表
                newHT._tables.resize(newSize);//给新表开扩容后的空间
                for(auto& e:_tables)
                {
                    if(e._status == EXIST)
                    {
                        newHT.Insert(e._kv);//将旧表的数据插入新表
                    }
                }
                _table.swap(newHT._tables);//将新表和旧表交换
            }
            Hash hf;
            size_t start = hf(kv.first) % _tables.size();
            //线性探测
            size_t i = 0;
            size_t index = start + i;
            while(_table[index]._status == EXIST)
            {
                ++index;
                if(index == _tables.size())
                {
                    //当index到达最后的时候,让它回到起始
                    index = 0;
                }
                //插满的时候会死循环
            }
            //走到这里要么是空要么是删除
            _tables[index]._kv = kv;
            _tables[index]._status = EXIST;
            ++_n;
            
            return true;
        }
    private:
        vector<HashData<K,V>> _tables;//vector来存储HashData
        size_t _n = 0;//存储有效数据的个数
    }
}

开散列的实现

开散列概念

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

数据的存储结构

因为桶里面是单链表结构，所以需要有一个指向下一个节点的指针_next，还有一个pair来存储数据

template<class V,class V>
struct HashBucketNode
{
    HashBucketNode(const pair<K,V>& kv)
        : _next(nullptr), _kv(kv)
    {}
    HashBucketNode<K,V>* _next;
    pair<K,V> _kv;
};

哈希表的结构

vector里面需要存储Node而不是Node，如果是Node会出现二义性：存节点了还是没有存，因为定义对象出现时节点都申请出来了，都进行了初始化。所以这里需要存储Node，指向第一个节点

class HashTable
 {
     typedef HashBucketNode<K,V> Node;
     private:
     size_t _n = 0;//哈希表中的有效数据
     vector<Node*> _tables;//会出现二义性：存节点了还是没有存,因为定义对象出现节点都申请出来了，都进行了初始化
 };

开散列是通过单链表链接分方式处理哈希冲突的，所以并不需要给每个节点设置状态，只需要将哈希地址相同的元素都放到同一个哈希桶里以单链表链接，开散列可以无限的插入，如果表的大小太小，那么每个桶中的单链表就会链接的节点越多，这样找一个节点时效率就会变低，所以开散列我们也要通过负载因子来判断是否增容，通过增容，每个哈希桶的链接的元素相对变少，效率也就好了些，所以我们需要一个_n变量来记录哈希表中的有效数据，来计算负载因子

注意：

负载因子 = 数据个数/表的大小，负载因子越低，冲突的概率越低，空间浪费越高，负载因子越高，冲突的概率越高，空间浪费越低

哈希表的插入

哈希表的插入步骤：

如果哈希表中已经存在该键值对，则插入失败返回false
判断该哈希表的大小以及负载因子，确定是否需要增容
将键值对插入哈希表
++_n

首先我们解决增容的问题，首先我们确定的是_table.size() == 0时需要增容，其次我们设置负载因子=有效数据/表的大小，如果负载因子大于1时就增容。

那么怎么增容呢？

可以这样扩容吗？直接扩2倍：

此时表的大小发生变化，所以需要重新计算位置，会导致处理十分混乱

需要这样扩容：创建一个新表，该哈希表是原来表的2倍，之后遍历旧哈希表，将旧哈希表的数据插入到新哈希表中，最后将新表和旧表交换即可：

将旧哈希表的数据插入到新哈希表中，如果像闭散列那样的方式写时，即通过复用Insert来插入数据时会有一个问题，闭散列表中就是存储数据的，而开散列表中不存储数据，存储的是节点的指针，通过复用Insert来插入数据时，相当于又创建了重复的节点，把已经存在的节点再创建一遍，到最后又要将旧表中和新表中重复的节点释放一次，是不是多此一举了

所以我们只需要通过遍历旧哈希表的哈希桶，将旧表哈希桶的数据头插到新表的哈希桶中，然后将旧表的头节点的next置为空，最后新表和旧表交换即可

bool Insert(const pair<K,V>& kv)
{
    //当负载因子到1时，进行扩容
    if(_n == _table.size())
    {
        size_t newSize = _tables.size() == 0?10:_tables.size()*2;
        vector<Node*> newtables;
        newtables.resize(newSize,nullptr);
        for(size_t i =0;i<_tables.size();i++)
        {
            //遍历旧表
            Node* cur = _tables[i];
            while(cur)
            {
                //桶里有数据
                Node* next = cur->_next;
                size_t index = cur->kv.first % newSize;//当前节点在新表中的位置
                //头插
                cur->_next = newtable[index];//插入节点的next指向新表的第一个节点
                newtable[index] = cur;//第一个节点变为cur

                cur = next;
            }
            _tables[i] = nullptr;
        }
        newtables.swap(_tables);
    }

    size_t index = kv.first % _tables.size();//要存的位置
    Node* cur = _table[index];
    while(cur)
    {
        if(cur->_kv.first == kv.first)
        {
            return false;
        }
        else
        {
            cur = cur->_next;
        }
    }
    Node* newnode = new Node(kv);
    //插入节点->头插
    newnode->_next = _table[index];
    _table[index] = newnode;
    ++_n;
}

哈希表插入效率很高，但是扩容影响了插入接口的效率，扩容的代价比较大

哈希表的查找

如果表的大小等于0，返回nullptr
找到桶的位置，然后进行遍历桶，比较值是否相等，相等则返回，不相等继续下一个节点
遍历完没找到返回nullptr

Node* Find(const K& key)
{
    if(_table.size() == 0)
    {
        return nullptr;
    }
    size_t index = key % _table.size();
    Node* cur = _table[index];//第一个节点的指针
    while(cur)
    {
        if(cur->_kv.first == key)
        {
            return cur;
        }
        else
        {
            cur = cur->_next;
        }
    }
    return nullptr;
}

哈希表的删除

如果表的大小等于0，返回false
找到桶的位置，需要注意删除节点需要保存节点的前一个节点，遍历桶找要删除的节点进行删除，需要注意头删和非头删，头删时prev为空，非头删prev不为空
删除完成–_n，返回true，否则返回false

bool Erase(const K& key)
 {
     if(_table.size() == 0)
     {
         return false;
     }
     size_t index = key % _table.size();
     Node* prev = nullptr;
     Node* cur = _tables[index];
     while(cur)
     {
         if(cur->_kv.first == key)
         {
             //找到这个节点
             if(prev == nullptr)
             {
                 //cur是第一个节点
                 _table[index] = cur->_next;
                 delete cur;
             }
             else
             {
                 //不是头节点
                 prev->next = cur->_next;
                 delete cur;
             }
             --_n;
             return true;
         }
         else
         {
             prev = cur;
             cur = cur->_next;
         }
     }
     //没有这个值
     return false;
 }

开散列和闭散列一样，都得通过仿函数处理string的情况：

template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return key;
	}
};
// 特化
template<>
struct HashFunc < string >
{
	size_t operator()(const string& key)
	{
		// BKDR Hash思想
		size_t hash = 0;
		for (size_t i = 0; i < key.size(); ++i)
		{
			hash *= 131;
			hash += key[i];
		}

		return hash;
	}
};

哈希表的大小尽可能是一个素数，这样效率会有提高，源码里面增加了一个素数表，还有一个GetNextPrime函数，获取下一个素数，我们可以用这个函数来获得newSize：

size_t GetNextPrime(size_t prime)
{
    const int PRIMECOUNT = 28;
    const size_t primeList[PRIMECOUNT] =
    {
        53ul, 97ul, 193ul, 389ul, 769ul,
        1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
        49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
        1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
        50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
        1610612741ul, 3221225473ul, 4294967291ul
    };
    size_t i = 0;
    for(; i < PRIMECOUNT; ++i)
    {
        if(primeList[i] > prime)
            return primeList[i];
    }
    return primeList[i];
}

所以我们的扩容的newSize这样获取，这样可以获取比表大小大的素数，所以insert接口扩容大小这样写效率更高：

size_t newSize = GetNextPrime(_table.size());//获取比表大小大的素数

STL当中有桶的个数和最大桶的个数的接口：

哈希桶的析构函数

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

哈希表开散列的完整代码

namespace bucket_hash
{
	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)
		{}
	};

	size_t GetNextPrime(size_t prime)
	{
		const int PRIMECOUNT = 28;
		static const size_t primeList[PRIMECOUNT] =
		{
			53ul, 97ul, 193ul, 389ul, 769ul,
			1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
			49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
			1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
			50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
			1610612741ul, 3221225473ul, 4294967291ul
		};

		size_t i = 0;
		for (; i < PRIMECOUNT; ++i)
		{
			if (primeList[i] > prime)
				return primeList[i];
		}

		return primeList[i];
	}

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

		// 拷贝 和 赋值 需要自己实现桶的拷贝

		~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 Erase(const K& key)
		{
			if (_tables.size() == 0)
			{
				return false;
			}

			Hash hf;
			// 素数
			size_t index = hf(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[index];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					// 1、cur是头结点
					// 2、非头节点
					if (prev == nullptr)
					{
						_tables[index] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}

					delete cur;
					--_n;

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

			return false;
		}

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

			Hash 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)
		{
			Hash hf;

			//当负载因子到1时，进行扩容
			if (_n == _tables.size())
			{
				//size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				size_t newSize = GetNextPrime(_tables.size());

				//HashTable<K, V> newHT;
				vector<Node*> newtables;
				newtables.resize(newSize, nullptr);
				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) % newSize;
						cur->_next = newtables[index];
						newtables[index] = cur;

						cur = next;
					}
					_tables[i] = nullptr;
				}

				newtables.swap(_tables);
			}

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

			Node* newnode = new Node(kv);
			newnode->_next = _tables[index];
			_tables[index] = newnode;

			++_n;

			return true;
		}

	private:
		vector<Node*> _tables;
		size_t _n = 0; // 存储多少有效数据
	};

C++之unordered_map和unordered_set以及哈希详解

unordered_map和unordered_set的使用

unordered_map的文档

unordered_set和unordered_map的两个OJ题

两个数组的交集

两个数组的交集二

set和undered_set的性能比较

哈希

哈希概念

哈希冲突

常见哈希函数

哈希冲突的解决

闭散列

开散列

闭散列的实现

数据的存储结构

哈希表的结构

哈希表的插入

哈希表的查找

哈希表的删除

哈希表闭散列的代码

哈希表闭散列的完整代码

开散列的实现

开散列概念

数据的存储结构

哈希表的结构

哈希表的插入

哈希表的查找

哈希表的删除

哈希桶的析构函数

哈希表开散列的完整代码

相关文章

热门标签

最新文章

目录