• C++ - 开放地址法的哈希介绍 - 哈希表的仿函数例子

    前言

    哈希其实是一种搜索方式，像暴力查找，有序数组的二分查找，二分查找就很快了，可以达到O(log n)。但是有序数组有一个 弊端，就是要先进行排序，这就有消耗，这还好，当要插入删除修改数据的时候，那么这种效率就不可看了。

    然后就有了平衡搜索树的出现：

    比如 AVL树 ， B树 ， B+树 ， 红黑树等等，可以看下面几篇博客的讲解：
    C++ - set 和 map 的实现（下篇）- set 和 map 的迭代器实现_chihiro1122的博客-CSDN博客

    C++ - map 和 set 的模拟实现上篇 - 红黑树当中的仿函数 - 红黑树的迭代器实现-CSDN博客

    C++ - 红黑树 介绍 和 实现-CSDN博客

    C++ - AVL树实现（下篇）- 调试小技巧_chihiro1122的博客-CSDN博客

    C++ - AVL 树 介绍 和 实现 （上篇）-CSDN博客

     平衡搜索树好就好在，它的增删查改都是 O（log N） ，它插入删除虽然在实现上很复杂，但是真正运行起来，效率非常高，因为 其中的 旋转等等的操作都没有用到多少循环，都是 O（1）级别的。

    但是平衡搜索树也是有缺点的，比如当数据量重复或者 相对有序或有序的情况下，虽然查找还是O(log n） 级别的，但是插入和删除在效率上就会明显下降，但是最多也就下降到 二分查找的级别。因为比如是有序数据的话，它会蜕变成类似链表的形式。

    所以，就有了哈希 更 平衡二叉树补全。两者之间可谓是 各有各的优缺点，具体可以看这篇博客：
    C++ - unordered系列关联式容器介绍 - 和 set map 的比较-CSDN博客

     其中的 set 和 map 底层是红黑树实现，而 unordered_map 和 unordered_set 底层是哈希。

     认识哈希

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

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

     哈希（散列表）：存储的值跟存储的位置建立出一个映射关系（对应关系）。这个映射关系是使用 函数来表示和实现的。把 存储的值跟存储的位置建立出一种规则，在查找的时候，可以按照这个规则，快速的跳过不需要遍历的数据，跳跃式的查找到我们想要查找到的数据。也就是在查找当中，有了规则，有了查找的方向，不再像暴力查找当中一样，一头查到底，无向的查找。

    比如计数排序当中就有哈希的影子：数据结构-基数排序_chihiro1122的博客-CSDN博客

     哈希寻找数据的过程，就跟在学校图书馆找书差不多，图书馆一般是分区的，比如 有 计算机类的，有金融类的等等，而在这些区当中又是按照 拼音，比如 开头是A 的放在一堆，B 开头的放在 一堆的···········：

     我们发现，不管是 计数排序还是 上述图书馆排列书籍，排列出来的区间都太分散了，不太好寻找。像上述的属于 直接定值法，比如上述图书馆就是按照字母的大小排序，直接和存储地址进行匹配，适合于数据比较集中的，但是遇到数据比较分散的就不适合了。

    当，数据比较分散，不好用直接定值法，所以就有人提出了除留余数法。他就是创建一个规则，然后数据按照这个规则计算出应该存储的应该存储的位置，在除留余数法的数组当中，同样有多个区，每一个区当中都有一个数的映射位置，每次存储数据可以按照这个映射关系来在这个表当中进行存储，这样每个数据存储的位置就有了规则，在查找的时候，计算出需要查找的数在这个区当中的映射位置，如果没有，就查找往下遍历元素，具体可以参考 下述 线性探测。

    在数据结构当中学习的哈希表，一般是使用下述这种规则进行存储的：

    hash = key % size;

    其中的 key 是要存储的数据，size 的值一般是刚开始给数据个数，或者是小一些的数，这样就可以以 size 大小把 整个数组分成一个一个区间，而每一个 key 值 模上 size 之后肯定是 0 - size 的数，那么就可以在某一个区间当中有一席之地了。

     但是这一种方法有一个很大弊端，它只能支持 类似整形这样 数据，如果是string类型的数据，或者是一些自定义类型，那么上述的规则就不适用了，但是总会有解决办法的，具体在哈希实现当中具体介绍。

    建立一个哈希表不一定一定要是用 除留余数法，还有很多方法可以建立，如下所示：


    平方取中法
    假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址；再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况。


    折叠法
    折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况。


     随机数法
    选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中
    random为随机数函数。通常应用于关键字长度不等时采用此法。


    数学分析法
    设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。

    本博客主要介绍 除留余数法。
     

     哈希冲突

     相信你已经猜到会有冲突的情况了，就是前面插入的数据肯定会占用某一个区间的某一个映射位置，那么在后序插入的数据肯定会有情况，在规则计算之后，和之前插入数据的位置冲突，图喜爱图所示：
     

     我们发现，当我们想要插入 23 这个数据的时候，23  % 8 = 7，那么我们应该插入到 第一区间当中的 7 这个位置，但是 这个位置已经被 15 占了。这种情况就是哈希冲突。

     闭散列

    线性探测

     解决哈希冲突的有三种解决方案，这里先不列出，先举个闭散列当中的线性探测进行理解，因为三种解决方案虽然不一样，但是大思路都是往后寻找可以插入的位置：

    如果我们当前想插入数据 ，和数组当中的某个数据的存储位置冲突了，按规则，找下一个位置（占用几个别人的位置）。

     如上述所示，我们当前要插入元素 44 ，原本插入的位置应该是 下标为 4 的位置，但是这个位置就已经被 4 给占用了，发生了哈希冲突。此时就要在这个区间当中往后寻找空位置，如上，就找到了 8 这个位置是空的，那么就在这个位置进行插入。

     如上述所示，如果当前到插入的位置已经被人占了，往后寻找位置的时候已经超出了 capacity 数组大小了，首先要做的不是开空间，而是从这个区间的首元素地址开始再次寻找前面是否有空位置，如果有，就插入，没有才会进行扩容操作。

     如果，没有像上述一样先往前寻找，没有空位再扩容，就是如果冲突就扩容的话，就会造成下述的情况的空间浪费：

     如上所示，数组此时就之后一个19 元素，如果我们插入一个 9 的话，就会发生哈希冲突，那么正常应该是先从头开始寻找，然后插入到第一个位置，如果直接扩容的话，前面这个数组空间此时就极大的浪费了。

    此时 查找 44 是这样查找的：
    首先计算 44 的应该存储位置，也就是 下标为 4 的这个位置，如果这个位置不是 44 的话，那么就要往后线性探测，找到了就停止。

    如果此时要寻找的是 54 ，54 是数组当中没有的，那么首先一样找到 下标为 4 的位置，然后往后寻找，找到9 的时候这个区间就到头了，就要往前寻找，当找到 位置0的时候，因为 位置 0 是空，此时就停止了；或者再次走到 下标为4 的这个位置，都代表着这个区间当中没有这个元素。

     按照上述这种查找规则，意味着，如果表当中的很满的话，查找效率会下降，所以这也就引出了一个问题，哈希表不会纵容这种事情的发生，肯定不会让一个区间当中的数据太满的。那么就会涉及到 什么时候扩容的问题了。这个问题后面再介绍。

     哈希表的删除数据也是有讲究的，比如要上述数组的 6 这个元素，不能直接删除掉6 这个元素，小的影响是 ，如果把 上述的 1   4    5   6   7   9  都删除了，值剩下一个 44 ，那么其中的空间不就浪费了。

    更大影响是，如果直接删除了 6 这个元素，那么 下标为 6 的这个位置就是空了，那么在删除之后，去查找 44 这个元素的时候，从4 位置开始遍历，按照上述的查找规则，遇到空就停止了，但是此时没有查找到 44 这个元素，但是这个元素到 数组当中是真实存在的，那么就出大问题了。

     也不能直接填上一个无效值，应为我们当前要实现的哈希表要是一个模版，泛型编程要能存储多种数据，所以无效值是什么都不太好。

    我们选择标记的方式解决上述问题：

    数组当中的一个元素不止存储值，还有存储该元素当前的一个状态，有三种状态：

    • EXITS：存在
    • EMPTY：空
    • DELETE：删除

     所以现在删除这个 6 ，就不要真删除这个 6 了，直接把这个元素的状态修改为 DELETE就行了。

    按照上述进行修改之后，我们在寻找 44 的时候，是遇到 EMPTY 才会停止，遇到 DELETE 就不会停止了。

    哈希表的闭散列线性探测方式实现

     insert（）插入函数

     按照上述对 线性探测的说明和一些细节的探讨，我们先来实现一下 哈希表的 闭散列当中的 线性探测：
    因为哈希表的物理存储是一个数组，所以直接使用 vector 来存储数据。还考虑到 一个元素有三种状态，所以，我们创建一个枚举类型来列举出着三种类型，方便后续修改这三种状态。

    在 vector 当中就有 _size这个成员变量来维护vector 当中的有效数据个数，但是这时不够的，我们还需要在哈希当中创建一个成员变量 _n 用于存储 哈希当中的有效数据个数。以为 哈希当中的数据不是挨着存储的，他是哈希又叫散列表，其中的元素是散着存储的，而在 vector 当中的 _size 存储的是vector 当中的有效数据个数，这两者之间是不一样的，我们用一张图来解释：
     

     当表中的数据没有满的时候， vector 当中的 _size 存储的是 0 - 9 整个数组的长度，而 哈希当中的 _n 存储是在这个表当中没有不为空的数据个数。

    我们需要一个 _n 用于维护不为空的数据个数，当这个表满了或者快满的时候，我们需要进行扩容。关于扩容，我们先实现哈希的基本算法之后再来说明。

     某一个数据如果要插入到表当中，需要一个起始位置，我们先来计算这个起始位置：

    首先我们要考虑的是，我们取模使用的 数，应该是 vector 当中的 _capacity 还是 _size。

    如果我们使用 _capacity 的话，那么下述就不能使用 vector当中的 operator[]（）这个函数来对其中的成员当中的属性进行修改了，因为，operator[]() 这个函数，只能访问 下标小于 size（） 的元素，不能访问超出 size（）的元素，比如：
     

     现在我们想插入一个 18 ，那么如果是按照 capacity 20 来取模的话，就是  size - capacity 中间的这个位置，那么此时的这个位置就会超出 operator[]（）这个函数访问的元素范围，在这个函数当中就会直接断言报错。空间确实是开出了 capacity 的大小，但是 在 operator[]() 当中就会限制在 size（）当中去访问。

     所以，我们为了后续能够使用 operator[]（）更方便的修改 vector 也就是哈希表当中的元素，我们还是控制 在 size（）之内。

     而且，我们还考虑到 ，让 size 和 capacity 相等，这样的话就会大大的减少空间的浪费。控制相等我们可以使用 vector 当中的 resize（）函数来进行扩容，这样就可以保持size 和 capacity 相等。

    现在解决了初始位置的问题，但是如果初始位置上有元素，那么我们还需要往后继续遍历，当访问到 某一个元素的 状态是 EMPTY 或者是 DELETE的就可以插入了。因为 DELETE 的元素，在顺序表当中是要被直接删除掉然后往前挪数据的，但是在哈希表当中，我们引入了状态这个值，那么可以对元素进行个性化的赋值，直到这个元素当中处于哪一种状态，所以，当我们给这个元素的状态修改为 DELETE 就直接代表这个元素已经不要了。 

     当我们实现好基础插入逻辑之后，就要来看看 扩容问题了。

    在介绍线性探测的时候说过，哈希表不敢让自己太满，或者满，因为哈希表满的话，插入的效率会下降得很快。因为，表快满了，其中的值已经很多了，随便插入几个数就会冲突。冲突就会往后进行遍历，又因为表快满了，遍历的次数就会很多，当表满的时候，相当于全部遍历一遍。找一个 不存在的值不进行特殊判断还会死循环。

     哈希表的扩容问题

     哈希表当中用一个 值来存储 其中元素个数和 开空间个数的关系：

     看这个 α ，就可以知道当前 表当中的有效元素个数和 表的长度的关系。显然，这个 α 越大，产生哈希冲突的概率就越大，但是空间利用率越高，反之。

    这个 载荷因子 是哈希表当中一个非常重要的一个 数，因为这个数的大小会直接影响到整个哈希表的插入效率。

    一般：

     对于开放定址法，应该严格控制载荷因子在 0.7 - 0.8 一下，超过 0.8 ，在查表的时候CPU花村不命中按照指数曲线飞速上升。所以，一些采用开放定址法的hash库，如JAVA的系统库限制了载荷因子0.75，超过0.75 就会 resize 散列表。

     我们本博客实现的哈希表使用上述方法进行扩容。

     重新映射

    而且，不能直接还用 resize（）函数来直接进行扩容：

     如果像上述一样直接库容的话，就会出问题，如下所示：
     

     如果在扩容之后，我们想找到 111 这个元素，那么应该是 111 % 20 找到 初始位置，是 11，那么就会在 11 这个位置去找的，但是我们发现，这个初始位置其实是错误的。

     所以扩容之后就要重新映射。

    此处实现就重新创建一个 vector ，然后把 原 vector 当中的数据都按照新的 hash 函数插入到新的vector 当中。

    当然，要直接创建一个 vector也行，但是我们使用现代写法，让编译器帮我们把原vector 释放掉，如下所示，创建一个 hash对象 - newhash，把 newhash对象当中的 vector 空间开成扩容之后的大小，把 原vector 当中的数据按照新的hash 规则插入到 新的vector 当中之后，直接将两个 hash 当中的两个 vector 进行交换，这样原vector就复制给新的hash 当中去了，这个 newhash 出了 insert（）函数作用域就会自动销毁：
     

    我们发现，哈希表的插入会有不小的消耗，但是扩容不是每一次都发生的，如果把哈希表执行之间化成一个曲线的话，大概是这样的：
     

     他会有一个峰值，这个峰值就是扩容，但是不是扩容的话，哈希表效率是非常高的。而且，哈希表的扩容不频繁。

     insert完整代码：
     

    1. hash()
    2. 		{
    3. 			// 使用 resize 函数可以让 size 和 capacity 保持一致
    4. 			_table.resize(10);
    5. 		}
    6.  
    7. 		bool insert(const pair& kv)
    8. 		{
    9. 			// 扩容
    10. 			// 要考虑一个问题，当 初始的时候 _table当中的没有元素
    11. 			// 可以直接判断_table.size() == 0
    12. 			// 但是有更好的方式，就是写个构造函数，初始就开一点点空间
    13. 			// 至少得强转一个为 double(另一个就会隐式的转)，不然 int类型 7 / 10 = 0
    14. 			if (_n * 10 / _table.size() >= 7)
    15. 			{
    16. 				size_t newsize = _table.size() * 2;
    17. 				hash newhash;
    18. 				newhash._table.resize(newsize);
    19.  
    20. 				for (size_t i = 0; i < _table.size(); i++)
    21. 				{
    22. 					if (_table[i].state == EXITS)
    23. 					{
    24. 						// 不会死循环，以为空间已经开好了，在这次结束之间不会满的
    25. 						newhash.insert(_table[i]._kv);
    26. 					}
    27. 				}
    28.  
    29. 				// 交换
    30. 				_table.swap(newhash._table);
    31. 			}
    32.  
    33. 			size_t hashi = kv.first % _table.size();
    34. 			// 如果遍历的元素不为空就继续遍历
    35.  			while (_table[hashi].state == EXITS)
    36. 			{
    37. 				++hashi;
    38.  
    39. 				// 每一次都按照规则模一下，防止遍历到最后超出这个表
    40. 				hashi %= _table.size();
    41. 			}
    42.  
    43. 			// 此时有两种情况，要么找到了，要么就没找到合适位置，需要扩容
    44. 			_table[hashi]._kv = kv;
    45. 			_table[hashi].state = EXITS;
    46. 			++_n; // 哈希当中的有效个数++
    47.  
    48. 			return true;
    49. 		}
    50. 	private:
    51. 		vector> _table;
    52. 		int _n; // 存储哈希表当中的有效数据个数
    53. 	};

     find（）查找函数

     关于查找规则上述已经说明了，此处是实现和一些细节的说明。

    查找就要遇到空才结束，查找过程和插入过程类型，而且要保证这个结点是存在的，不能是删除的结点。

    1. // 返回值当中的 const 修饰 K 是为了防止 K 被修改		
    2.         hashNode<const K, V>* find(const K& key)
    3. 		{
    4. 			int hashi = key % _table.size();
    5. 			while (_table[hashi]._kv.state != EMPTY)
    6. 			{
    7. 				if (_table[hashi]._kv.state == EXITS
    8. 					&& _table[hashi]._kv.first == key)
    9. 				{
    10. 					return &_table[hashi];
    11. 				}
    12. 				++hashi;
    13. 				hashi &= _table.size();
    14. 			}
    15.  
    16. 			// 没找到
    17. 			return nullptr;
    18. 		}

     上述返回值当中的 const 修饰 K 是为了防止 K 被修改。其实应该用 迭代器去实现是最好的，具体可以参考 其中红黑树的迭代器实现：
    C++ - set 和 map 的实现（下篇）- set 和 map 的迭代器实现_chihiro1122的博客-CSDN博客

    C++ - map 和 set 的模拟实现上篇 - 红黑树当中的仿函数 - 红黑树的迭代器实现-CSDN博客

    erase（）删除函数

     一般数据结构删除结点都比 插入结点要难，但是哈希表是一个例外，哈希表的删除非常的简单。按照上述的对删除的描述，只需要复用 find（）函数找到这个元素，然后把这个元素的 state状态赋值为 DELETE 删除状态就行。

    1.  
    2. 		bool erase(const K& key)
    3. 		{
    4. 			hashNode<const K, V>* hashN = find(key);
    5. 			if (hashN)
    6. 			{
    7. 				hashN->state = DELETE;
    8. 				// 维护 _n
    9. 				--_n;
    10. 				return true;
    11. 			}
    12.  
    13. 			return false;
    14. 		}

    各种类型作为 key 的哈希表实现

     上述实现的 只是 int 类型作为 key 的时候，那么我们直接取模，来计算出初始位置，但是如果是 string 类型的话，显然是不能取模的，此时我们得换一种方式，建立另一种映射关系。

    我们之所以不能用string 直接取模，是因为，取模是类似 int类型才能去取模的，那么就想办法把 string类作为整形去计算取模的值，映射出初始位置就行了。

    相当于是在整形映射存储位置之上，在建立一个映射，把 字符串建立一个映射：

     介绍如何映射之前，我们下来考虑一个问题，在string当中我们找到string当中的某一个字符，最方便的方式是使用 operator[]（）函数来访问其中的元素，如下所示：

     但是，我们不能这样写，因为我们当前写的insert（）函数当中的传入的 key 这个形参，它的类型是一个模板：

     既然是模版，那么传入什么类型的变量都是可能的，那么所有的 内置类型或者 自定义类型都支持 operator[]() 这个函数吗？答案是否定的。

     比如int 类型，直接像上述一样 直接使用 key 就行了，那里用什么 operator[]() 取其中的值。

     更不可能用每个字符串的首元素地址来寻找哈希当中的字符串：

     比如上述两个 string类型，字符串是一模一样的，但是两个字符串的地址是不相同的，我们知道 在string类当中存储字符串也是用一个 字符串数组来存储的，我们肯定不能保证两个字符串的地址相同。

    所以按照上述的描述，我们很难使用一个模版函数就实现所有类型的哈希表的操作。

     所以，我们得写多个函数来实现多种类型的 哈希表，那么如何控制 函数的使用，我们之前也说过，就是使用仿函数来实现。

    仿函数的本质就是，写了一个类，当中写了 operator[]（）这个重载运算符函数，我们可以利用这个特性把传进来的参数，可能是一个变量，可能是一个对象，进行特殊的处理，然后实现：一份代码多处使用的泛型编程。

     那么此处，我们只用 string 类做例子，只实现 string类在哈希表当中的存储，但是其他方法也是使用类似操作，只是在函数实现上不一样而已。

    定义两个仿函数，一个是 哈希表默认的仿函数，也就是我们刚开始实现的 int 类的哈希表；另一个就是 string了：

    哈希默认仿函数实现：

    1. 	template<class K>
    2. 	struct DefaultHashFunc
    3. 	{
    4. 		size_t operator()(const K& key)
    5. 		{
    6. 			// 不管是什么类型的，都转换成 size_t
    7. 			// 不管是 负数还是正数，都转换为 正数
    8. 			return (size_t)key;
    9. 		}
    10. 	};

     在上述实现之后，我们就可以在 insert（），find（）等等函数当中控制 key 的使用了：

    string的仿函数：

    对于 string转为 int 的类型的方式有两种的：
    注意，我们在使用map 和 set 等等容器的时候，发现，并没有仿函数的输入，所以，我们要在此处相比于之前的仿函数使用进行一些处理，应为一些经常要使用的一些类型，我们可以使用特化来直接书写，使用特化来对 string 的 仿函数进行特化；
     

    1. 	// string 的特化
    2. 	template<>
    3. 	struct DefaultHashFunc
    4. 	{
    5. 		size_t operator()(const string& str)
    6. 		{
    7. 			// 字符串转 int 的算法
    8. 			// ·············
    9. 		}
    10. 	};

    如果像上述实现一样实现string的仿函数的话，就可以不用传入模版当中的仿函数参数了：
     

     第一种 string 转 int 的方法：

    首先肯定想到的是，计算 string 每一个字符的 ascll 码值的和，算和大小来排序。但是这样的计算会有问题：

     最后三种情况，计算出来应该是不一样的，但是这三种情况应该是不一样的key值。

    其实，字符串计算成int 值是一个很常见的算法，在下面这个文章当中就记录了很多 的 字符串转 int 的算法：
    各种字符串Hash函数 - clq - 博客园 (cnblogs.com)

     有一种简单算法就是在 每一次加 字符的ascll 码之前就 乘上一个数，然后在加：

    1. 	// string 的特化
    2. 	template<>
    3. 	struct DefaultHashFunc
    4. 	{
    5. 		size_t operator()(const string& str)
    6. 		{
    7. 			// 字符串转 int 的算法
    8. 			int hash = 0;
    9. 			for (auto& ch : str)
    10. 			{
    11. 				hash *= 131;
    12. 				hash += ch;
    13. 			}
    14.  
    15. 			return hash;
    16. 		}
    17. 	};

    我们发现，如果不限制字符串的长度的话，那么字符串的组合就是 无限个，转换成 size_t 类型的大小就是 2 ^ 32 种。那么冲突的几率也不大，总是会输出。

     完整代码

     

    1. #pragma once
    2. #include
    3.  
    4. namespace Myhash
    5. {
    6. 	enum STATE
    7. 	{
    8. 		EXITS,
    9. 		EMPTY,
    10. 		DELETE
    11. 	};
    12.  
    13. 	template<class K, class V>
    14. 	struct hashNode
    15. 	{
    16. 		pair _kv;
    17. 		STATE state = EMPTY;
    18. 	};
    19.  
    20. 	template<class K>
    21. 	struct DefaultHashFunc
    22. 	{
    23. 		size_t operator()(const K& key)
    24. 		{
    25. 			// 不管是什么类型的，都转换成 size_t
    26. 			// 不管是 负数还是正数，都转换为 正数
    27. 			return (size_t)key;
    28. 		}
    29.  	};
    30.  
    31. 	// string 的特化
    32. 	template<>
    33. 	struct DefaultHashFunc
    34. 	{
    35. 		size_t operator()(const string& str)
    36. 		{
    37. 			// 字符串转 int 的算法
    38. 			int hash = 0;
    39. 			for (auto& ch : str)
    40. 			{
    41. 				hash *= 131;
    42. 				hash += ch;
    43. 			}
    44.  
    45. 			return hash;
    46. 		}
    47. 	};
    48.  
    49. 	template<class K, class V, class HashFunc = DefaultHashFunc>
    50. 	class hash
    51. 	{
    52. 	public:
    53. 		hash()
    54. 		{
    55. 			// 使用 resize 函数可以让 size 和 capacity 保持一致
    56. 			_table.resize(10);
    57. 		}
    58.  
    59. 		bool insert(const pair& kv)
    60. 		{
    61. 			// 扩容
    62. 			// 要考虑一个问题，当 初始的时候 _table当中的没有元素
    63. 			// 可以直接判断_table.size() == 0
    64. 			// 但是有更好的方式，就是写个构造函数，初始就开一点点空间
    65. 			// 至少得强转一个为 double(另一个就会隐式的转)，不然 int类型 7 / 10 = 0
    66. 			if (_n * 10 / _table.size() >= 7)
    67. 			{
    68. 				size_t newsize = _table.size() * 2;
    69. 				hash newhash;
    70. 				newhash._table.resize(newsize);
    71.  
    72. 				for (size_t i = 0; i < _table.size(); i++)
    73. 				{
    74. 					if (_table[i].state == EXITS)
    75. 					{
    76. 						// 不会死循环，以为空间已经开好了，在这次结束之间不会满的
    77. 						newhash.insert(_table[i]._kv);
    78. 					}
    79. 				}
    80.  
    81. 				// 交换
    82. 				_table.swap(newhash._table);
    83. 			}
    84.  
    85. 			HashFunc hf;
    86. 			size_t hashi = hf(kv.first) % _table.size();
    87. 			// 如果遍历的元素不为空就继续遍历
    88.  			while (_table[hashi].state == EXITS)
    89. 			{
    90. 				++hashi;
    91.  
    92. 				// 每一次都按照规则模一下，防止遍历到最后超出这个表
    93. 				hashi %= _table.size();
    94. 			}
    95.  
    96. 			// 此时有两种情况，要么找到了，要么就没找到合适位置，需要扩容
    97. 			_table[hashi]._kv = kv; 
    98. 			_table[hashi].state = EXITS;
    99. 			++_n; // 哈希当中的有效个数++
    100.  
    101. 			return true;
    102. 		}
    103.  
    104. 		// 返回值当中的 const 修饰 K 是为了防止 K 被修改
    105. 		hashNode<const K, V>* find(const K& key)
    106. 		{
    107. 			HashFunc hf;
    108. 			int hashi = hf(key) % _table.size();
    109. 			while (_table[hashi]._kv.state != EMPTY)
    110. 			{
    111. 				if (_table[hashi]._kv.state == EXITS
    112. 					&& _table[hashi]._kv.first == key)
    113. 				{
    114. 					// 此时的_table[hashi] 的类型是一个 hashNode，那么返回就是一个 隐式类型转换
    115. 					// 不是所以的编译器都支持 隐式类型转换，所以我们在这里强转一下
    116. 					return (hashNode<const K, V>*) & _table[hashi];
    117. 				}
    118. 				++hashi;
    119. 				hashi &= _table.size();
    120. 			}
    121.  
    122. 			// 没找到
    123. 			return nullptr;
    124. 		}
    125.  
    126. 		bool erase(const K& key)
    127. 		{
    128. 			hashNode<const K, V>* hashN = find(key);
    129. 			if (hashN)
    130. 			{
    131. 				hashN->state = DELETE;
    132. 				// 维护 _n
    133. 				--_n;
    134. 				return true;
    135. 			}
    136.  
    137. 			return false;
    138. 		}
    139.  
    140. 	private:
    141. 		vector> _table;
    142. 		int _n; // 存储哈希表当中的有效数据个数
    143. 	};
    144. }

  • 相关阅读:
    PIE-Engine 教程:水稻面积提取2—监督分类(宿迁市)
    【PTHREAD】线程状态
    【LeetCode】7. 整数反转
    Q格式的数据
    微服务注册中心：Eureka详解
    1.每天进步一点点------爬虫应用场景
    React--路由详解
    升级你的提问技巧：ChatGPT-4o时代，如何让对话更智能？
    Linux创建逻辑卷并扩容（超详细）
    python-kafka客户端封装
  • 原文地址：https://blog.csdn.net/chihiro1122/article/details/133364456