一、哈希表的基本概念
1、负载因子：假设哈希表中已经映射存储了N个值，哈希表的大小为M，那么负载因子 = N / M，负载因子有些地⽅也翻译为载荷因子/装载因子等，他的英文为load/factor。负载因子越大，哈希冲突的概率越高，空间利用率越高；负载因子越小，哈希冲突的概率越低，空间利用率越低
2、哈希函数：这是哈希表的核心，它将键（Key）映射为一个数组索引（通常称为哈希值或哈希码）。哈希函数的设计至关重要，因为它直接影响到哈希表的性能。一个好的哈希函数应该能够均匀地分布键的哈希值，以减少哈希冲突。
3、哈希表（数组）：哈希表本质上是一个数组，它的大小（即数组的长度）是预先确定的。数组的每个位置都对应一个哈希值，该位置用于存储键和值的映射关系。
4、哈希冲突：由于哈希函数可能会将不同的键映射到相同的哈希值，因此需要一种机制来处理这种情况。常见的处理哈希冲突的方法有开放寻址法（如线性探测、二次探测等）和链地址法（也称为哈希链法）
二、开放定址法代码实现一个哈希表
总代码
template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};template<>
struct HashFunc<string>
{size_t operator()(const string& s){// BKDRsize_t hash = 0;for (auto ch : s){hash += ch;hash *= 131;}return hash;}
};struct MapKeyOfT
{const K& operator()(const pair<K, V>& kv){return kv.first;}
};template<class K, class V, class MapKeyOfT, class HashFunc>
class Hashtable
{
public:Hashtable():_table(__stl_next_prime(0)),_n(0){}inline unsigned long __stl_next_prime(unsigned long n){// Note: assumes long is at least 32 bits.static const int __stl_num_primes = 28;static const unsigned long __stl_prime_list[__stl_num_primes] = {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};const unsigned long* first = __stl_prime_list;const unsigned long* last = __stl_prime_list + __stl_num_primes;const unsigned long* pos = lower_bound(first, last, n);return pos == last ? *(last - 1) : *pos;}bool Insert(const pair<K, V>& kv){if (_n * 10 / _table.size() >= 7){Hashtable<K, V> newt;newt._table.resize(__stl_next_prime(_table.size() + 1));for (auto e : _table){if (e._state == EXIST){newt.Insert(e._kv);}}_table.swap(newt._table);}MapKeyOfT kot;HashFunc hash;size_t hash0 = hash(kot(kv) % _table.size();size_t hash1 = hash0;size_t i = 1;while (_table[hash1]._state != EMPTY){hash1 = (hash0 + i) % _table.size();i++;}_table[hash1]._kv = kv;_table[hash1]._state = EXIST;_n++;return true;}bool Erase(const K& key){Hashtable<K, V, MapKeyOfT, HashFunc>* pos = Find(key);if (pos){pos->_state = DELETE;_n--;return true;}elsereturn false;}Hashtable<K, V>* Find(const K& key){MapKeyOfT kot;HashFunc hash; size_t hash0 = hash(kot(key)) % _tables.size();size_t hashi = hash0;size_t i = 1;while (_tables[hashi]._state != EMPTY){if (_tables[hashi]._state == EXIST&& _tables[hashi]._kv.first == key){return &_tables[hashi];}// 线性探测hashi = (hash0 + i) % _tables.size();++i;}return nullptr;}private:vector<HashtableDate<K, V>> _table;size_t _n;
};其基本思想是，当发生哈希冲突（即两个不同的键被映射到哈希表的同一位置）时，通过一定的探测方法找到下一个可用的哈希地址。
原理
哈希函数：首先，需要一个哈希函数将键映射到哈希表的索引。常见的哈希函数包括取模运算（例如，hash_value = key % _table.size（）），其中_table.size（）是哈希表的大小。
冲突处理：当发生冲突时，开放定址法通过探测序列来找到下一个可用的位置。探测序列可以是线性的、二次的或基于另一个哈希函数的。
线性探测：每次冲突时，按顺序检查下一个位置，直到找到一个空位置或回到起始位置。
开放定址法的哈希表结构里应有一个枚举类型来记录每个位置的状态（存在、空和删除）
用一个 HashData 结构体来存放节点的数据和状态，最后用 HashTable 类里用一个vector对象来存放一个一个的节点。
开放定址法的哈希表结构：
enum State
{EXIST,EMPTY,DELETE
};template<class K, class V>
struct HashData
{pair<K, V> _kv;State _state = EMPTY;
};template<class K, class V，class>
class HashTable
{
private:vector<HashData<K, V>> _tables;size_t _n = 0; // 表中存储数据个数
};哈希表的插入
如果我们vector开11个空间，当我们要插入数据的时候，将插入的值 % 容器的容量得到要映射的位置，然后将值插入在这个位置上。
例如：插入{19 , 30 , 52 , 63 , 11 , 22}，当插入 19 的时候，先用 19 % 11 得到 8，将 19 插入在 8这个位置上，但当插入 30 的时候，映射的位置也是 8 ，这时候就发生了哈希冲突， 我们需要判断一下下一个位置能否插入，遇到状态为空的时候就可以插入了，重复存在，直至负载因子 >= 0.7。
bool Insert(const pair<K, V>& kv)
{size_t hash0 = kv.first % _table.size();size_t hash1 = hash0;size_t i = 1;while (_table[hash1]._state != EMPTY){hash1 = (hash0 + i) % _table.size();i++;}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;
}为了方便取到 pair <K, V> 里的K的数据或类型，我们可以写一个仿函数来得到。
struct MapKeyOfT
{const K& operator()(const pair<K, V>& kv){return kv.first;}
};但这里的类型刚刚好是整形，可以用 % ，如果我们要插入字符类型的数据怎么办，它不能映射到对应的值，这时候我们可以写一个仿函数来使得 字符类型的数据变为整形类型。
template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};template<>
struct HashFunc<string>
{size_t operator()(const string& s){// BKDRsize_t hash = 0;for (auto ch : s){hash += ch;hash *= 131;}return hash;}
};这时候我们的插入代码就变成这样了
bool Insert(const pair<K, V>& kv)
{HashFunc hash;MapKeyOfT kot;size_t hash0 = hash(kot(kv) % _table.size();size_t hash1 = hash0;size_t i = 1;while (_table[hash1]._state != EMPTY){hash1 = (hash0 + i) % _table.size();i++;}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;
}但当 负载因子 >= 0.7 的时候，我们需要扩容，确保 负载因子 <= 0.7。
bool Insert(const pair<K, V>& kv){if (_n * 10 / _table.size() >= 7){Hashtable<K, V> newt;newt._table.resize(__stl_next_prime(_table.size() + 1));for (auto e : _table){if (e._state == EXIST){newt.Insert(e._kv);}}_table.swap(newt._table);}MapKeyOfT kot;HashFunc hash;size_t hash0 = hash(kot(kv) % _table.size();size_t hash1 = hash0;size_t i = 1;while (_table[hash1]._state != EMPTY){hash1 = (hash0 + i) % _table.size();i++;}_table[hash1]._kv = kv;_table[hash1]._state = EXIST;_n++;return true;}
}哈希表的查找
我们从要查找的值的映射开始寻找，一个接一个的寻找，若都找到状态为空的位置都没有找到，那就查找失败，返回nullptr。
Hashtable<K, V>* Find(const K& key)
{MapKeyOfT kot;HashFunc hash; size_t hash0 = hash(kot(key)) % _tables.size();size_t hashi = hash0;size_t i = 1;while (_tables[hashi]._state != EMPTY){if (_tables[hashi]._state == EXIST&& _tables[hashi]._kv.first == key){return &_tables[hashi];}// 线性探测hashi = (hash0 + i) % _tables.size();++i;}return nullptr;
}哈希表的删除
哈希表的删除，我们只需要将找到位置的状态设为空状态即可。
bool Erase(const K& key)
{Hashtable<K, V, MapKeyOfT, HashFunc>* pos = Find(key);if (pos){pos->_state = DELETE;_n--;return true;}elsereturn false;
}
