@TOC

零、前言

本章主要讲解unordered系列关联式容器及其底层结构和模拟实现，还有哈希的相关应用等

一、unordered系列关联式容器

• 概念：

1. 在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到 ，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想
2. 最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同
3. unordered_map/unordered_set与map/set基本上只有底层实现上的区别，前者是哈希，后者是红黑树
4. unordered_map/unordered_set与unordered_multimap/unordered_multiset的区别是是否允许键值冗余
5. unordered系列关联式容器因为底层不是红黑树了，所以遍历的结果不是排序好的序列

1、unordered_map介绍及使用

• 概念：

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

• 接口介绍：

1. unordered_map的构造

2. unordered_map的容量

3. unordered_map的迭代器

4. unordered_map的元素访问

注意：该函数中实际调用哈希桶的插入操作，用参数key与V()构造一个默认值往底层哈希桶中插入，如果key不在哈希桶中，插入成功，返回V()，插入失败，说明key已经在哈希桶中，将key对应的value返回

5. unordered_map的查询

注意：unordered_map中key是不能重复的，因此count函数的返回值最大为 1，对于unordered_multimap才是允许键值冗余的

6. unordered_map的修改操作

7. unordered_map的桶操作

• 使用示例：

void test_unordered_map()
{
    unordered_map<string, string> dict;
    dict.insert(make_pair("string", ""));
    dict.insert(make_pair("sort", ""));

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

• 结果：

2、unordered_set的介绍及使用

• 概念：

1. unordered_set是不按特定顺序存储键值的关联式容器，其允许通过键值快速的索引到对应的元素
2. 在unordered_set中，元素的值同时也是唯一地标识它的key
3. 在内部，unordered_set中的元素没有按照任何特定的顺序排序，为了能在常数范围内找到指定的key，unordered_set将相同哈希值的键值放在相同的桶中
4. unordered_set容器通过key访问单个元素要比set快，但它通常在遍历元素子集的范围迭代方面效率较低
5. 它的迭代器是单向前向迭代器

• 接口介绍：

1. unordered_set当中常用的成员函数

2. 迭代器相关函数

• 使用示例：

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

• 结果：

3、性能比较

• 测试代码：

void test_op()
{
    set<int> s;
    unordered_set<int> us;
    const int n = 1000000;
    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)
    {
        s.insert(e);
    }
    size_t end1 = clock();

    size_t begin2 = clock();
    for (auto e : v)
    {
        us.insert(e);
    }
    size_t end2 = clock();

    cout << "set insert:" << end1 - begin1 << endl;
    cout << "unordered_set insert:" << end2 - begin2 << endl;
    cout << "=====================" << endl;
    size_t begin3 = clock();
    for (auto e : v)
    {
        s.find(e);
    }
    size_t end3 = clock();

    size_t begin4 = clock();
    for (auto e : v)
    {
        us.find(e);
    }
    size_t end4 = clock();

    cout << "set find:" << end3 - begin3 << endl;
    cout << "unordered_set find:" << end4 - begin4 << endl;

    cout << "=====================" << endl;
    size_t begin5 = clock();
    for (auto e : v)
    {
        s.erase(e);
    }
    size_t end5 = clock();

    size_t begin6 = clock();
    for (auto e : v)
    {
        us.erase(e);
    }
    size_t end6 = clock();

    cout << "set erase:" << end5 - begin5 << endl;
    cout << "unordered_set erase:" << end6 - begin6 << endl;
}

• 结果：

总结：使用底层为哈希的容器总体的效率是非常高的，对于关联式set/map的复杂度能达到O(logN)，而unordered系列关联式容器可以达到接近O(1)的水平

二、哈希表/哈希桶

unordered系列的关联式容器之所以效率比较高，是因为其底层使用了哈希结构

1、哈希介绍及概念

• 概念：

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

2. 理想的搜索方法是可以不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素，则复杂度为O(1)非常的高效，而计数排序用的即是这种思想

• 大体步骤：

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

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

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

• 示例：

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

• 示图：

注：该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快，但是这样的搜索存在哈希冲突

2、哈希冲突及解决

• 概念：

1. 对于不同关键字通过相同哈希哈数可能会计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞，而具有不同关键码而具有相同哈希地址的数据元素称为“同义词”

2. 引起哈希冲突的一个原因可能是：哈希函数设计不够合理，但是好的哈希函数只能是减小冲突的概率，并非能杜绝

• 哈希函数设计原则：

哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间哈希函数计算出来的地址能均匀分布在整个空间中

• 常见哈希函数:

1. 直接定制法--(常用)

取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B

优点：简单、均匀 缺点：需要事先知道关键字的分布情况 使用场景适合查找比较小且连续的情况

2. 除留余数法--(常用)

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

3. 平方取中法--(了解)

假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址； 再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址

平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况

• 注意：

1. 哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突

2. 对于像使用计数排序的方式开辟足够大的空间来用下标建立映射关系的方式具有局限性，仅适用于数据集中的正数

• 解决哈希冲突两种常见的方法是：

闭散列和开散列

3、闭散列/哈希表的实现

• 概念：

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

• 寻找下一个空位置方式：

1. 线性探测

从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止，即newindexi=（index+i)%capacity

线性探测实现非常简单，但是一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低

2. 二次探测

从发生的冲突的位置开始，不逐个往后找，而是以平方个位置找，即计算位置为newindexi=（index+i^2)%capacity

二次探测可以较为有效的方式减小哈希冲突的概率

• 闭散列实现步骤：

1. 插入

通过哈希函数获取待插入元素在哈希表中的位置，如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素

• 示图：线性探测：依次往后找

2. 删除

采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索，比如删除元素4，如果直接删除掉，44查找起来可能会受影响

因此线性探测采用标记的伪删除法来删除一个元素，即每个位置都有一个表示当前状态的变量，存在数据为EXIST，不存在为EMPTY，删除为DELETE

• 示例：

// 哈希表每个空间给个标记
// EMPTY此位置空， EXIST此位置已经有元素， DELETE元素已经删除
enum State
{
    EMPTY, EXIST, DELETE
};

3. 查找

对于查找的话先利用哈希函数获取对应的哈希映射位置，再根据具体情况而进行下一步行为

如果探测的位置状态为空，那么不必比较数据且不用再往后查找

如果探测的位置状态为存在，那么则进行比较数据值，相等则查找到了；不相等则往后根据对应的探测方式继续查找

如果探测的位置状态为删除，那么同样需要继续往后查找，直到找到对应存在的数据或者探测到状态为空的位置就不用再查找了

4. 闭散列扩容

• 哈希表什么时候扩容：

• 哈希表扩容的实现：

使用除留余数定制法时，对于扩容后的哈希表对应的哈希函数的除数的值会发生相应的改变，导致下一次查找定制的位置可能不同，所以需要对原来的数据进行再次映射到新的位置上

5. 哈希类型取值映射的问题：

1. 由于哈希函数我们旋转的是除留余数法，但是只有整形才能进行取余，所以对于整形，浮点型数据我们可以直接进行强转取值，但是面对字符串类型或者其他自定义的类型的话，我们就需要进行取值特化，实现其对应类型的函数来取其中特定的数据当做取余的值

2. 为了遍历取值，我们选择使用仿函数的方式进行实现，并将该取值类型设置为模板类型，便于特化类型的传入和使用

• 代码实现：

//比较仿函数-取出类型中的数值
template<class T>
struct HashFunc
{
    size_t operator()(const T& key)
    {
        return key;
    }
};
//对string类型特化
template<>
struct HashFunc<string>
{
    size_t operator()(const string& str)
    {
        size_t hash = 0;
        for (int i = 0; i < str.size(); i++)
            hash = hash * 131 + str[i];//这种方式的冲突概率小
        return hash;
    }
};

• 闭散列代码实现：

enum State
{
    EXIST,
    DELETE,
    EMPTY
};
//哈希储存的数据类型
template<class K, class V>
struct HashData
{
    pair<K, V> _kv;
    State _state = EMPTY;//缺省值
};
//比较仿函数-取出类型中的数值
template<class T>
struct HashFunc
{
    size_t operator()(const T& key)
    {
        return key;
    }
};
//对string类型特化
template<>
struct HashFunc<string>
{
    size_t operator()(const string& str)
    {
        size_t hash = 0;
        for (int i = 0; i < str.size(); i++)
            hash = hash * 131 + str[i];//这种方式的冲突概率小
        return hash;
    }
};
template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
public:
    HashData<K, V>* Find(const K& key)
    {
        if (_table.size() == 0)//避免取模0
            return nullptr;
        Hash  hf;
        int i = 0;
        size_t start = hf(key) % _table.size();//取模size()，使用capacity()可能存到一定位置的空间会使得vector进行自动扩容，不便于控制
        size_t index = start;
        while (_table[index]._state != EMPTY)
        {
            if (_table[index]._kv.first == key &&
                _table[index]._state == EXIST)//存在且key相等
                return &_table[index];
            i++;
            index = (start + i * i) % _table.size();//二次探测+取模避免越界
        }
        return nullptr;
    }

    bool Insert(const pair<K, V>& kv)
    {
        if (Find(kv.first))//避免冗余
            return false;
        if (_table.size() == 0 || _size * 1.0 / _table.size() >= 0.7)//空哈希或者哈希因子达到一定程序则扩容
        {
            size_t newsize = _table.size() == 0 ? 10 : _table.size() * 2;
            HashTable<K, V, Hash> newHT;
            newHT._table.resize(newsize);//重新开辟足够空间
            //重新构建映射
            for (size_t i = 0; i < _table.size(); i++)
            {
                if (_table[i]._state == EXIST)
                    newHT.Insert(_table[i]._kv);
            }
            _table.swap(newHT._table);//交换地址
        }
        Hash  hf;
        int i = 0;
        size_t start = hf(kv.first) % _table.size();//取模size()
        size_t index = start;
        while (_table[index]._state == EXIST)
        {
            i++;
            index = (start + i * i) % _table.size();
        }
        //找到空或者删除则插入
        _table[index]._kv = kv;
        _table[index]._state = EXIST;
        _size++;
        return true;
    }
    bool Erase(const K& key)
    {
        auto ret = Find(key);
        if (ret == nullptr)
            return false;
        else
        {
            ret->_state = DELETE;//伪删除
            _size--;
            return true;
        }
    }
    size_t Size() const
    {
        return _size;
    }

    bool Empty() const
    {
        return _size == 0;
    }
private:
    vector<HashData<K, V>> _table;
    size_t _size = 0;//记录有效数据个数
};

• 测试代码：

void TestHashTable1()
{
    int a[] = { 5, 3, 100, 9999, 333, 14, 26, 34, 5 };
    //int a[] = { 5, 15, 25, 35, 45 };
    HashTable<int, int> ht;
    for (auto e : a)
    {
        ht.Insert(make_pair(e, e));
    }

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

void TestHashTable2()
{
    //HashTable<string, string, HashFuncString> dict;
    HashTable<string, string> dict;
    dict.Insert(make_pair("sort", "排序"));
    dict.Insert(make_pair("insert", "插入"));

}
void TestHashTable3()
{
    HashTable<int, int> ht1;
    int a[] = { 4, 44, 14, 5, 2, 22, 12, 5, 8, 10, 15 };
    for (auto e : a)
    {
        ht1.Insert(make_pair(e, e));
    }

    ht1.Insert(make_pair(11, 11));
    HashTable<int, int> ht2(ht1);
    HashTable<int, int> ht;
    ht = ht2;
    for (size_t i = 0; i < 53; ++i)
    {
        ht.Insert(make_pair(rand(), i));
    }

    ht.Insert(make_pair(rand(), 0));
}

• 结果：

4、开散列/哈希桶的实现

• 概念：

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

• 示图：

注：开散列中每个桶中放的都是发生哈希冲突的元素

• 开散列实现步骤：

1. 插入

通过哈希函数进行映射到对应的位置，我们的哈希桶选择存的元素是节点地址，那么直接选择头插就好，并不用担心哈希冲突，但是在插入之前需要进行遍历桶节点查看是否存在与插入的值相同的节点，没有才进行头插

2. 删除/查找

通过哈希函数映射到对应的位置，进行对该位置通的遍历再进行删除或查找

3. 开散列增容

桶的个数是一定的，随着元素的不断插入，每个桶中元素的个数不断增多，极端情况下，可能会导致一个桶中链表节点非常多，会影响的哈希表的性能，因此在一定条件下需要对哈希表进行增容

开散列最好的情况是：每个哈希桶中刚好挂一个节点，再继续插入元素时，每一次都会发生哈希冲突，因此，在元素个数刚好等于桶的个数时，可以给哈希表增容

科学增容：除留余数法，最好模一个素数

• 代码实现：

//获取下一个质数（接近二倍开辟）,比较科学减少冲突的取扩容大小的方式
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>
struct HashNode
{
    pair<K,V> _kv;
    HashNode* _next;

    HashNode(const pair<K,V>& kv)
        :_kv(kv)
        , _next(nullptr)
    {}
};
//取值比较仿函数及其特化
template<class K>
struct HashFunc
{
    size_t operator()(const K& key)
    {
        return key;
    }
};
template<>
struct HashFunc<string>
{
    size_t operator()(const string& str)
    {
        size_t hash = 0;
        for (int i = 0; i < str.size(); i++)
        {
            hash = hash * 131 + str[i];
        }
        return hash;
    }
};
//获取下一个质数（接近二倍开辟）,比较科学减少冲突的取扩容大小的方式
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:
    typedef HashTable<K, V, Hash> HT;
    HashTable()
        :_n(0)
    {}
    HashTable(const HT& ht)//拷贝构造
        :_n(ht._n)
    {
        if (ht._table.size() == 0)//空栈
            return;

        _table.resize(ht._table.size(), nullptr);//开辟空间并初始化
        for (int i = 0; i < ht._table.size(); i++)//遍历深拷贝
        {
            Node* cur = ht._table[i];
            while (cur)//遍历桶
            {
                Node* newnode = new Node(cur->_kv);
                newnode->_next = _table[i];//头插
                _table[i] = newnode;

                cur = cur->_next;
            }
        }
    }
    HT& operator=(const HT& ht)//赋值重载（现代式）
    {
        if (&ht != this)
        {
            HT temp(ht);//拷贝构造
            _table.swap(temp._table);
            _n = ht._n;
        }
        return *this;
    }
    ~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;//置空
        }
        _n = 0;
    }
    bool Insert(const pair<K,V>& kv)
    {
        Hash hf;
        //空哈希或者负载因子达到1时进行扩容
        if (_table.size() == _n)
        {
            //size_t newsize = _table.size() == 0 ? 10 : _table.size() * 2;
            size_t newsize = GetNextPrime(_table.size());//获取新的扩容大小
            vector<Node*> newdata;
            newdata.resize(newsize, nullptr);//开新的数组并扩容
            //将原数组中的节点重新映射插入到新数组
            for (size_t i = 0; i < _table.size(); ++i)
            {
                Node* cur = _table[i];
                while (cur)//挂有节点
                {
                    Node* next = cur->_next;//记录下一个节点
                    size_t index = hf(cur->_kv.first) % newsize;//重新计算下标

                    cur->_next = newdata[index];//头插
                    newdata[index] = cur;

                    cur = next;//移动
                }
                _table[i] = nullptr;//原数组置空
            }
            _table.swap(newdata);
        }

        size_t index = hf(kv.first) % _table.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;
        return true;
    }
    Node* Find(const K& key)
    {
        //空哈希
        if (_table.size() == 0)
            return nullptr;
        Hash hf;
        size_t index = hf(key) % _table.size();
        Node* cur = _table[index];
        while (cur)
        {
            if (cur->_kv.first == key)
                return cur;
            else
                cur = cur->_next;
        }
        return nullptr;
    }
    bool Erase(const K& key)
    {
        //空哈希
        if (_table.size() == 0)
            return false;
        Hash hf;
        size_t index = hf(key) % _table.size();
        Node* cur = _table[index];
        Node* parent = nullptr;
        while (cur)
        {
            if (cur->_kv.first == key)
            {
                if (parent == nullptr)//头结点进行头删
                    _table[index] = cur->_next;
                else
                    parent->_next = cur->_next;
                delete cur;
                --_n;
                return true;
            }
            else
            {
                parent = cur;
                cur = cur->_next;
            }
        }
        return false;
    }
private:
    vector<Node*> _table;
    size_t _n;
};

• 测试代码：

void TestHashTable1()
{
    HashTable<int, int> ht;
    int a[] = { 4, 44, 14, 5, 2, 22, 12, 5, 8, 10, 15 };
    for (auto e : a)
    {
        ht.Insert(make_pair(e, e));
    }

    ht.Insert(make_pair(11, 11));
    cout << ht.Find(44) << endl;
    ht.Erase(44);
    cout << ht.Find(44) << endl;
    ht.Erase(2);
}

void TestHashTable2()
{
    //HashTable<string, string, HashFuncString> dict;
    HashTable<string, string> dict;
    dict.Insert(make_pair("sort", "排序"));
    dict.Insert(make_pair("insert", "插入"));
    dict.Insert(make_pair("erase", "删除"));
}

void TestHashTable3()
{
    HashTable<int, int> ht1;
    int a[] = { 4, 44, 14, 5, 2, 22, 12, 5, 8, 10, 15 };
    for (auto e : a)
    {
        ht1.Insert(make_pair(e, e));
    }

    ht1.Insert(make_pair(11, 11));
    HashTable<int, int> ht2(ht1);
    HashTable<int, int> ht;
    ht = ht2;
    for (size_t i = 0; i < 53; ++i)
    {
        ht.Insert(make_pair(rand(), i));
    }

    ht.Insert(make_pair(rand(), 0));
}

• 结果：

• 开散列与闭散列比较：

应用链地址法处理溢出，需要增设链接指针，似乎增加了存储开销。事实上： 由于开地址法必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子a <= 0.7，而表项所占空间又比指针大的多，所以使用链地址法反而比开地址法节省存储空间

三、哈希封装实现unordered_map/unordered_set

这里使用哈希桶来封装实现map和set，哈希桶相对于哈希表来说没有哈希冲突，并且效率也十分好

使用哈希封装map/set和使用红黑树来封装的思维具有很多相似的地方

1、哈希桶的改装

• 注意：

1. 存储节点的数据类型对于set的K模型以及map的KV模型的兼容

• 示例代码：

//哈希储存的数据类型
template<class T>
struct HashNode
{
    T _data;//对于不同的上层可以存对应的K类型以及pair<K,V>
    HashNode* _next;

    HashNode(const T& data)
        :_data(data)
        , _next(nullptr)
    {}
};

• 解释：

1. 封装上层是set的话，则给底层哈希桶传入K类型，通过哈希桶再给底层的节点储存类型传入K类型

2. 封装上层是map的话，则给底层哈希桶传入pair<K,V>，通过哈希桶再给底层的节点储存类型传入pair<K,V>

2. 储存节点在不同封装的使用下进行对应的取出数据的key进行比较

• 示例代码：

//set上层
struct SetOfKey
{
    const K& operator()(const K& key)const
    {
        return key;
    }
};
typedef HashNode<K> Node;
typedef HashTable<K, K, Hash, SetOfKey> HT;
//map上层
struct MapOfKey
{
    const K& operator()(const pair<K,V>& kv)const
    {
        return kv.first;
    }
};
typedef HashNode<pair<K, V>> Node;
typedef HashTable<K, pair<K, V>, Hash, MapOfKey> HT;

• 解释：

上层封装中实现仿函数，给对应底层哈希传入对应使用的仿函数，便于进行使用对应的函数将储存数据的key继续取出比较

3. 哈希桶的迭代器如何实现，对于当前位置的迭代器怎么找到下个位置

• 示例代码：

template<class K, class T, class Hash, class KeyOfT>
struct HTIterator
{
    typedef HashNode<T> Node;
    typedef HashTable<K, T, Hash, KeyOfT> HT;
    typedef HTIterator<K, T, Hash, KeyOfT> Self;

    HT* _ht;
    Node* _node;
    HTIterator(Node* node, HT* ht)//不能加const，与成员变量不匹配
        :_ht(ht)
        , _node(node)
    {}
    bool operator==(const Self& s) const;
    bool operator!=(const Self& s) const;
    T& operator*();
    T* operator->();
    Self& operator++()
    {
        if (_node->_next)//存在下个节点
            _node = _node->_next;
        else//找下一个桶
        {
            Hash hf;
            KeyOfT kot;
            size_t index = hf(kot(_node->_data)) % _ht->_table.size();
            //kot仿函数为了取出储存类型数据的key，hf仿函数是实现对key类型的取整值，便于进行取模
            int i=index+1;
            for (; i < _ht->_table.size(); i++)
            {
                if (_ht->_table[i])
                {
                    _node = _ht->_table[i];
                    break;
                }
            }
            if (i == _ht->_table.size())//走到最后*
                _node = nullptr;
        }
        return *this;
    }
};

template<class K, class T, class Hash, class KeyOfT>
class HashTable
{
    typedef HashNode<T> Node;
    friend struct HTIterator<K, T, Hash, KeyOfT>;//*
public:
    typedef HashTable<K, T, Hash, KeyOfT> HT;
    typedef HTIterator<K, T, Hash, KeyOfT> Iterator;
    //...
}

注：对于哈希桶来说只有正向迭代器（单向），主要是底层是一个单向的链表，找上个节点地址比较麻烦，对于反向并不是很强求

• 解释：

1. 迭代器底层为哈希桶节点地址，同时还需要指向该哈希桶的指针，用来进行查找对应桶的下个节点地址，这里需要使用哈希的私有成员，所以我们需要让迭代器成为哈希桶的友元类，便于访问成员

2. 在实现的时候，我们发现，实现的迭代器包含了哈希桶类型，而哈希桶也包含了迭代器类型，两个类型互相去查找对方类型，这里就需要进行前置声明，避免有一方找不到对方类型

• 示例代码：

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

template<class K, class T, class Hash, class KeyOfT>
struct HTIterator
{
    typedef HashNode<T> Node;
    typedef HashTable<K, T, Hash, KeyOfT> HT;
    typedef HTIterator<K, T, Hash, KeyOfT> Self;
    HT* _ht;
    Node* _node;
    //...
    Self& operator++();
};

template<class K, class T, class Hash, class KeyOfT>
class HashTable
{
    typedef HashNode<T> Node;
    friend struct HTIterator<K, T, Hash, KeyOfT>;//*
public:
    typedef HashTable<K, T, Hash, KeyOfT> HT;
    typedef HTIterator<K, T, Hash, KeyOfT> Iterator;
    Iterator begin()
    {
        for (int i = 0; i < _table.size(); i++)
        {
            if (_table[i])
                return Iterator(_table[i], this);
        }
        return Iterator(nullptr, this);
    }
    Iterator end()
    {
        return Iterator(nullptr, this);
    }
    //...
}

• 哈希桶改装后完整代码：

#include<iostream>
#include<vector>
#include<string>
using namespace std;

//哈希储存的数据类型
template<class T>
struct HashNode
{
    T _data;//对于不同的上层可以存对应的K类型以及pair<K,V>
    HashNode* _next;

    HashNode(const T& data)
        :_data(data)
        , _next(nullptr)
    {}
};
//取值比较仿函数及其特化
template<class K>
struct HashFunc
{
    size_t operator()(const K& key)
    {
        return key;
    }
};
template<>
struct HashFunc<string>
{
    size_t operator()(const string& str)
    {
        size_t hash = 0;
        for (int i = 0; i < str.size(); i++)
        {
            hash = hash * 131 + str[i];
        }
        return hash;
    }
};
//获取下一个质数（接近二倍开辟）
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 T, class Hash, class KeyOfT>
class HashTable;

template<class K, class T, class Hash, class KeyOfT>
struct HTIterator
{
    typedef HashNode<T> Node;
    typedef HashTable<K, T, Hash, KeyOfT> HT;
    typedef HTIterator<K, T, Hash, KeyOfT> Self;

    HT* _ht;
    Node* _node;

    HTIterator(Node* node, HT* ht)//不能加const，与成员变量不匹配
        :_ht(ht)
        , _node(node)
    {}
    bool operator==(const Self& s) const
    {
        return _node == s._node;
    }
    bool operator!=(const Self& s) const
    {
        return _node != s._node;
    }
    T& operator*()
    {
        return _node->_data;
    }
    T* operator->()
    {
        return &_node->_data;
    }
    Self& operator++()
    {
        if (_node->_next)
            _node = _node->_next;
        else//找下一个桶
        {
            Hash hf;
            KeyOfT kot;
            size_t index = hf(kot(_node->_data)) % _ht->_table.size();
            int i=index+1;
            for (; i < _ht->_table.size(); i++)
            {
                if (_ht->_table[i])
                {
                    _node = _ht->_table[i];
                    break;
                }
            }
            if (i == _ht->_table.size())//走到最后*
                _node = nullptr;
        }
        return *this;
    }
};

template<class K, class T, class Hash, class KeyOfT>
class HashTable
{
    typedef HashNode<T> Node;
    friend struct HTIterator<K, T, Hash, KeyOfT>;//*
public:
    typedef HashTable<K, T, Hash, KeyOfT> HT;
    typedef HTIterator<K, T, Hash, KeyOfT> Iterator;

    HashTable()
        :_n(0)
    {}
    Iterator begin()
    {
        for (int i = 0; i < _table.size(); i++)
        {
            if (_table[i])
                return Iterator(_table[i], this);
        }
        return Iterator(nullptr, this);
    }
    Iterator end()
    {
        return Iterator(nullptr, this);
    }
    HashTable(const HT& ht)//拷贝构造
        :_n(ht._n)
    {
        if (ht._table.size() == 0)
            return;
        KeyOfT kot;
        _table.resize(ht._table.size(), nullptr);
        for (int i = 0; i < ht._table.size(); i++)
        {
            Node* cur = ht._table[i];
            while (cur)
            {
                Node* newnode = new Node(cur->_kv);
                newnode->_next = _table[i];
                _table[i] = newnode;
                cur = cur->_next;
            }
        }
    }
    HT& operator=(const HT& ht)
    {
        if (&ht != this)
        {
            HT temp(ht);
            _table.swap(temp._table);
            _n = ht._n;
        }
        return *this;
    }
    ~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;//置空
        }
        _n = 0;
    }
    pair<Iterator,bool> Insert(const T& data)
    {
        Hash hf;
        KeyOfT kot;
        //空哈希或者负载因子达到1
        if (_table.size() == _n)
        {
            size_t newsize = _table.size() == 0 ? 10 : _table.size() * 2;
            //size_t newsize = GetNextPrime(_table.size());//获取新大小
            vector<Node*> newdata;
            newdata.resize(newsize, nullptr);//开新的数组并扩容
            //将原数组中的节点重新插入到新数组
            for (size_t i = 0; i < _table.size(); ++i)
            {
                Node* cur = _table[i];//遍历数组
                while (cur)//挂有节点
                {
                    Node* next = cur->_next;//记录下一个节点
                    size_t index = hf(kot(cur->_data)) % newsize;//重新计算下标
                    //头插到新位置
                    cur->_next = newdata[index];
                    newdata[index] = cur;

                    cur = next;//移动
                }
                _table[i] = nullptr;
            }
            _table.swap(newdata);
        }
        //遍历查找
        size_t index = hf(kot(data)) % _table.size();
        Node* cur = _table[index];
        while (cur)
        {
            if (kot(cur->_data) == kot(data))
                return make_pair(Iterator(cur,this),false);
            else
                cur = cur->_next;
        }
        //头插
        Node* newnode = new Node(data);
        newnode->_next = _table[index];
        _table[index] = newnode;
        ++_n;
        return make_pair(Iterator(newnode,this),true);
    }
    Node* Find(const K& key)
    {
        //空哈希
        if (_table.size() == 0)
            return nullptr;
        Hash hf;
        KeyOfT kot;
        size_t index = hf(key) % _table.size();
        Node* cur = _table[index];
        while (cur)
        {
            if (kot(cur->_data) == key)
                return cur;
            else
                cur = cur->_next;
        }
        return nullptr;
    }
    bool Erase(const K& key)
    {
        //空哈希
        if (_table.size() == 0)
            return false;
        Hash hf;
        KeyOfT kot;
        size_t index = hf(key) % _table.size();
        Node* cur = _table[index];
        Node* parent = nullptr;
        while (cur)
        {
            if (kot(cur->_data) == key)
            {
                if (parent == nullptr)//头结点
                    _table[index] = cur->_next;
                else
                    parent->_next = cur->_next;
                delete cur;
                --_n;
                return true;
            }
            else
            {
                parent = cur;
                cur = cur->_next;
            }
        }
        return false;
    }
private:
    vector<Node*> _table;
    size_t _n=0;
};

2、unordered_map的上层封装

只需要在底层哈希桶的接口以及迭代器的接口，进行进一步的封装接口，便于外部进行调用

• 实现代码：

namespace cole
{
    template<class K,class V,class Hash=HashFunc<K>> 
    class unordered_map
    {
        struct MapOfKey
        {
            const K& operator()(const pair<K,V>& kv)const
            {
                return kv.first;
            }
        };
        typedef HashNode<pair<K, V>> Node;
    public:
        typedef HashTable<K, pair<K, V>, Hash, MapOfKey> HT;
        typedef typename HT::Iterator iterator;
        //获取类型中的类型需要加typename进行修饰，告诉编译器在实例化后进行查找对应的类型
        iterator begin()
        {
            return _ht.begin();
        }
        iterator end()
        {
            return _ht.end();
        }
        pair<iterator,bool> insert(const pair<K, V>& kv)
        {
            return _ht.Insert(kv);
        }
        V& operator[](const K& key)
        {
            auto ret = insert(make_pair(key, V()));
            return ret.first->second;
        }
        Node* find(const K& key)
        {
            return _ht.Find(key);
        }
        bool erase(const K& key)
        {
            return _ht.Erase(key);
        }
    private:
        HT _ht;
    };
    void test_unordered_map()
    {
        unordered_map<int, int> map;
        int arr[] = { 1,2,22,34,3,4,54,4,2,6,18,48,56,16,45,16,23,156,49,153,45,81,6,6,16,16,151,84894,11,6 };
        for (auto e : arr)
        {
            map.insert(make_pair(e, e));
        }
        for (auto& e : map)
        {
            cout << e.first << ":" << e.second << endl;
        }
        map[56] = 11;
        auto ret = map.find(4);
        cout << ret << endl;
        cout << map[4] << endl;
        map.erase(4);
        cout << map[4] << endl;
        cout << map[56] << endl;
        for (auto e : arr)
        {
            map.erase(e);
        }
        for (auto& e : map)
        {
            cout << e.first << ":" << e.second << endl;
        }
    }
}

• 测试结果：

3、unordered_set的上层封装

同样的对于set来说，也只需要在底层哈希桶的接口以及迭代器的接口，进行进一步的封装接口，便于外部进行调用

• 实现代码：

namespace cole
{
    template<class K , class Hash = HashFunc<K>>
    class unordered_set
    {
        struct SetOfKey
        {
            const K& operator()(const K& key)const
            {
                return key;
            }
        };
        typedef HashNode<K> Node;
    public:
        typedef HashTable<K, K, Hash, SetOfKey> HT;
        typedef typename HT::Iterator iterator;
        iterator begin()
        {
            return _ht.begin();
        }
        iterator end()
        {
            return _ht.end();
        }
        pair<iterator, bool> insert(const K& key)
        {
            return _ht.Insert(key);
        }
        /*V& operator[](const K& key)
        {
            auto ret = insert(make_pair(key, V()));
            return ret.first->second;
        }*/
        Node* find(const K& key)
        {
            return _ht.Find(key);
        }
        bool erase(const K& key)
        {
            return _ht.Erase(key);
        }
    private:
        HT _ht;
    };
    void test_unordered_set()
    {
        unordered_set<int> set;
        int arr[] = { 1,2,22,34,3,4,54,4,2,6,18,48,56,16,45,16,23,156,49,153,45,81,6,6,16,16,151,84894,11,6 };
        for (auto e : arr)
        {
            set.insert(e);
        }
        for (auto& e : set)
        {
            cout << e << endl;
        }
        auto ret = set.find(4);
        cout << ret << endl;
        set.erase(4);
        for (auto& e : set)
        {
            cout << e << endl;
        }
        for (auto e : arr)
        {
            set.erase(e);
        }
        for (auto& e : set)
        {
            cout << e<< endl;
        }
    }
}

• 测试结果：