参考博客：C+±–哈希

1. 哈希表简介

1.1 概念

“散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

1.1.1 散列函数

将键值经过某些加工得到另一个值的函数。

常见函数方法：

1. 直接定址法：取关键字或关键字的某个线性函数值为哈希地址。
2. 数字分析法：假设关键字是以r为基的数（如：以10为基的十进制数），并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。
3. 平方取中法：取关键字平方后的中间几位为哈希地址。
4. 折叠法：将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址，这方法称为折叠法。
5. 除留余数法：取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。即H(key)=key MOD p,(p<=m)，这是一种最简单，也是最常用的构造哈希函数的方法。它不仅可以对关键字直接取模（MOD），也可在折叠、平方取中等运算之后取模。
6. 随机数法：选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key)=random(key)，其中random为随机函数。通常，当关键字长度不等时采用此法构造哈希函数较切当。

1.1.2 关键值key

用于访问数据储存位置的值。

1.1.3 散列表

散列表就是一个数组。它将关键值key通过散列函数生成一个值，这个值就是访问数组的下标。

注意：数组中储存的元素是键值对（key-value）。

1.2 哈希表扩容

当哈希表为空，或其被占的位置比较多的时候，出现哈希冲突的概率也就变高了，此时需要进行扩容。为判断是否需要扩容，我们需要了解负载因子的概念。

1.2.1 负载因子

简单点说就是已经被占的位置与总位置的百分比。比如说当前共有十个位置，其中七个被占，那此时的负载因子就是70%。党负载因子大于某个临界的时候，我们就有必要对哈希表进行扩容。

1.2.2 扩容方法

对哈希表进行扩容，并不是对原数组扩容，而是建立一个两倍大的新数组，把原数组的元素重新hash进新数组。

1.3 哈希冲突

简单来说就是两个不同的关键值通过散列函数，得到同一个坐标值。

处理哈希冲突常用的方式为：闭散列和开散列。

1.3.1 闭散列

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

需要注意的是，在使用闭散列方法时，不能随便物理删除一个元素，这样会影响其他元素的查找。所以我们使用标记的方式伪删除一个元素。

构造代码(简单模版)：

#include <iostream>
using namespace::std;

enum State {
    EMPTY,
    EXIST,
    DELETE
};

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

// 封装哈希表
template<class K, class V>
class HashTable {
public:
    // 插入
    bool Insert(const pair<K, V>& kv) {
        // ...
        return true;
    }
    // 查询
    HashData<K, V>* Find(const K& key) {
        // ...
        return nullptr;
    }
    // 删除
    bool Erase(const K& key) {
        // ...
        return true;
    }
    

private:
    // 哈希函数
    size_t HasnFunc(const K& key) {
        return key % _tables.size(); // 可替换为其他方法
    }
private:
    vector<HashData<K, V>> _tables;
    size_t size = 0;
};

各函数具体实现：
Insert：

// 插入
    bool Insert(const pair<K, V>& kv) {
        // 如果关键值重复，返回false
        if (Find(kv.first)) {
            return false;
        }
        // 表为空或负载因子超过70%扩容
        if (_tables.stize() == 0 || 100 * _size / _tables.size() >= 70) {
            size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
            HashTable<K, V> newHashTable;
            newHashTable._tables.resize(newSize);
            // 旧表数据hash进新表
            for (auto e : _tables) {
                if (e._state == EXIST) {
                    newHashTable.Insert(e._kv);
                }
            }
            _tables.swap(newHashTable._tables);
        }
        
        // 线性检测
        size_t hashi = HasnFunc(kv.first);
        while (_tables[hashi]._state == EXIST) {
            if (hashi + 1 == _tables.size()) {
                hashi = 0;
            }
            hashi++;
        }
        _tables[hashi]._kv = kv;
        _tables[hashi]._state = EXIST;
        _size++;
        
        return true;
    }

Find:

// 查询
    HashData<K, V>* Find(const K& key) {
        if (_tables.size() == 0) {
            return nullptr;
        }
        
        size_t hashi = HasnFunc(key);
        while (_tables[hashi]._state != EMPTY) {
            if (_tables[hashi]._state != DELETE && _tables[hashi]._kv.first == key) {
                return &_tables[hashi];
            }
            hashi++;
            if (hashi == _tables.size()) {
                hashi = 0;
            }
        }
        return nullptr;
    }

Erase:

// 删除
    bool Erase(const K& key) {
        HashData<K, V>* ret = Find(key);
        if (ret) {
            ret->_state = DELETE;
            _size--;
            return true;
        }
        return false;
    }

在这里，我使用的是线性探测，但是当某一个位置冲突过多时会引起一片冲突。这时可以考虑2次探测（每次以2的i次方进行探测）。

仅以Insert代码举例：

	bool Insert(const pair<K, V>& kv) {
        // 如果关键值重复，返回false
        if (Find(kv.first)) {
            return false;
        }
        // 表为空或负载因子超过70%扩容
        if (_tables.stize() == 0 || 100 * _size / _tables.size() >= 70) {
            size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
            HashTable<K, V> newHashTable;
            newHashTable._tables.resize(newSize);
            // 旧表数据hash进新表
            for (auto e : _tables) {
                if (e._state == EXIST) {
                    newHashTable.Insert(e._kv);
                }
            }
            _tables.swap(newHashTable._tables);
        }
        // 二次检测
        size_t start = HasnFunc(kv.first);
        size_t i = 0;
        size_t hashi = start;
        while (_tables[hashi]._state == EXIST) {
            i++;
            hashi = start + i*i;
            if (hashi >= _tables.size()) {
                hashi %= _tables.size();
            }
        }
        _tables[hashi]._kv = kv;
        _tables[hashi]._state = EXIST;
        _size++;
        
        return true;
    }

1.3.2 开散列

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

构造代码（简单代码）：

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 HashTable {
    typedef  HashNode<K, V> Node;
public:
    bool Insert(const pair<K, V>) {
        return true;
    }
    
    Node* Find(const K& key) {
        return nullptr;
    }
    
    bool Erase(const K& key) {
        return true;
    }
public:
    size_t HasnFunc(const K& key) {
        return key % (_tables.size() + 1); // 可替换为其他方法
    }
private:
    vector<Node*> _tables;
    size_t _size = 0;
};

各函数具体实现：
Insert：

bool Insert(const pair<K, V>& kv) {
        if (Find(kv.first)) {
            return false;
        }
        // 负载因子到1就扩容
        if (_size == _tables.size()) {
            size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
            // 旧表元素hash进新表
            HashTable<K, V> newHashTable;
            newHashTable._tables.resize(newSize, nullptr);
            // 旧表数据hash进新表
            for (size_t i = 0; i < _tables.size(); i++) {
                Node* cur = _tables[i];
                while (cur) {
                    Node* next = cur->_next;
                    
                    size_t hashi = HasnFunc(cur->_kv.first);
                    cur->_next = newHashTable[hashi];
                    newHashTable[hashi] = cur;
                    
                    cur = next;
                }
                _tables[i] = nullptr;
            }
            _tables.swap(newHashTable._tables);
        }
        
        size_t hashi = HasnFunc(kv.first);
        // 头插
        Node* newnode = new Node(kv);
        newnode->_next = _tables[hashi];
        _tables[hashi] = newnode;
        _size++;
        
        return true;
    }

Find:

Node* Find(const K& key) {
        if (_tables.size() == 0) {
            return nullptr;
        }
        
        size_t hashi = HasnFunc(key);
        Node* cur = _tables[hashi];
        while (cur) {
            if (cur->_kv.first == key) {
                return cur;
            }
            cur = cur->_next;
        }
        return nullptr;
    }

Erase:

bool Erase(const K& key) {
        if (_tables.size() == 0) {
            return false;
        }
        
        size_t hashi = HasnFunc(key);
        Node* prev = nullptr;
        Node* cur = _tables[hashi];
        while (cur) {
            if (cur->_kv.first == key) {
                // 头删
                if (prev == nullptr) {
                    _tables[hashi] = cur->_next;
                } else {
                    prev->_next = cur->_next;
                }
                delete cur;
                _size--;
                return  true;
            }
            prev = cur;
            cur = cur->_next;
        }
        return false;
    }

如果冲突过多的话，这块的链表会变得比较长，怎么处理呢？这里举个例子吧，拿java集合类中的HashMap来说吧，如果这里的链表长度大于等于8的话，链表就会转换成树结构，当然如果长度小于等于6的话，就会还原链表。以此来解决链表过长导致的性能问题。

2 map、hash_map、unordered_map

2.1 map

map以模板(泛型)方式实现，可以存储任意类型的数据，包括使用者自定义的数据类型。Map主要用于资料一对一映射(one-to-one)的情況，map內部的实现自建一颗红黑树，这颗树具有对数据自动排序的功能。在map内部所有的数据都是有序的。

它的查找时间复杂度O(logN)的，对于数量庞大的数据来说，查找还是太慢了。

2.2 hash_map

hash_map是C++ STL中的一个哈希表容器，用于将键映射到值。其工作方式类似于map，但效率更高，因为它是通过哈希函数实现的。

hash_map可以用于存储任何类型的键值对，只要满足以下要求：

• 键必须是可哈希的（即可以通过哈希函数计算出一个哈希值）。
• 键必须支持比较操作，以便在哈希表中查找元素。
• 值可以是任何类型。

hash_map提供了常见的哈希表操作，例如插入、查找、删除元素等。其时间复杂度通常为O(1)，因此在大多数情况下，使用hash_map要比使用其他容器更有效率。

2.3 unordered_map

实际上，最初的 C++ 标准库中没有类似 hash_map 的实现，但不同实现者自己提供了非标准的 hash_map。 因为这些实现不是遵循标准编写的，所以它们在功能和性能保证方面都有细微差别。

从 C++ 11 开始，hash_map 实现已被添加到标准库中。但为了防止与已开发的代码存在冲突，决定使用替代名称 unordered_map。这个名字其实更具描述性，因为它暗示了该类元素的无序性。

2.3.1 简单介绍

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

2.3.2 unordered_map接口说明

1. unordered_map构造

2. unordered_map的容量

3. unordered_map的迭代器

4. unordered_map的元素访问

5. unordered_map的查询

注意：unordered_map中key是不能重复的，因此count函数的返回值最大为1

6. unordered_map的修改操作

7. unordered_map的桶操作