那么状态的存在意义是什么？
💢举个例子：当我们需要在哈希表中查找一个数据40，这个数据我用哈希函数算出来他的位置是 0 ，但是我们不知道是不是存在哈希冲突，如果冲突就会向后偏移，我们就需要从 0 这个位置开始向后遍历，但是万万不能遍历完整个哈希表，这样就失去了哈希原本的意义
通过除留余数法得知元素在哈希表中的地址0
从0下标开始向后进行查找，若找到了40则说明存在，找到空位置判定为不存在即可
但是这样真的行得通吗？如果我是先删除了一个值1000，空出的空位在40之前，查找遇到空就停止了，此时并没有找到元素40，但是元素40却在哈希表中存在。
因此我们必须要给哈希表中的每个节点设置一个状态，有三种可能：当哈希表中的一个元素被删除后，我们不应该简单的将该位置的状态设置为EMPTY，而是应该将该位置的状态设置为DELETE
这样一来在查找的时候，遇到节点是EXIST或者DELETE的都要继续往后找，直到遇到空为止；而当我们插入元素的时候，可以将元素插入到状态为EMPTY或是DELETE的位置
所以节点的数据不仅仅要包括数据，还有包括当前的状态
//哈希节点存储结构 template<class K, class V> struct HashNode { pair<K, V> _kv; State _state = EMPTY; //状态 };
为了要在插入的时候算好负载因子，我们还要记录下哈希表中的有效数据，数据过多时进行扩容
templete<class K, class V> class HashTable { public: //... private: vector<HashData<K, V>> _tables;//哈希表 size_t _size;//存储多少个有效数据 };
🎨数据插入
步骤如下：
1.查找该键值对是否存在，存在则插入失败
2.判断是否需要扩容：哈希表为空 & 负载因子过大 都需要扩容
3. 插入键值对
4. 有效元素个数++
其中扩容方式如下：
如果是哈希表为空：就将哈希表的初始大小增大为10
如果是负载因子大于0.7： 先要创建一个新的哈希表（大小是原来的两倍），遍历原哈希表，旧表的数据映射到新表（此处复用插入），最后两个哈希表互换。
此处要注意：是将 旧表的数据重新映射到新表，而不是直接把原有的数据原封不动的搬下来，要重新计算在新表的位置，再插入
产生了哈希冲突，就会出现踩踏事件，不断往后挪，又因为每次插入的时候会判断负载因子，超出了就会扩容，所以哈希表不会被装满！
bool Insert(const pair<K, V>& kv) { //数据冗余 if (Find(kv.first)) return false; //负载因子到了就扩容 if (_tables.size() == 0 || 10 * _size / _tables.size() > 7)//扩容 { size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2; //创建新的哈希表，大小设置为原哈希表的2倍 HashTable<K, V> newHT; newHT._tables.resize(newSize); //旧表的数据映射到新表 for (auto e : _tables) { if (e._state == EXIST) { newHT.Insert(e._kv);//复用插入，因为已经有一个开好了的两倍内存的哈希表 } } _tables.swap(newHT._tables);//局部对象出作用域 析构 } //注意不能是capacity，size存的是有效字符个数，capacity是能存有效字符的容量 size_t hashi = kv.first % _tables.size(); //线性探测 while (_tables[hashi]._state == EXIST) { ++hashi; hashi %= _tables.size(); } /*Hash hash; size_t start = hash(kv.first) % _tables.size(); size_t i = 0; size_t hashi = start; //二次探测 while (_tables[hashi]._state == EXIST) { ++i; hashi = start + i*i; hashi %= _tables.size(); }*/ //数据插入 _tables[hashi]._kv = kv; _tables[hashi]._state = EXIST; ++_size; return true; }
🎨数据查找
步骤如下：
先判断哈希表大小是否，如果为零查找失败！
通过除留余数法算出对应的哈希地址
从哈希地址开始向后线性探测，直到遇到 EMPTY 位置还没找到则查找失败，如果遇到状态是DELETE的话，也要继续往后探测，因为该值已经被删掉了
💢注意：key相同的前提是状态不能是：删除。必须找到的是位置状态为 EXIST 且 key 值匹配，才算查找成功（不然找到的数据相同的，确实被删除了的）
HashData<K, V>* Find(const K& key) { //如果是空表就直接返回空 if (_tables.size() == 0) return nullptr; size_t start = key % _tables.size(); size_t hashi = start; while (_tables[hashi]._state != EMPTY)//不等于空 == 存在和删除都要继续找 { //key相同的前提是状态不能是：删除 if (_tables[hashi]._state != DELETE && _tables[hashi]._kv.first == key) { return &_tables[hashi]; } hashi++; hashi %= _tables.size(); if (hashi == start)//极端判断：兜兜转转一圈遇到了 { break; } } return nullptr; }
🎨数据删除
删除的步骤比较简单：修改状态 —— 减少元素个数
检查哈希表中是否存在该元素
如果存在，把其状态改成DELETE即可
哈希的有效元素个数-1
注意：我们这里是伪删除：只是修改了数据的状态变成DELETE，并没有把数据真正的删掉了，因为插入时候的数据可以覆盖原有的 —— 数据覆盖
bool Erase(const K& key) { HashData<K, V>* ret = Find(key); if (ret) //找到了 { ret->_state = DELETE; //状态改成删除 --_size; //有效元素个数-1 return true; } else { return false; } }
🎨仿函数
如果我们统计的是字符串的出现次数呢？kv.first还能取模吗？怎么样转化string呢 —— 其实大佬早就帮我们想到了
仿函数转化成一个可以取模的值
将key数据强制类型转换成size_t，如果key是string类型的就走string类型的特化版本
这样就可以不用显示的传属于哪个Hashfunc
涉及到了BKDR算法，因为ascll码值单纯地加起来，可能会出现相同现象，大佬推算出了这个算法
特化：符合string类型的优先走string类型
template<class K> struct Hashfunc { size_t operator()(const K& key) { return (size_t)key; } }; //特化版本 template<> struct Hashfunc<string> { //BKDR算法 size_t operator()(const string& key) { size_t val = 0; for (auto ch : key) { val *= 131;//为什么是131？经过了 val += ch; } return val; } };
六. 开散列的实现（哈希桶）
在开散列的哈希表中，哈希表的每个位置存储的实际上是某个单链表的头结点，即每个哈希桶中存储的数据实际上是一个结点类型，该结点类型除了存储所给数据之外，还需要存储一个结点指针用于指向下一个结点：next
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) {} };
为了使代码更有观赏感，对节点的类型进行typedef
typedef HashNode<K, V> Node;
这里与闭散列不同的是，不用给每个节点设置状态，因为将哈希地址相同的元素都放到了同一个哈希桶中了，不用再所谓的遍历找下一个空位置
当然了哈希桶也是要进行扩容的，在插入数据时也需要根据负载因子判断是否需要增容，所以我们也应该时刻存储整个哈希表中的有效元素个数，当负载因子过大时就应该进行哈希表的增容
template<class K, class V> struct HashTable { typedef HashNode<K, V> Node; public: //... private: vector<Node*> _table; size_t _size; //存储的有效数据个数 };
💦数据插入
步骤如下：
去重，如果有相同的值在哈希表中，则插入失败
判断是否需要扩容：哈希表为0、负载因子过大
插入数据
有效元素个数++
其中哈希表中的调整方式
若哈希表的大小为0，则将哈希表的初始大小设置为10
如果哈希表中负载因子等于1，则先创建一个新的表，遍历旧表，把节点都统统转移到新表上，最后交换两个表
注意：此处我们没有复用插入，是因为我们可以使用原本节点来对新的哈希表进行复制，这样就可以节省了新哈希表中的插入的节点了
bool Insert(const pair<K, V>& kv) { //去重 if (Find(kv.first)) return false; //负载因子到1就扩容 if (_size == _table.size()) { size_t newsize = _table.size == 0 ? 10 : 2 * _table.size(); vector<Node*> newTable; newTable.resize(newsize); //旧表节点移动映射到新表中 for (size_t i = 0; i < _table.size(); i++) { Node* cur = _table[i]; while (cur) { Node* next = cur->_next; //记录cur的下一个节点 size_t hashi = cur->_kv.first % newTable.size();//计算哈希地址 //头插 cur->_next = newTable[hashi]; newTable[hashi] = cur; cur = next; } _table[i] = nullptr;//原桶取完后置空 } //交换 _table.swap(newTable); } size_t hashi = kv.first % _table.size(); //头插 Node* newnode = new Node(kv); newnode->_next = _table[hashi]; // _table[hashi]指向的就是第一个结点 _table[hashi] = newnode; ++_size; return true; }
💦数据查找
步骤如下：
还是先判断哈希表是否为0，为0则查找失败
计算出对应哈希表中的地址
通过哈希地址找到了节点中的单链表，遍历单链表即可
//查找 Node* Find(const K& key) { if(_table.size() == nullptr)//哈希表为0，没得找 { return nullptr; } size_t hashi = kv.first % _table.size();//招牌先算出哈希地址 Node* cur = _table[hashi]; while (cur)//直到桶为空 { if (cur->_kv.first == key) { return true; } cur = cur->_next; } return nullptr;//遍历完桶，都没找到，返回空 }
💦数据删除
通过哈希函数计算出对应的哈希桶编号
遍历哈希桶，寻找待删除节点
删除节点：头删 or 中间删
有效元素个数-1
注意： 这里我们不调用find函数，因为是单链表，我们还要自己去找prev，所以干脆我们自己去查找好了
bool Erase(const K& key) { if(_table.size() == 0) { return nullptr; } //1、通过哈希函数计算出对应的哈希桶编号hashi size_t hashi = key % _table.size(); Node* prev = nullptr; Node* cur = _table[hashi]; while (cur) { if (cur->_kv.first == key) { //头删 if (prev == nullptr) { _table[hashi] = cur->_next;//将第一个结点从该哈希桶中移除 delete cur; } else //中间删除 { prev->_next = cur->_next;//将该结点从哈希桶中移除 delete cur; } --_size; return true; } prev = cur; cur = cur->_next; } return false; }
哈希表的大小为什么建议是素数？
其实哈希表在使用除留余数法时，为了减少哈希冲突的次数，很多地方都使用了素数来规定哈希表的大小
下面用合数（非素数）10和素数11来进行说明。
合数10的因子有：1，2，5，10。
素数11的因子有：1，11。
我们选取下面这五个序列：
间隔为1的序列：s1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
间隔为2的序列：s2 = {2, 4, 6, 8,10, 12, 14, 16, 18, 20}
间隔为5的序列：s3 = {5, 10, 15, 20, 25, 30, 35, 40,45, 50}
间隔为10的序列：s4 = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100}
间隔为11的序列：s5 = {11, 22, 33, 44, 55, 66, 77, 88, 99, 110}
对这几个序列分别放进哈希表，分别观察，不难得出他们的规律：
如果一个序列中，每个元素之间的间隔为1，那么不管哈希表的大小为几，该序列插入哈希表后都是均匀分布的
如果一个序列中，每个元素之间的间隔刚好是哈希表大小或哈希表的倍数，他们将全部产生冲突
如果一个序列中，序列的间隔恰好是哈希表大小的因子，那么哈希表的分布就会产生间隔，反之则不会。
综上所述，某个随机序列当中，每个元素之间的间隔是不定的，为了尽量减少冲突，我们就需要让哈希表的大小的因子最少，此时素数就可以视为最佳方案
实现方案
很明显如果还是采用传统的 2 倍扩容就会不符合素数大小的要求，所以我们不妨直接将素数大小存储在数组里，我们规定下面这个数组即可，其中元素近似 2 倍增长
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 GetNextPrime(size_t prime) { const int PRIMECOUNT = 28; size_t i = 0; for (i = 0; i < PRIMECOUNT; i++) { if (primeList[i] > prime) return primeList[i]; } return primeList[i]; }
