哈希表通过键值映射实现高效查找。本文讲解哈希函数性质（确定性、有限性、均匀性）、冲突解决策略（开放定址法、哈希桶）。重点阐述 STL 中 unordered_set 和 unordered_map 底层基于哈希桶的实现细节，包括节点定义、负载因子计算、扩容机制、迭代器封装及内存管理。提供完整的 C++ 模拟实现源码，涵盖构造函数、插入、查找、删除、析构等核心功能，帮助深入理解无序关联容器原理。
在正式讲解 STL 的 unordered_map 以及 unordered_set 这两个容器之前，我们先回顾一下目前接触到的能够高效查找数据的数据结构。首先想到的是数组，但这里的数组不是简单的将元素直接存放到任意位置，而是先将存储在数组中的元素排序，然后借助二分算法进行查找。由于排序只需一次，代价可均摊到每次查找中，所以排序代价可忽略不计，而二分查找的时间复杂度则是 logN。这种方式能实现高效的数据查找，但如果涉及插入及删除操作，若不在数组末尾，必然要移动大量元素，意味着插入和删除的时间复杂度最坏情况下会达到 O(N)，效率不如查找。
接着是在二叉搜索树基础上优化、压缩其高度的 AVL 树和红黑树。这两种数据结构会将整个二叉搜索树的高度压缩到 logN，所以对于 AVL 树以及红黑树来说，其查找和插入都是在 logN 这个量级。相比于刚才所说的排序 + 二分的数组，其综合效率上又更进一步。
而目前接触到的数据结构中，综合效率最为高效的是 AVL 树以及红黑树。本文要登场的数据结构：哈希表，该数据结构核心功能也是高效查找数据，更关键的是，哈希表的综合效率还能够在 AVL 树以及红黑树的基础上更进一步。本文着要讲的 STL 的两个容器：unordered_map 和 unordered_set，其底层采取的数据结构便是哈希表。所以要掌握 unordered_map 以及 unordered_set，首先就得先掌握哈希表。后文内容将首先讲解哈希表的原理，理解了哈希表之后，便可以用代码模拟实现 STL 中的 unordered_set 和 unordered_map 这两个容器。
由上文可知，哈希表也是高效查找数据的数据结构。AVL 以及红黑树之所以能够高效查找数据，核心就是借助二叉搜索树的左小右大的性质，也就是左子树中的所有节点小于根节点，右子树中的所有节点大于根节点，来实现数据的查找。而这里的哈希表是如何来实现数据的查找呢？
哈希表实现数据的查找则是通过建立键与存储位置的映射来实现数据的查找，而哈希表本质上就是一个动态数组，所以这里的存储位置其实就是数组的索引，哈希表就是建立键与数组索引的一个映射。
而这里所谓的映射，有一个专业术语来称呼，便是哈希函数。
所谓的哈希函数可能仅仅就是一个简单的算术表达式，比如 Ax-C，也许可能对应的是一个有很多步骤的复杂算法。总之，我们可以用一个函数来代表这里的哈希函数：
y = hash(x)
那么在认识以及了解哈希函数具备哪些性质之前，可以先来看一下哈希函数长什么样：
// 乘法哈希
uint32_t knuth_hash(uint32_t key) {
return key * 2654435761;
}
// 字符串哈希
uint32_t djb2_hash(const char* str) {
uint32_t hash = 5381; // 魔术种子（Magic Number）
int c;
while ((c = *str++)) {
// hash * 33 + c
hash = ((hash << 5) + hash) + c;
}
return hash;
}
可以向哈希函数中给一个范围很大的输入，这个范围可以是无穷大，但是无论你给哈希函数的输入范围有多大，这些输入一旦经过哈希函数的运算得到的所有输出，通常都是在一个固定且有限的范围。
假设输入是一个整数类型，那么输入的范围或者说定义域是在 [0, 1000000000]，尝试给一个哈希函数输入 [0, 1000000000] 范围中的所有数字，但是经过哈希函数计算后的输出的结果的范围可能就是只位于 [0, 100] 或者 [0, 10000] 之间，意味着输入的样本量可以是 1000000000 个，但是经过哈希函数输出后的样本量却只有 100 个或者 10000 个。
上面说的内容，正是哈希函数的第一个性质，那就是输入的样本量可以是无限的，但是经过哈希函数计算后的输出结果一定是有限个的。
既然知道了这个性质，还是以上文的例子，假设哈希函数的输入的范围是在 [0, 1000000000]，意味着输入可以是 0 也可以 10 或者 100 或者 10000 等等，但是哈希函数的输出的范围假设为 [0, 100]，所以哈希函数得到的每一个输出，其一定是 [0, 100] 范围中的某个数。
这么大的样本量，得到却是在这么小的范围上的输出，那么就一定会面临一个问题：肯定会有很多不同的输入对应相同的输出，意味着这里输入与输出的关系是多对一的。因为这里输入的样本量远大于输出的样本量，就会导致多个样本经过哈希函数的计算之后，可能会得到的是同一个输出。比如 0 经过哈希函数的计算得到的输出是 20，然后 1000 得到哈希函数的计算的结果也是 20。而不同输入对应相同的输出，这里也有一个专业的术语，便是哈希碰撞。
但是这里如果可以让哈希函数的输出范围也能够达到 [0, 1000000000] 的话，那么哈希函数就可以做到一对一，也就是每一个输入对应唯一的一个输出，所以哈希函发生哈希碰撞并不是绝对的。
其次要注意的一点的就是，哈希函数还要满足确定性，也就是在当前时刻下某一个输入经过哈希函数计算的值是 a，之后的某个时刻再一次经过哈希函数计算的值却变成了 b，如果出现了这种情况，那么该函数就不是一个哈希函数，因为哈希函数具备的性质就是确定性，也就是一个输入每时每刻对应着一个唯一且确定的输入，不具备随机性。
最后就是哈希函数还满足均匀性，可以将哈希函数的输出也就是值域，如果用数轴来表示的话，那么这里哈希函数计算得到的每一个输出会均匀的落在数轴上的每一个点。以刚才的例子为例，哈希函数的输出的范围假设为 [0, 100]，输入的范围为 [0, 1000000000]，那么这里计算出的每一个输出都会均匀的落在 [0, 100] 的每一个位置上，不会出现所谓的聚群现象：也就是得到的所有输出会集中在 [0, 20] 或者其他某个区间上，意味着每一个输出落在数轴上的每一个点的概率是相等的。
假设这里计算出的哈希函数的输出有 100 个，那么按照哈希函数的均匀性，如果将这个数轴划分成 10 等分，分别为 [0, 9], [10, 29]…等等，然后接着统计分布在每一个区间中的输出有多少个，根据均匀性，这里统计出来的结果，也就是分布在每一个区间的输出的个数一定是在 10 左右，而不可能有一个区间的输出有 20 个或者 40 个，这是不满足均匀性。
最后就来总结一下哈希函数具备的这性质：
性质一：
确定性：相同输入必定产生相同输出性质二：
有限性：输出值的范围是固定且有限的性质三：
哈希函数可能会发生哈希碰撞：不同的输入可能产生相同的输出性质四：
哈希函数具备均匀性性质五：
高效性：哈希函数的计算一定得快，得接近 o(1) 常数级别的复杂度
讲解了哈希函数的原理，有的读者可能会好奇，为什么这里讲解全部都是围绕原理是什么，而没有涉及到为什么的内容，也就是证明哈希函数为什么满足这些性质比如均匀性，以及如何设计一个满足这些性质的哈希函数。
这里想说的是，某一个哈希函数的设计者或者发明者，这些发明者一般是数学家或者计算机科学家或者密码学家，那么一个哈希函数的设计是要涉及到数学以及概率论以及计算机中的位运算等等知识，背后要涉及大量的理论基础。其次就是设计完了哈希函数，除了理论证明还不够，还需要大量的测试去验证其正确性，所以要证明一个哈希函数的正确性以及设计一个哈希函数的成本其实很大的。
而我们不需要造轮子，只需要记住以及理解哈希函数的性质以及运用前人设计好的哈希函数即可，就好比你要学会驾驶汽车，你可以学习汽车的每一个部件比如发动机是怎么工作的，以及背后涉及到的化学知识，但是掌握这些对你实质性的帮助其实并不是很大，所以这里就只需要知道哈希函数具有哪些性质，以及有哪些哈希函数，至于证明，读者感兴趣下来可以自己了解。
最后再来说一下哈希函数的一个应用，假设要编写一个程序，该程序要接收 100 个亿的字符串，每一个字符串长 100 个字节，该程序要统计哪个一个字符串出现的次数最多。
解决这个问题，有的读者会立马想到用 map 这个容器，将 map 中的键设置为 string，然后将这 100 个亿的字符串分别插入到 map 当中去，然后来遍历一遍 map 来得到出现次数最多的字符串。这里知道 map 底层实现是采取的红黑树，而每一个字符串是 100 个字节，那么 100 个亿个字符串，就总共会消耗约为 931 个 G，而内存总共才 4G 或者 8G，并且红黑树除了存储 100 个字节的数据域，还会有指针域的额外的内存开销，所以这种方式肯定是不可取的。
这里就可以采取哈希函数，可以建立一个字符串到文件号的一个映射的哈希函数，所以可以创建 1000 个文件，哈希函数的输出就是某个特定文件号，根据哈希函数的性质，其具有均匀性，意味着这 100 亿个字符串会均匀的分布在这 1000 个文件中，每一个文件会分配大约 100 万个字符串，会占据 1GB 的大小的空间，所以这里就可以实现分流。
H(string) -> int
如果当前字符串映射到文件号为 2 的文件，那么这里就只需要将文件号为 2 的文件从磁盘加载到内存，那么每一个文件可以维护了一个 map 容器，来统计该文件中出现次数最多的字符串，而每一个文件都各自有一个出现次数最多的字符串，然后在获取这 1000 个文件中出现最多的字符串，在综合统计，就能得到这 100 个亿字符串中出现最多的字符串。
直接定址法对应的哈希函数非常简单，其就是一个简单的算术表达式。由于这里的哈希函数是键和数组索引的一个映射，所以直接定址法的哈希函数就是键的最大值减去最小值，那么得到的结果就是数组的索引：
Hash(Key) = Key - Keymin
按照这个哈希函数，如果当前的键就是整个输入范围中的最小的键，也就是 Keymin，那么经过哈希函数的映射之后，那么得到的值就是 0，对应的就是数组的起始位置。假设这里键的范围是 [keymin, keymax]，那么在经过哈希函数的映射之前，还得预先开辟一个长度为 Keymax-Keymin+1 长度的数组。
开辟好数组之后，那么位于这个范围上的所有的键经过哈希函数的映射之后，那么都会落在这个数组的某一个特定位置上。假设现在插入的键的范围是 [0, 99]，那么这里先开辟长度为 100 的数组，如果现在要插入的键值是 88，那么根据哈希函数，就可以计算出结果，确定其在数组下标 88 的位置上存储该键对应的数据，如果插入的建是 0，那么根据哈希函数就能计算出其在数组下标为 0 的位置上存储该键对应的数据。
知道了插入的原理，再来说一下查找。那么这里查找某一个键是否存储在这个哈希表当中，还是以上文的例子为例，那么知道该哈希表存储的键的范围是 [0, 99]，那么意味着这里开辟了 100 个长度的数组，而如果我们要查询的建是 101 或者 220，那么这些键不在有效范围内，那么经过哈希函数的映射，之后的访问就会出现越界访问。
所以采取这种方式，必然还得额外维护一个变量来记录当前数组的长度，然后判断该键经过映射后的数组索引是否合法，如果合法的话，那么就直接利用数组的随机访问特性，直接访问对应的数组下标的内容即可，所以这里的查找就只需要经过哈希函数的计算，然后判断合法性，最后直接访问即可。
知道了上文所讲述的直接定址法的原理，那么可以评价一下这种方式的效率。要插入 [Keymin, Keymax] 范围上的键，只需要开辟完数组之后，经过一个哈希函数的计算得到数组索引，就能够直接存储。由于哈希函数的计算以及用下标访问数组都是常数级别的时间复杂度，意味着这里的插入的时间复杂度是 O(1)，已经是最完美的了。
而对于查找以及删除来说，其也是只需要经过常数级别的哈希函数的计算，得到数组索引，然后访问对应数组下标的内容即可。
其次注意的是，这个哈希函数是不会发生哈希碰撞，也就是不同的键对应同一个数组索引，因为这里根据哈希函数的形式：Key-Keymin，其是以键为变量的一次函数，那么根据一次函数的性质或者图像，每一个自变量只能对应唯一的因变量，这里的自变量就是键，因变量就是数组索引。
这里可以将哈希表，也就是动态数组中的每一个元素设置为一个结构体，其中封装一个数据域以及一个状态标记，其中状态标记是一个枚举变量，其中定义了两个枚举常量 EMPTY 和 OCCUPY，其中 EMPTY 代表当前数组下标没有存储有效数据，而 OCCUPY 代表当前数组下标存储了有效数据，其节点中数据域的内容就有意义。
enum state { EMPTY, OCCUPY };
template<typename T>
struct HashNode {
T data;
state _state;
};
意味着如果要删除哈希表中键值为 key1 的元素，那么首先将 key1 代入哈希函数计算出索引 i1，由于这里数组中每一个元素是一个结构体，就可以访问下标为 i1 的结构体的状态标记，如果其为 EMPTY，说明此时哈希表中没有没有存储键为 key1 的数据，如果当前状态标记为 OCCUPY，说明当前数组下标存储了键为 key1 的元素，然后将状态标记设置为 EMPTY 即可，就逻辑上删除了该节点。
所以直接定址法的插入和查找以及删除的时间复杂度都是严格意义上的 O(1) 级别，各方面已经达到了完美。如果事实真是这样，那么毫无疑问，采取直接定址法的哈希表就是世界上最优秀的事实结构，当然现实肯定并非如此，要达到这种所谓的完美其实是有前提的，也就是这里存储的键的范围必须连续的。
上文说的场景其实都是非常理想化的场景，就好比你假设地面没有摩擦，那么物体要么会静止或者匀速直线运动一样，而真实的场景是，往哈希表中插入数据的时候，并不知道用户要插入的键的范围，而根据上文，首先就得开辟一定长度的数组，那么意味着这里得维护一个两个变量，来分别记录当前插入的键的最小值和最大值，因为数组的长度 L=Keymax-Keymin+1，那么这里维护这两个变量就需要额外的时间开销，并且这里的数组还极有可能频繁的扩容，但这都还不是最恼火的问题。
最恼火的问题是，假设插入的键的范围是 [Keymin, Keymax]，然后开辟了一个长度为 Keymax-Keymin+1 的数组，但是只往里面插入两个键，假设为 Keymin 和 Keymax，如果这里的 keymin 为 0，Keymax 为 100000，这里就会导致数组的大量空间会被浪费。
所以直接定址法的应用太狭窄了，是不会被采纳，而这里选择讲解是有便于理解之后的哈希函数，因为其是在此直接寻址法的基础上做了优化。
由于直接定址法对于空间的浪费很严重，所以这里开放定址法的哈希函数则是采取的是除留余数法：
Hash(Key)=key%N
除留余数法的好处则是：根本不用关心键的范围，因为无论键值有多大，那么经过除留余数法后，其输出结果一定是 [0, N-1]，而这里的 N 对应的就是数组存储有效数据的长度，得到的余数就是数组的索引，但是这里的哈希函数会发生一个问题：
假设这里插入两个键，键值分别为 key1=KN+2 和 key2=K(N+1)+2，这里 key1 和 key2 虽然键值不同，但是经过哈希函数的映射之后，其都会得到同一个余数 2，而数组中的位置只能存储一个有效的键值对，所以这里必然会导致哈希冲突。
既然冲突无法避免，那么就得解决冲突，那么解决冲突的方法就是线性探测。假设经过哈希函数计算出的数组索引为 i，如果当前为 i 的位置被占用，也就是已经存储了一个键值对了，那么就从下标 i 位置，往后查看 i+1，i+2… 之后的位置是否被占用，如果没被占用，就在当前的空闲位置存储键值对。
要注意这里线性探测的整个过程，要不断从当前位置往后遍历，那么可能会一直遍历到数组末尾甚至越界，所以每次往后遍历的时候，也就是 i 不断自增，每次自增玩，都要模数组的有效长度，这样一旦到达数组末尾，经过一次模运算，就会移到数组开头，然后继续往后遍历。
所以按照这种开放定址法 + 线性探测的玩法，会发现数组索引和键之间没有直接的映射关系，因为映射完得到的一个初始值，其并不一定会采纳。
而对于删除操作来说，其过程和插入类似，首先还是会经过哈希函数计算出一个初始值，但是这个计算出的初始值不一定就是该键对应的数据，所以还需要往后遍历之后的探测序列，如果遍历到未被占用的位置，说明此时哈希表没有存储当前键对应的数据，因为根据上文插入的原理，如果有该键值的数据，如果其计算得到的初始位置没发生冲入，那么直接在初始位置就存储该键对应的数据，而发生了冲突，那么一定会往后遍历探测序列，找到一个未被占用的位置插入。
所以一旦遍历到了未被占用的位置，就说明当前哈希表中没有存储该键对应的数据，而如果找到匹配的键值对之后，那么就可以删除。
而这里的数组的每一个节点可以同样设置为一个结构体或者自定义类型。
其中有数据域和状态标记，这里的状态标记是枚举变量，其中定义了三个状态的枚举常量，分别是 EMPTY 和 DELETE 以及 OCCUPY，分别代表未被占用以及删除和被占用。
enum state { EMPTY, DELETE, OCCUPY };
template<typename T>
struct HashNode {
T data;
state _state;
};
所以一旦找到了删除的位置后，那么就访问其状态标记，将其设置为 DELETE，就完成了删除。
而对于插入，其原理也是类似，先是将插入的数据的键代入哈希函数计算出初始位置，如果初始位置发生冲突，就遍历探测序列，依次访问数组中各个节点的状态标记，那么如果状态标记为 EMPTY 或者 DELETE，就在当前位置插入，而如果是 OCCUPY，就继续往后遍历，直到找到状态标记为 EMPTY 或者 DELETE 的位置。
对于查找来说，那么过程也是一样，经过哈希函数计算出初始位置，然后访问其数据域，如果不匹配，就依次遍历之后的探测序列，先访问状态标记，如果为 OCCUPY，就访问数据域，如果为 DELETE 或者 EMPTY，遍历就直接结束。
知道了插入以及删除和查找的原理之后，再来分析一下采取开放定址法 + 线性探测的哈希表的一个效率。其实可以发现这里的效率其实取决于在数组中存储的元素的个数，如果数组中存储的元素占比越大，那么意味着冲突的概率也就越大，因为数组中剩余的未被占用的位置已经很少了，并且如果某个位置发生了冲突，那么遍历的探测序列也就会越长。
而如果此时数组中存储的有效数据较小，那么此时空闲的位置偏多，意味着冲突的概率就越小，那么此时插入一个元素，经过哈希函数计算出的初始位置，极有可能就是最终的插入位置，即使发生了冲突，由于有效数据较少，探测序列较短，也可以极小的代价，也就只需遍历几个节点，就能确定插入的位置。
而如果存储的数据过少，虽然此时性能是最优秀的时候，其插入以及删除的复杂度接近 O(1)，但是空间利用率低，而如果存储的有效数据越多，反而性能会下降，因为冲突的概率增大以及遍历的探测序列会很长。
所以一旦数据量变大，那么就需要我们扩容，那么扩容会让数组的长度变大，由长度 N 变成 M，那么此时就需要将原本的元素重新拷贝到扩容后的数组，此时由于数组长度变大，那么哈希函数也会改变，意味着键对应数组索引的映射会发生改变，那么这里就需要重新映射。
这些元素重新映射到新的数组当中去，由于数组长度增加再加上重新映射的缘故，会使得扩容后有效数据在新数组的位置变得分散起来，那么插入和查找以及删除的效率就会提升。
但是扩容得是有时机的，如果此时数组中存储的有效数据的个数很少的情况下，选择扩容，那么反而更会让空间利用率降低，而如果扩容的时机太晚，也就是数组中的有效数据快填满整个数组时候，才选择扩容，那么知道数组在达到这个状态，必然经历了一系列的插入以及查找和删除操作，意味着这些动作会在哈希表的性能低效的状态下完成，但我们期望这些动作能够在哈希表性能良好的状态下完成，所以扩容太晚也不行。
所以这里就得引入一个负载因子，来帮助判断目前哈希表的状态。
所谓的负载因子，其计算过程很简单，就是通过当前数组中存储的有效元素的数据个数除以数组的有效长度，计算出的结果就是负载因子，那么负载因子就可以作为一个指标，用来反应当前哈希表的状态，如果负载因子过大，比如 0.7 或者 0.8 甚至接近于 1，那么说明此时数组中的剩余的空闲位置已经极少，冲突概率高，而如果负载因子过小，那么结果就相反，说明此时数组中的空闲位置很多，那么冲突概率低。
而至于扩容的时机，那么这个时机一般就是在负载因子达到 0.7 或者 0.75 的时候，选择扩容，那么不同的平台下，选择扩容的方式会有不同，一般都是 2 倍扩容，至于为什么是负载因子为 0.7 或者 0.75 的时候选择扩容，而不是 0.9 或者 0.6 选择扩容。
这个数字的得到肯定是经过大量的实验以及结合了数学理论支撑才得到，那么知道的是如果负载因子超过了 0.7 或者 0.75，此时哈希表的性能会大幅下降，而至于为什么负载因子是 0.7 或者 0.75 的证明感兴趣的读者，可以自己下来了解，本文不再对此做过多的赘述。
由上文可知，造成线性探测的性能下降的原因，就和数组中存储的有效数据的占比以及分别有关，其实不难发现，线性探测得到的探测序列，其是线性且连续的，并且随着数据的占比的增大，这个探测序列会越来越聚集，就会造成一个集群的现象发生，因为每一次在 i 位置发生冲突，需要遍历的探测序列是 i，i+1，i+2 …
这种方式就会导致有效数据的分布较为集中，而不是分散的分布，那么较为集中的分布影响的就是发生冲突之后，要涉及到遍历较长的探测序列。
所以二次探测的方式则是，如果当前 i 位置处发生了冲突，那么这里遍历的探测序列就是 i+0^2 ,i+1^2, i+2^2， …
根据这里的二次探测的方式，可以发现，每一个产生冲突的位置 i，其对应的探测序列是不同的，并且这里的探测序列不是连续而是离散的分布，也减少了之后继续发生冲突的概率。
按照二次探测的这种方式，可以减少有效数据分布的集中性，让有效数据分布的较为离散，从而减少了首次发生冲突的概率以及后续遍历探测序列发生的冲突的概率，所以这里开放定址法 + 二次探测的方式要比线性探测较为优秀。
根据上文介绍的开放定址法，我们知道开放定址法的缺陷就在于遍历较长的探测序列，而接下来的哈希桶，则是在直接定址以及开放都定址的基础上，又做出了进一步的改进。
那么这里所谓的哈希桶本质上还是一个动态数组，只不过这里的数组是一个指针数组，数组中的每一个位置则是指向一个链表。
而哈希桶的哈希函数则还是采取的除留余数法，也就是：
Hash(Key)=Key% N
而这里与开放定址放不同的是，这里将键值经过哈希函数的计算，得到一个初始位置，这个初始位置就是数组的下标，那么根据上文所讲的原理，知道这里的哈希函数会存在哈希碰撞，也就是不同的键值可能对应这同一个数组下标，但是这里哈希桶则是不处理冲突，所谓的不处理冲突，也就是是哈希桶允许多个键值对应同一个数组下标，那么这一点会在后文继续补充解释。
那么哈希桶定义了一个节点，这个节点可以是结构体也可以是自定义类型，那么其中包含数据域和以及指向后继节点的指针域。
所以一旦计算出该键对应的数组下标之后，那么直接采取头插，因为指针数组中的每一个元素都是指向对应的链表的头节点，那么再开辟一个新的节点，将键值对拷贝到该节点中，然后将该节点的指针域指向其链表的头节点，接着让该数组下标的指针指向新开辟的节点，从而就完成了链表的头插。
这种方式的优点，一下就可看出来，那么这里的插入操作，就只需要经过一次哈希函数的计算，得到数组下标，然后直接头插即可，那么哈希函数的计算以及头插的时间复杂度都是常数级别，意味着这里的插入的整体时间复杂度是严格意义上的 O(1)，已经是最优秀的了。
那么对于哈希桶的查找来说，其时间复杂度取决于整个桶数组中，链表最长的桶，有的读者会认为，那么如果插入的所有的键，其经过哈希函数都映射到同一个数组索引，也就是所有插入的键值对都位于同一个链表或者集中分布于某几个桶中，那么此时哈希桶的查找的时间复杂度岂不是会退化到 O(N) 量级。
对于这种情况，首先想说，这种情况确实存在，但是，其发生或者说出现的概率是极低的，而刚才说的极端情况，也就是插入的键都位与同一个桶中，那么可以计算这个情况发生的概率：
假设有 m 个桶，要插入 N 个键，那么每一个键映射出的结果有 m 种可能性，那么要让插入的每一个键都位于同一个桶中，其概率为 (1/m)^N，并且这里所有插入的数据可能都位于第一个桶，也可能位于第二个桶，所以这里的还得乘以一个 m，最终计算得到插入的 N 个键位于同一个桶的概率为：m * (1/m) ^N=(1/m) ^ (N-1)
那么这里的 N 如果是 100000 的话，那么这个概率已经非常低了，况且这是哈希函数，其一定是满足均匀性，所以这里如果插入 N 个键，那么每一个桶中包含的有效节点个数应该是在 N/m 左右。
这意味着这里每一个桶的链表长度应该都维持在 N/m 左右，所以知道一旦插入的数据过多，比如这里的 N 远大于 m，那么意味着此时每一个桶的链表长度都会很长，那么此时哈希桶会退化到 O(N) 这个量级，但是如果插入的数据个数 N 和 m 是刚好相等，那么此时每个桶的平均长度为 1，那么意味着此时查找的时间复杂度会达到常数级别 O(1)。
所以这里哈希表就得同样需要维护一个指标，也就是负载因子，而哈希桶的负载因子的计算和上文是一样的计算方式，就是整个哈希桶数组中所有节点的个数除以桶的个数，计算出来的结果就是负载因子。
可以通过负载因子来反映当前哈希桶的一个状态，如果负载因子到达 1，说明此时哈希桶此时每一个桶的平均长度为 1，那么此时就需要扩容。
扩容之后，同样需要在旧数组保存的数据重新映射到扩容后的新数组，由于此时桶的数量增加了，并且扩容之后，会让整个哈希桶数组的元素分布更加的分散，这样就能够降低每一个桶的链表长度，从而优化了哈希桶的性能。
所以理论上，如果哈希桶的插入和删除以及查找，都能够到达 o(1) 级别的时间复杂度，所以这里 STL 的 unordered_set 和 unordered_map 这两个容器都是选择哈希桶作为其底层结构来实现。
而对于 Java 来说，其有一个 Hashmap 的容器，其底层采取的也是是哈希桶，但是其做了优化，也就是每一个桶对应的不应是一个链表，而可能是一个红黑树，那么一旦链表的长度大于某一个阈值，比如 8，那么其会链表转化为红黑树来存储。
上文介绍了哈希表的原理之后，接下来就要模拟实现 unordered_set 以及 unordered_map，那么 unordered_set 以及 unordered_map 底层都是封装了哈希表，而如果有 map 和 set 模拟实现经验的读者，那么知道 map 和 set 底层封装的都是红黑树，并且都复用的是同一个红黑树的模板类。
同理这里 unordered_set 和 unordered_map，其也应该都是复用的是同一个哈希表的模板类，而如果 unordered_map 和 unordered_set 都各自编写对应的一份支持自身特性的哈希表代码，一旦哈希表的某个部分的代码逻辑出错，那么需要修改 unordered_set 以及 unordered_map 对应的两处代码，而复用同一个哈希表的模板类，那么就减少了代码的维护成本以及代码冗余。
而 unordered_set 是 key 模型，其只用存储一个键值即可，而 unordered_map 则是一个 key_value 模型，其则是存储一个键值对，而这里采取的方式和 map 和 set 的做法是一样的，也就是 unordered_set 和 unordered_map 则是都复用 key-value 模型或者更准确的说是 key-T 模型的哈希表。
对于 unordere_set 来说，那么哈希表的两个模版参数 key 和 T，到时候都会被实例化为键值 key，而对于 unordered_map 来说，这两个模版参数则会分别实例化为键值 key 和键值对 pair。
而这里首先就得先实现底层封装的哈希桶，那么在实现哈希桶之前，得先实现每一个桶对应的链表的节点的定义，那么这里每一个链表的节点，包含数据域以及指向后继节点的指针域：
template<typename T>
class HashNode {
public:
T data;
HashNode<T>* next;
HashNode(const T& val):data(val),next(nullptr){}
};
要注意的就是这里的链表是单链表，而不是双链表，因为没必要维护一个指向前驱节点的指针，查找该链表中是否存在对应键的节点，就是直接往后遍历该数组下标对应的链表的一个一个节点即可，其次就是这里的成员变量都应该被 public 修饰，便于后续在哈希桶类的成员函数中直接访问或者修改节点的指针。
节点定义完之后，那么接下来就是完善哈希桶的模板类了，那么知道哈希桶的本质就是一个动态数组，准确来说是动态指针数组，那么数组的每一个元素指向其对应的链表的头结点，所以这里实现哈希桶可以封装一个 vector 对象，因为 vector 对象底层维护的就是一个动态数组，其次由于后续要插入函数需要计算负载因子，那么这里还得额外维护一个变量，来记录当前哈希桶中节点的总个数。
template<typename key, typename T, typename keyofT, typename HashFuc>
class HashTable {
private:
typedef HashNode<T> Node;
std::vector<Node*> HT;
size_t _n;
};
而这里 HashTable 的第三个模版参数 keyofT 以及第四个模版参数 HashFuc 则会在后文进行补充以及讲解。
这里哈希桶的构造函数只有一个无参的构造函数，因为上层在封装哈希桶的时候，不会传递任何参数给哈希桶，所以这里哈希桶不用编写带参的构造函数，那么这里的构造函数，有两个版本，那么第一个版本就是直接构造一个空的哈希桶，所谓的空的哈希桶，意味此时是一个空的指针数组，如果采取这种方式实现构造函数，那么就一定要注意在之后的 insert 插入函数中，添加一个额外的条件判断，如果当前哈希桶的指针数组为空，就需要先分配一个初始长度的空间然后再进行之后的插入操作。
第二个版本就是这里就直接干脆给哈希桶数组开辟一个初始长度的指针数组，而这里采取的是第二个版本的构造函数，那么预先开辟一个有效长度为 10 的动态指针数组，然后将节点数初始化为 0。
HashTable():_n(0){ HT.resize(10,nullptr);}
这里要注意的就是，开辟一定长度的指针数组，一定得用 resize 而不是 reserve，resize 和 reserve 的区别就在于，reserve 虽然也开辟了一定长度的动态数组，但是有效长度却是 0，而数组存储有效数据的区间是 [0,size-1]，而后续计算平衡因子也需要用到是数组存储数据的有效长度而不是总长度，所以这里一定要注意。
insert 函数则是接收要插入的数据，其实现原理也很简单，那么就是获取数据的键，然后再经过哈希函数计算，得到数组下标，然后再直接头插到该数组下标对应的链表中即可，虽然 insert 函数原理简单，但是其要注意很多的细节。
首先就是 insert 函数接收到的参数是一个 T 类型的参数，这个 T 就是 HashTable 的第二个模版参数，那么它会被实例化为键或者键值对，如果实例化为键，那么可以直接带入哈希函数中，直接进行模运算得到结果，但如果是键值对，也就是 pair，那么是无法直接进行模运算。
所以这里要注意的第一个点，就是的获取插入的数据的键，那么这里底层的 insert 函数是不知道接收到的参数的数据类型是什么，所以这里就得借助仿函数，那么仿函数就是一个类，类中定义了 () 运算符重载函数，那么这里可以通过定义一个仿函数对象，然后调用其 () 运算符重载函数，来为 insert 函数提供获取该数据类型的键值的方法，那么由于这里 insert 函数中没有编写处理特定数据类型的代码逻辑，保证了泛型，并且还很好的实现了解耦，通过这个仿函数对象，能够实现获取不同数据类型的键值的逻辑。
所以这就要在上层，也就是封装哈希表的 unordered_set 以及 unordered_map 类，定义一个内部类，那么这个内部类中就要定义 () 运算符重载函数，而这里 HashTable 模版类的第三个模版参数的作用，就是会被实例化为 unordered_map 或者 unordered_set 中的带有 () 运算符重载函数的内部类类型。
template<typename key>
class unordered_set {
private:
class keyofSetT {
public:
const key& operator()(const key& k) { return k; }
};
HashTable<key, key, keyofSetT> _HT;
public:
// ...
};
template<typename key, typename val>
class unordered_map {
private:
class keyofMapT {
public:
const key& operator()(const std::pair<key, val> _kv) { return _kv.first; }
};
HashTable<const key, std::pair<key, val>, keyofMapT> _HT;
public:
// ...
};
但是这里解决了如何获取键值之后，还没有结束，这里的键的数据类型可以是浮点型也可以是自定义类型比如 string，那么浮点型以及自定义类型，是无法直接进行模运算的，所以这里还得通过二次映射，也就是将浮点型或者自定义类型的键，先经过一次映射，目的是得到该键对应的整形，然后再通过这个整形，经过哈希函数的计算，最终得到数组索引。
那么对于浮点型来说，那么知道浮点型底层本质上也是一个长度为 32 或者 64 位的二进制序列，只不过解释这个序列的方式和整形不一样，所以这里就可以直接强制类型转换成 size_t，将浮点类型转换成整形，那么每一个浮点类型的二进制序列不一样，意味着强转成整形后的值也是不一样的，那么强转后的整形，就能代入哈希函数运算，得到对应的数组索引。
而对于 string 类型的键，那么要得到其对应的整形，那么可以获取 string 类型中的字符串中的第一个字符的阿斯克码来作为其对应的整形，然后再代入哈希函数运算，但是这种映射方法有一个明显的缺陷，那么由于字母只有 26 个，而字符串的种类则是有无限个，那么采取这种映射方法，意味着有很多不同种类的字符串，比如首字符以'a'开头的，那么他们都会映射为同一个整形值 97，那么这样最终经过哈希函数，得到的数组索引就是相同的，那么这样极大的增加了哈希碰撞。
有的读者采取的另外一种方式，就是将字符串中的每一个字符的阿斯克码加起来，来作为映射的整形值，再带入哈希函数计算，那么这种方式相比于第一种方式确实减少了哈希碰撞，但是如果遇到这种情况，也就是字符相同但是顺序不同：
"abcd"
"dbca"
"acdb"
那么这三个字符明显是不同的字符串，但是每一个字符的阿斯克码加起来的值是相同的，还是会有很大概率的哈希碰撞，均匀性不足。
所以这里可以利用大佬为字符串设计的哈希函数，比如 BKDR 字符哈希，其原理是将字符串的每一个字符的阿斯克码值相加，但是每次加当前的字符的阿斯克码之前，那么它会讲前面的字符的阿斯克码的累加和给乘以 131，这样让能够显著减少哈希碰撞，至于为什么是乘以 131 而不是其他数字，那么这就和数学有关了，那么读者感兴趣，下去也可以自己了解。
那么每一个键的类型会对应不同的映射函数，而这里 insert 函数是不知道键的数据类型，那么这里就得借助仿函数，来提供处理特定数据类型的整形映射的 () 运算符重载函数，并且可以采取模版的特化，先编写一个通用模版类_HashFun，那么该模板类内部定义了 () 运算符重载函数，其中默认该模版参数会被实例化为 size_t 类型，然后直接返回 () 运算符重载函数接收到的参数即可。
template<typename T>
class _HashFun {
public:
size_t operator()(const T& val) { return val; }
};
然后再是定义特化的模板类，那么首先就是 int 类型，因为 int 类型是有符号的，意味着键可以是负数，其也要经过二次映射，采取的方式直接强制类型转化成整形即可。
template<>
class _HashFun<int> {
public:
size_t operator()(const int& val) { return size_t(val); }
};
最后则是 string 类型，那么其采取的方式就是按照上文所说的 BKDR 字符哈希，那么每次加上当前字符的阿斯克码之前，会将前面的计算的字符的阿斯克码整体的累加和乘以 131。
template<>
class _HashFun<std::string> {
public:
size_t operator()(const std::string& val) {
size_t hash = 0;
for (int i = 0; i < val.size(); i++) {
hash = hash * 131 + val[i];
}
return hash;
}
};
所以这里就能够解释哈希表的第四个模版参数的作用，那么它会被实例化为带有处理键的映射 () 运算符重载函数的自定义类型。
但是调用库的 unordered_set 的时候，只需要提供一个模版参数，而调用 unordered_map，则需要提供两个模版参数，而并没有提供处理键的映射的仿函数对象的自定义类型。
之所以不需要，是因为底层会编写多个带有特定数据类型键的映射的 () 运算符重载函数的特化的模版类，所以只需要为第四个模版参数直接提供一个缺省参数，这里由于第一个模版参数会被实例化为键的数据类型，所以这里的缺省参数就是直接对应该键对应该键的特化的模版类，并且这里上层封装哈希表的 unordered_map 以及 unordered_set 甚至都不需要提供第四个模版参数。
template<typename key, typename T, typename keyofT, typename HashFun = _HashFun<key>>
class HashTable {
// ...
};
insert 函数要注意的就是这两个细节，那么接下来就定义两个仿函数对象，分别是提取键的仿函数对象 returnKey 以及将键映射为整形的仿函数对象 returnHash，那么在进行模运算之前，这里首先得判断哈希表中是否存在该键对应的数据，因为 unordered_map 以及 unordered_set 有去重的功能，所以这里需要先调用 find 函数，如果 find 函数返回值为 true，就不用再插入，返回为 false 就插入，但是在插入之前，那么得判断当前状态下的哈希表是否需要扩容，通过判断当前哈希表存储的节点数与哈希表桶数组的长度，如果哈希表存储的节点数大于等于桶数组的长度，意味着负载因子大于等于 1，那么就需要扩容。
而扩容的逻辑就是创建一个扩容之后的指针数组，然后让之前的指针数组中每一个链表的节点重新映射到新数组中去，那么这里有两种处理方式，第一种方式就是遍历旧的指针数组中的每一个节点，然后计算该节点映射到新数组的数组索引，然后创建一个新的节点，然后将数据拷贝到新节点中然后尾插，最后销毁旧节点。
而第二种方式，首先还是遍历原本哈希表中的每一个节点，计算其在新数组中的索引，但是这里并不创建新的节点，而是直接修改链接关系，将旧的节点直接头插在新节点的指针数组中即可，然后节点插入完，就调用 vector 的 swap 函数，交换其 vector 中的动态数组，此时新创建的 vector 对象中保存的动态数组就是扩容之前的旧数组，那么它会随着 insert 函数调用结束后，随着函数栈帧一起被销毁，那么明显第二种方式，是更为优秀的方式。
if (_n == HT.size()) {
std::vector<Node*> newve;
size_t newsize = 2 * HT.size();
newve.resize(newsize);
for (int i = 0; i < HT.size(); i++) {
Node* cur = HT[i];
while (cur) {
Node* prev = cur->next;
size_t num = returnHash(returnKey(cur->data)) % newve.size();
Node* next = newve[num];
cur->next = next;
newve[num] = cur;
cur = prev;
}
}
HT.swap(newve);
}
最后一个环节就是获取新插入的数据的键，然后利用仿函数进行模运算得到数组索引，然后直接尾插即可。
void insert(const T& _data) {
HashFun returnHash;
keyofT returnKey;
if (find(returnKey(_data))) {
return;
}
if (_n == HT.size()) {
std::vector<Node*> newve;
size_t newsize = 2 * HT.size();
newve.resize(newsize);
for (int i = 0; i < HT.size(); i++) {
Node* cur = HT[i];
while (cur) {
Node* prev = cur->next;
size_t num = returnHash(returnKey(cur->data)) % newve.size();
Node* next = newve[num];
cur->next = next;
newve[num] = cur;
cur = prev;
}
}
HT.swap(newve);
}
size_t num = returnHash(returnKey(_data)) % HT.size();
Node* newnode = newNode(_data);
newnode->next = HT[num];
HT[num] = newnode;
_n++;
return;
}
有的读者如果知道库的 insert 函数以及 find 函数的返回值的话，那么事实上，insert 函数的返回值是一个 pair 元组，其中 first 是迭代器，second 则是一个 bool 值，而 find 函数的返回值是迭代器，那么这里之所以将 insert 函数的返回值写成 void 以及将 find 函数的返回值写成 bool，是因为迭代器还没讲，那么讲完迭代器之后，那么会完善 insert 函数接口。
unordered_set 以及 unordered_map 也分别提供了迭代器，来访问容器中的元素，那么知道 unordered_set 以及 unordered_map 底层采取的是哈希表，并且哈希表本质上是一个指针数组，每一个位置指向一个链表的头节点，而迭代器本质上模拟的就是指针的行为，但这里不能采取指向节点的原生指针直接作为迭代器，虽然这里的原生指针能够成功遍历某一个桶的单链表，可以直接使用原生指针的自增运算符来遍历某一个桶的单链表中的所有节点，但是遍历完该桶的链表，得想办法遍历下一个非空桶的链表，所以不能单纯的使用原生指针的自增运算符遍历整个桶数组中的所有节点，所以这里还是得对原生指针进行一个封装，并且重载自增运算符以及 * 运算符和 -> 运算符等。
而这里 unordered_set 以及 unordered_map 没有提供双向迭代器，意味着这里只需要重载自增运算符即可，那么自增运算的逻辑，就是从当前迭代器指向的某个链表的节点开始，移到下一个节点，那么要注意几种场景，如果当前迭代器指向的节点是该节点所处的链表中的最后一个节点，那么意味着就得找到下一个非空桶的链表中的头结点，该头结点就是迭代器移动的下一个位置，而如果当前迭代器指向的节点其并不是位于整个链表的末尾，迭代器移动的下一个位置就是其后继节点。
而如果迭代器指向的节点位于是位于链表的结尾，意味着得找到之后的非空桶的链表的头结点，那么这里迭代器中如果只封装一个指向节点的指针，面对刚才的场景，就无法访问到之后的桶，因为这里每一个节点只有指向后继节点的指针。
所以这里单纯只封装一个指向节点的指针还不够，那么还得封装一个指向哈希表对象的指针，然后通过解引用该指针去访问哈希表对象中的成员变量，也就是指针数组，由于哈希表中的成员变量是私有的，那么这里迭代器类要访问另一个类的私有成员变量，那么就需要在 HashTable 类中，将迭代器类定义为友元类。
那么这里迭代器能够访问哈希表的指针数组了，所以接下来实现一个自增运算符的逻辑就是，首先获取迭代器指向的节点的数据域中的键值 key，然后进行模运算计算出数组下标，从而得到该节点位于指针数组中哪一个位置对应的链表当中，但是要注意这里的数据域存储的可能是一个键也可能是一个键值对，所以这里要获取到键，那么就需要定义一个获取键值的仿函数对象，其中内部定义了获取键值的 () 运算符重载函数，同理这里获取到键值之后，这里的键值的类型可能是浮点或者 string 类型，所以还需要定义一个处理键的映射的仿函数对象，其内部定义了将键映射为整形的 () 运算符重载函数，所以这里的 Hash_iterator 还需要两个额外的模版参数 keyofT 以及 HashFuc。
template<typename key, typename T, typename ptr, typename ref, typename keyofT, typename HashFun>
class Hash_iterator {
private:
typedef HashNode<T> Node;
Node* _Node;
HashTable<key, T, keyofT, HashFuc>* HT;
// ...
};
template<typename key, typename T, typename keyofT, typename HashFuc>
class HashTable {
public:
template<typename key, typename T, typename ptr, typename ref, typename keyofT, typename HashFun>
friend class Hash_iterator;
// ...
};
而这里由于 Hash_iterator 内部封装了指向 HashTable 的对象的指针，而 HashTable 的第一个模版参数是键的数据类型，意味着这里 Hash_iterator 中也得包含这个模版参数，尽管这个模版参数在 Hash_iterator 类中的各个成员函数中都不会用到。
这下就能够完善自增运算符的代码逻辑了：首先我们需要判断迭代器指向的节点是否为空，如果为空就直接返回，如果不为空，那么我们在判断迭代器指向的该节点是否有后继节点，有，就将迭代器内部的指针移动到后继节点，没有的话，意味着该节点位于链表的末尾，那么就得计算出其所处的数组下标 i，然后再定义一个指针，来遍历 i 位置之后的指针数组的每一个位置，如果遍历结束，该指针非空，就说明找到了 i 之后的非空桶，那么迭代器中指向节点的指针移到该桶对应的链表的头结点，而如果指针为空，说明 i 位置之后的所以桶都是空链表，那么就将迭代器中指向节点的指针设置为 nullptr。
self& operator++() {
if (_Node == nullptr) {
return *this;
}
if (_Node->next) {
_Node = _Node->next;
return * this;
}
keyofT returnKey;
HashFun returnHash;
size_t currentnum = returnHash(returnKey(_Node->data)) % HTptr->HT.size();
size_t nextnum = currentnum + 1;
while (nextnum < HTptr->HT.size() && HTptr->HT[nextnum] == nullptr) {
nextnum++;
}
if (nextnum < HTptr->HT.size()) {
_Node = HTptr->HT[nextnum];
} else {
_Node = nullptr;
}
return *this;
}
这里实现的是前置自增运算符重载函数，所以返回值就是已经移到下一个节点的迭代器引用，这里将迭代器给 typedef 取了一个别名为 self。
typedef Hash_iterator<key, T, ptr, ref, keyofT, HashFun> self;
而知道 unordered_map 以及 unordered_set 有 const 版本的迭代器以及非 const 版本的迭代器，这里可以为 const 版本以及非 const 版本各自编写一个模版类，但更为优秀的做法是：让 const 版本以及非 const 版本复用同一个模板类，然后实例化成 const 版本的迭代器以及非 const 版本的迭代器。
而 const 版本的迭代器类与非 const 版本的迭代器类的区别就是能否通过迭代器来修改键值 key 对应的值 value，那么迭代器访问节点中的数据域则是通过 * 运算符以及 -> 运算符来访问，如果数据域是一个键值，那么就可以直接通过 * 运算符来访问，而如果数据域是一个键值对，那么就需要 -> 来访问键值对中的 first 以及 second，因为 * 返回的就是节点的数据域的引用（T &），而 -> 返回的是节点的数据域的指针（T *），如果数据域是一个 pair，那么直接通过 -> 运算符：it->first 以及 it->second(it 是迭代器) 来访问键值对的 first 和 second。
T* operator*() { return _Node->data; }
T& operator->() { return &_Node->data; }
虽然这里 -> 返回的是数据域的指针，也就是 pair* 的指针，所以理论上要访问 pair 元组中的 first 或者 second，应该解引用两次，也就是 it->->first，第一次解引用是获取 pair *，第二次是解引用 pair * 获取元组中的 first 或者 second，但是这里编译器进行了优化，只需要一次解引用：it->first。
所以这里 const 版本的迭代器以及非 const 版本的迭代器只需要控制 * 运算符重载函数以及 -> 运算符重载函数的返回值即可，如果是 const 版本的迭代器，那么 * 运算符重载函数以及 -> 运算符重载函数的返回值应该分别返回的是 const 修饰的引用以及 const 修饰的指针，这样就不能通过迭代器修改节点的数据域，而非 const 版本的迭代器的 * 运算符重载函数以及 -> 运算符重载函数则是返回非 const 的引用和非 const 修饰的指针，所以这里将引用和指针设置为了第三个个模版参数 ptr 以及第四个模版参数 ref。
template<typename key, typename T, typename ptr, typename ref, typename keyofT, typename HashFuc>
class Hash_iterator {
public:
// ...
ref operator*() { return _Node->data; }
ptr operator->() { return &_Node->data; }
// ...
};
所以这里在 HashTable 中，就可以根据第三个模版参数 Ptr 以及第四个模版参数 ref 来实例化出 const 版本的迭代器以及非 const 版本的迭代器，并且用 typedef 将 const 版本的迭代器去别名为 const_iterator，将非 const 版本的迭代器取别名为 iterator。
template<typename key, typename T, typename keyofT, typename HashFun>
class HashTable {
// ...
public:
typedef Hash_iterator<key, T, T*, T&, keyofT, HashFun> iterator;
typedef Hash_iterator<key, T, const T*, const T&, keyofT, HashFun> const_iterator;
// ...
};
说道这里读者认为这里在实现完 == 以及 != 比较运算符重载函数就结束了，但是这里其实还有一个大坑。
这里发现 HashTable 类内部封装一个迭代器类型的别名，而 Hash_iterator 类中则会封装一个指向 HashTable 对象的指针，而由于这里 Hash_iterator 的模板类的定义和 HashTable 的模板类的定义是封装到同一个头文件中，那么会形成一个相互依赖，相互引用。
那么如果 Hash_iterator 的定义在 HashTable 的上方，那么这里 Hash_iterator 内部封装了一个指向 HashTable 对象的指针，而这里编译器检查 HashTable 只会前置检查，而由于这里 HashTable 的定义在后文，那么编译器是不会检查到 HashTable 的，所以这里需要一个前置的模版类的声明，来告诉编译器，这里的 HashTable 是一个模板类。
template<typename key, typename T, typename keyofT, typename HashFuc = _HashFun<key>>
class HashTable;
template<typename key, typename T, typename ptr, typename ref, typename keyofT, typename HashFun = _HashFun<key>>
class Hash_iterator {
private:
typedef HashNode<T> Node;
Node* _Node;
HashTable<key, T, keyofT, HashFuc> HT;
// ...
};
template<typename key, typename T, typename keyofT, typename HashFuc>
class HashTable {
// ...
};
而由于这里迭代器类有两个成员变量，所以这里在写迭代器的构造函数的时候，构造函数就需要接收两个参数分别是指向节点的指针以及指向哈希表对象的指针。
Hash_iterator(Node* ptr, const HashTable<key, T, keyofT, HashFun>* _HTptr) :_Node(ptr), HTptr(_HTptr) { }
最后就是 == 运算符重载函数和！= 运算符重载函数，那么其会接收一个迭代器对象，然后直接比较成员变量，也就是指向节点的指针即可。
bool operator==(const self& p) { return _Node == p._Node; }
bool operator!=(const self& p) { return _Node != p._Node; }
实现了迭代器，那么上层封装哈希表的 unordered_map 以及 unordered_set 类也需要给外部提供迭代器类型，所以这里上层需要访问 HashTable 中的迭代器类型，然后再取一个别名。
template<typename key>
class unordered_set {
private:
class keyofSetT {
public:
const key& operator()(const key& k) { return k; }
};
HashTable<key, key, keyofSetT> _HT;
public:
typedef typename HashTable<key, key, keyofSetT>::const_iterator iterator;
typedef typename HashTable<key, key, keyofSetT>::const_iterator const_iterator;
// ...
};
注意这里 typedef 后面要加 typename，因为需要告诉编译器域作用限定符::后面的内容，应该解释为类型而不是静态成员变量，其次就是由于 unordered_set 不能修改键值，而这里访问 unordered_set 容器中的元素只能通过迭代器去访问，所以这里将 iterator 以及 const_iterator 都设置为 HashTable 中 const_iterator 的别名。
template<typename key, typename val>
class unordered_map {
private:
class keyofMapT {
public:
const key& operator()(const std::pair<key, val> _kv) { return _kv.first; }
};
HashTable<const key, std::pair<key, val>, keyofMapT> _HT;
public:
typedef typename HashTable<const key, std::pair<key, val>, keyofMapT>::iterator iterator;
typedef typename HashTable<const key, std::pair<key, val>, keyofMapT>::const_iterator const_iterator;
// ...
};
这里对于 unordered_map 来说，那么其迭代器就是正常的对应，iterator 就是 HashTable 中 iterator 的别名，const_iterator 就是 HashTable 中的 const_iterator 的别名，但是这里 unordered_map 不能修改键值 key，但是可以修改键值 key 对应的值 value，所以这里 unordered_map 封装的 HashTable 对象，实例化的键值 key 的属性是 const，所以一旦尝试用非 const 版本迭代器去修改键值对中的 first，那么就会报错，因为其属性已经被设置为 const。
介绍完迭代器，那么就能实现 begin 函数以及 end 函数了，那么 begin 函数就是返回一个指向哈希表中第一个非空桶中的链表的头节点的迭代器，其实现原理就是定义一个指针，去遍历访问哈希表即可，而 end 函数则是返回返回一个指向 nullptr 的迭代器，并且这里 begin 和 end 都应该提供 const 版本和非 const 版本。
iterator begin() {
for (int i = 0; i < HT.size(); i++) {
if (HT[i]) {
return iterator(HT[i], this);
}
}
return iterator(nullptr, this);
}
const_iterator begin() const {
for (int i = 0; i < HT.size(); i++) {
if (HT[i]) {
return const_iterator(HT[i], this);
}
}
return const_iterator(nullptr, this);
}
iterator end() {
return iterator(nullptr, this);
}
const_iterator end() const {
return const_iterator(nullptr, this);
}
find 函数则是查找哈希表中是否存在该键值的节点，如果存在就返回指向该节点的迭代器，不存在，就返回指向 nullptr 的迭代器，而 find 函数的实现原理较为简单，那么就是定义一个指针，依次遍历哈希表中所有的非空链表即可，其中需要利用获取键的仿函数对象的（）运算符重载函数来提取键，所以需要定义一个仿函数对象，最后注意要实现 find 的 const 版本以及非 const 版本。
iterator find(const key& k) {
keyofT returnKey;
HashFun returnHash;
size_t num = returnHash(k) % HT.size();
Node* cur = HT[num];
while (cur) {
if (returnKey(cur->data) == k) {
return iterator(cur, this);
}
cur = cur->next;
}
return iterator(nullptr, this);
}
const_iterator find(const key& k) const {
HashFun returnHash;
keyofT returnKey;
size_t num = returnHash(k) % HT.size();
Node* cur = HT[num];
while (cur) {
if (returnKey(cur->data) == k) {
return const_iterator(cur, this);
}
cur = cur->next;
}
return const_iterator(nullptr, this);
}
底层的哈希表实现好了 find 函数之后，那么上层的 unordered_map 以及 unordered_set 函数就只需要复用这里底层实现好的 find 函数。
template<typename key, typename val>
class unordered_map {
// ...
public:
iterator find(const key& k) { return _HT.find(k); }
const_iterator find(const key& k) const { return _HT.find(k); }
// ...
};
template<typename key>
class unordered_set {
public:
iterator find(const key& k) { return _HT.find(k); }
};
了解了迭代器之后，那么就可以完善 insert 函数接口，那么 insert 函数的返回值是一个元组，其 first 是迭代器，second 是一个 bool 值，insert 插入之前，会取出插入数据的键，检查哈希表是否存在该键的数据，如果存在，那么就直接返回一个元组，其中 first 就是指向已经存在节点的迭代器，second 就是 false，而如果不存在，那么插入新创建的节点之后，就返回一个元组，其中 first 是指向新创建的节点的迭代器，那么 second 就是 true 调用。
其中检查哈希表是否存在该键对应的节点，就可以调用 find 函数，然后利用 find 的函数的返回值来进行判断即可。
这里在返回元组的时候，采取的方式则是构建一个匿名的迭代器对象，其中要传递指向节点的指针和 this 指针该迭代器带参的构造函数，因为 this 指针就是指向哈希表对象的指针，那么由于这里是传值返回，所以这里返回匿名对象是没有问题的。
std::pair<iterator, bool> insert(const T& _data) {
HashFun returnHash;
keyofT returnKey;
iterator exit = find(returnKey(_data));
if (exit != end()) {
return std::make_pair(exit, false);
}
if (_n == HT.size()) {
std::vector<Node*> newve;
size_t newsize = 2 * HT.size();
newve.resize(newsize);
for (int i = 0; i < HT.size(); i++) {
Node* cur = HT[i];
while (cur) {
Node* prev = cur->next;
size_t num = returnHash(returnKey(cur->data)) % newve.size();
Node* next = newve[num];
cur->next = next;
newve[num] = cur;
cur = prev;
}
}
HT.swap(newve);
}
size_t num = returnHash(returnKey(_data)) % HT.size();
Node* newnode = newNode(_data);
newnode->next = HT[num];
HT[num] = newnode;
_n++;
return std::make_pair(iterator(newnode, this), true);
}
而底层实现好了哈希表的 insert 函数之后，那么上层就直接复用哈希表的 insert 函数即可。
template<typename key, typename val>
class unordered_map {
// ...
public:
std::pair<iterator, bool> insert(const std::pair<key, val>& data) { return _HT.insert(data); }
// ...
};
而这里要注意的就是 unordered_set 的 insert 函数，由于上层的 unordered_set 类的 iterator 以及 const_iterator 都是 const_iterator 的别名，所以这里 unordered_set 中返回的元组，也就是 std::pair<iterator, bool>，那么这里元组的 first 实际上是一个 const_iterator，也就是 const 版本的迭代器，其会返回底层的哈希表的 insert 函数的返回值给外部，但事实上，底层的哈希表的 insert 函数返回的元组的 first 的 iterator，是非 const 版本的迭代器，所以这里就需要非 const 版本转化为 const 版本。
那么这就需要隐式类型转化，那么要实现隐式类型转化，这就需要我们在迭代器类定义一个接收非 const 版本迭代器的构造函数，而这里将 Hash_iterator<key,T,T*,T&,keyofT,HashFuc> 这个非 const 版本的迭代器给 typedef 为了 iterator，方便书写。
template<typename key, typename T, typename ptr, typename ref, typename keyofT, typename HashFun = _HashFun<key>>
class Hash_iterator {
private:
// ...
typedef Hash_iterator<key, T, T*, T&, keyofT, HashFun> iterator;
public:
// ...
};
但是注意 const 版本的迭代器和非 const 版本的迭代器虽然共有同一个模板类，但是经过实例化之后，他们是两个不同的类，而这里的成员变量的属性都是私有的，所以 const 版本的实例化之后的类无法访问非 const 版本实例化之后的类中的私有属性的成员变量，那么这就要求定义一个共有的接口，分别返回指向节点的指针以及返回指向哈希表对象的指针。
Node* getNode() const { return _Node; }
const HashTable<key, T, keyofT, HashFun>* getHTptr() const { return HTptr; }
那么这两个接口注意后面应该添加 const 修饰符，因为 unordered_set 对象可以被 const 修饰，那么被 const 修饰的对象，那么其成员变量的属性也是 const，那么 unordered_set 对象中的成员变量就是哈希表对象，那么哈希表对象也会被 const 修饰，意味着指向哈希表对象的 this 指针也会被 const 修饰，所以这里两个接口后面一定要加 const 修饰。
所以对于 getHTptr 接口来说，其返回的指向哈希表对象的属性很有可能是 const，所以这里就得将返回值设置为 const 属性，而这里既然 getHTptr 的返回的是 const 属性的接口，那么这里 const 属性只能被 const 属性的变量接收，而不能被非 const 属性的变量接收，也就是允许权限的平移或者缩小，但不允许权限的放大，所以这里还得将 Hash_iterator 中的指向哈希表对象的指针的属性设置为 const。
template<typename key, typename T, typename ptr, typename ref, typename keyofT, typename HashFun = _HashFun<key>>
class Hash_iterator {
private:
// ...
Node* _Node;
const HashTable<key, T, keyofT, HashFun>* HTptr;
public:
Hash_iterator(const iterator& it) :_Node(it.getNode()), HTptr(it.getHTptr()) {}
Node* getNode() const { return _Node; }
const HashTable<key, T, keyofT, HashFun>* getHTptr() const { return HTptr; }
// ...
};
而有的读者这里可能会有疑问，这里的_Node，也就是指向节点的指针为什么也不设置为 const，不将其设置为 const，这里能够正常运行吗？
那么首先想说，如果将这里指向节点的指针设置为 const，unordered_set 倒是没啥问题，因为只能通过迭代器访问键值而不允许修改，但对于 unordered_map 来说，它也是复用的同一个迭代器的模板类，其还需要迭代器修改 pair 中的 value，那么你这里将指向节点的指针设置为 const，意味着 unordered_map 不管是 const 还是非 const 版本的迭代器都无法修改键值 key 对应的值 value，所以这里肯定是不能将其设置为 const 的。
那么这里关键就是_Node，也就是指向节点的指针不被 const 修饰，为什么正确呢？是因为 HashTable 中各个返回迭代器的成员函数，比如 insert 和 find 以及 begin 和 end 函数，那么其返回迭代器之前，会初始化迭代器，也就是必须传递参数给迭代器带参的构造函数，其中传递一个指向节点的指针和 this 指针，而这里传递指向节点的指针的属性，全部都是非 const 的属性，可以看上文的 find 以及 insert 等函数的代码，那么返回一个匿名迭代器对象的时候，传递指向节点的指针，没有一个是被 const 修饰，意味着这里迭代器中的指向节点的指针的属性一定是非 const。
这也是为什么 getNode 返回的指针不加 const 的原因，就是保证迭代其中的指向节点的指针的属性一定是非 const 的，所以这里迭代器的_Node 成员变量不用加 const 修饰。
erase 函数则是删除对应键的节点，而这里不能直接调用 find 函数，因为 find 函数只能返回指向该节点的迭代器，而这里是单链表，没有指向前驱节点的指针，那么释放掉迭代器指向的节点的空间之后，还要让该节点的前驱节点指向其后继节点。
所以这里只能自己来遍历，那么还是根据键值，计算出节点位于哪一个数组下标对应的链表中，然后定义两个指针 prev 和 cur 来遍历该链表，其中 prev 指针来记录前驱节点，另一个 cur 指针来记录当前遍历的节点，因为每一次 cur 移动到后继节点之前，那么会将值拷贝给 prev，那么一旦找到，此时 cur 指针指向的就是要删除的节点。
但是要注意如果删除的节点可能是链表的头结点，这里由于每次 cur 赋值给 prev 之前，会先判断当前 cur 指向的节点是否就是匹配该键值的节点。
而如果删除节点是链表的头结点，那么此时 cur 就不用移动到下一个节点，而在遍历之前，prev 的值是 nullptr，所以这里不能直接解引用 prev，而是直接将该数组下标的元素保存 cur 指向的节点的后继节点的地址。
而如果删除的节点不是链表的头结点，那么此时 prev 指向的就是删除节点的前驱节点，那么就让 prev 指向节点的 next 指针，指向 cur 的后继节点，然后删除 cur 指向的节点即可。
void erase(const key& k) {
HashFun returnHash;
keyofT returnKey;
size_t num = returnHash(k) % HT.size();
Node* cur = HT[num];
Node* prev = nullptr;
while (cur) {
if (returnKey(cur->data) == k) {
if (prev) {
prev->next = cur->next;
} else {
HT[num] = cur->next;
}
delete cur;
_n--;
return;
}
prev = cur;
cur = cur->next;
}
}
这里由于哈希表中的指针数组的每一个链表的节点都是从堆上申请的，那么这里就需要析构链表中的每一个节点，那么实现原理很简单，就是遍历指针数组，然后依次释放每一个非空链表的节点即可。
~HashTable() {
for (int i = 0; i < HT.size(); i++) {
Node* cur = HT[i];
while (cur) {
Node* next = cur->next;
delete cur;
cur = next;
}
HT[i] = nullptr;
}
}
#pragma once
#include <string>
#include <vector>
namespace my_std {
template<typename T>
class _HashFun {
public:
size_t operator()(const T& val) { return val; }
};
template<>
class _HashFun<int> {
public:
size_t operator()(const int& val) { return size_t(val); }
};
template<>
class _HashFun<std::string> {
public:
size_t operator()(const std::string& val) {
size_t hash = 0;
for (int i = 0; i < val.size(); i++) {
hash = hash * 131 + val[i];
}
return hash;
}
};
template<typename T>
class HashNode {
:
T data;
HashNode<T>* next;
( T& val) :(val), () {}
};
< key, T, keyofT, HashFuc = _HashFun<key>>
HashTable;
< key, T, ptr, ref, keyofT, HashFun = _HashFun<key>>
Hash_iterator {
:
HashNode<T> Node;
Hash_iterator<key, T, ptr, ref, keyofT, HashFun> self;
Hash_iterator<key, T, T*, T&, keyofT, HashFun> iterator;
Node* _Node;
HashTable<key, T, keyofT, HashFun>* HTptr;
:
(Node* ptr, HashTable<key, T, keyofT, HashFun>* _HTptr) :_Node(ptr), (_HTptr) {}
( iterator& it) :_Node(it.()), (it.()) {}
{ _Node; }
{ HTptr; }
self& ++() {
(_Node == ) {
*;
}
(_Node->next) {
_Node = _Node->next;
*;
}
keyofT returnKey;
HashFun returnHash;
currentnum = ((_Node->data)) % HTptr->HT.();
nextnum = currentnum + ;
(nextnum < HTptr->HT.() && HTptr->HT[nextnum] == ) {
nextnum++;
}
(nextnum < HTptr->HT.()) {
_Node = HTptr->HT[nextnum];
} {
_Node = ;
}
*;
}
ref *() { _Node->data; }
ptr ->() { &_Node->data; }
==( self& p) { _Node == p._Node; }
!=( self& p) { _Node != p._Node; }
};
< key, T, keyofT, HashFun>
{
:
HashNode<T> Node;
std::vector<Node*> HT;
_n;
:
Hash_iterator<key, T, T*, T&, keyofT, HashFun> iterator;
Hash_iterator<key, T, T*, T&, keyofT, HashFun> const_iterator;
() :_n() { HT.(, ); }
~() {
( i = ; i < HT.(); i++) {
Node* cur = HT[i];
(cur) {
Node* next = cur->next;
cur;
cur = next;
}
HT[i] = ;
}
}
< key, T, ptr, ref, keyofT, HashFun>
;
{
keyofT returnKey;
HashFun returnHash;
num = (k) % HT.();
Node* cur = HT[num];
(cur) {
((cur->data) == k) {
(cur, );
}
cur = cur->next;
}
(, );
}
{
HashFun returnHash;
keyofT returnKey;
num = (k) % HT.();
Node* cur = HT[num];
(cur) {
((cur->data) == k) {
(cur, );
}
cur = cur->next;
}
(, );
}
{
HashFun returnHash;
keyofT returnKey;
iterator exit = ((_data));
(exit != ()) {
std::(exit, );
}
(_n == HT.()) {
std::vector<Node*> newve;
newsize = * HT.();
newve.(newsize);
( i = ; i < HT.(); i++) {
Node* cur = HT[i];
(cur) {
Node* prev = cur->next;
num = ((cur->data)) % newve.();
Node* next = newve[num];
cur->next = next;
newve[num] = cur;
cur = prev;
}
}
HT.(newve);
}
num = ((_data)) % HT.();
Node* newnode = (_data);
newnode->next = HT[num];
HT[num] = newnode;
_n++;
std::((newnode, ), );
}
{
HashFun returnHash;
keyofT returnKey;
num = (k) % HT.();
Node* cur = HT[num];
Node* prev = ;
(cur) {
((cur->data) == k) {
(prev) {
prev->next = cur->next;
} {
HT[num] = cur->next;
}
cur;
_n--;
;
}
prev = cur;
cur = cur->next;
}
}
{
( i = ; i < HT.(); i++) {
(HT[i]) {
(HT[i], );
}
}
(, );
}
{
( i = ; i < HT.(); i++) {
(HT[i]) {
(HT[i], );
}
}
(, );
}
{ (, ); }
{ (, ); }
};
}
#pragma once
#include "hashbucket.h"
namespace wz {
template<typename key, typename val>
class unordered_map {
private:
class keyofMapT {
public:
const key& operator()(const std::pair<key, val> _kv) { return _kv.first; }
};
my_std::HashTable<const key, std::pair<key, val>, keyofMapT> _HT;
public:
typedef typename my_std::HashTable<const key, std::pair<key, val>, keyofMapT>::iterator iterator;
typedef typename my_std::HashTable<const key, std::pair<key, val>, keyofMapT>::const_iterator const_iterator;
std::pair<iterator, bool> insert(const std::pair<key, val>& data) { return _HT.insert(data); }
iterator find(const key& k) { return _HT.find(k); }
const_iterator find(const key& k) const { return _HT.find(k); }
void { _HT.(k); }
{ _HT.(); }
{ _HT.(); }
{ _HT.(); }
{ _HT.(); }
val& []( key& k) {
std::pair<iterator, > _pair = (std::(k, ()));
_pair.first->second;
}
};
}
#pragma once
#include "hashbucket.h"
namespace wz {
template<typename key>
class unordered_set {
private:
class keyofSetT {
public:
const key& operator()(const key& k) { return k; }
};
my_std::HashTable<key, key, keyofSetT> _HT;
public:
typedef typename my_std::HashTable<key, key, keyofSetT>::const_iterator iterator;
typedef typename my_std::HashTable<key, key, keyofSetT>::const_iterator const_iterator;
std::pair<iterator, bool> insert(const key& k) {
std::pair<iterator, bool> p = _HT.insert(k);
return std::pair<iterator, bool>(p.first, p.second);
}
iterator find(const key& k) { return _HT.find(k); }
void erase(const key& k) { _HT.erase(k); }
iterator begin() const { return _HT.(); }
{ _HT.(); }
};
}
#include <iostream>
#include <cassert>
#include <string>
#include <vector>
#include "hashbucket.h"
#include "myunordered_map.h"
#include "myunordered_set.h"
using namespace std;
using namespace my_std;
using namespace wz;
void test_HashFun() {
cout << "Testing _HashFun..." << endl;
_HashFun<int> intHash;
assert(intHash(42) == 42);
cout << "Int hash function test passed." << endl;
_HashFun<std::string> stringHash;
size_t hash1 = stringHash("hello");
size_t hash2 = stringHash("world");
assert(hash1 != hash2);
cout << "String hash function test passed." << endl;
cout << "All _HashFun tests passed!" << endl << endl;
}
void test_HashTable_basic() {
cout << "Testing HashTable basic operations..." << endl;
HashTable<int, , _HashFun<>> ht;
cout << << endl;
result = ht.();
(result.second == );
(*result.first == );
cout << << endl;
result2 = ht.();
(resultsecond == );
cout << << endl;
found = ht.();
(found != ht.());
(*found == );
cout << << endl;
notFound = ht.();
(notFound == ht.());
cout << << endl;
cout << << endl << endl;
}
{
cout << << endl;
HashTable<, , _HashFun<>> ht;
(ht.() == ht.());
cout << << endl;
ht.();
ht.();
ht.();
sum = ;
( it = ht.(); it != ht.(); ++it) {
sum += *it;
}
(sum == );
cout << << endl;
(ht.() != ht.());
cout << << endl;
cout << << endl << endl;
}
{
cout << << endl;
HashTable<, , _HashFun<>> ht;
ht.();
(ht.() != ht.());
ht.();
(ht.() == ht.());
cout << << endl;
ht.();
cout << << endl;
( i = ; i < ; i++) {
ht.(i);
}
( i = ; i < ; i += ) {
ht.(i);
}
( i = ; i < ; i++) {
it = ht.(i);
(i % == ) {
(it == ht.());
} {
(it != ht.());
}
}
cout << << endl;
cout << << endl << endl;
}
{
cout << << endl;
unordered_set<> uset;
result = uset.();
(result.second == );
(*result.first == );
cout << << endl;
result2 = uset.();
(resultsecond == );
cout << << endl;
found = uset.();
(found != uset.());
(*found == );
notFound = uset.();
(notFound == uset.());
cout << << endl;
uset.();
(uset.() == uset.());
cout << << endl;
uset.();
uset.();
uset.();
count = ;
( it = uset.(); it != uset.(); ++it) {
count++;
(*it >= && *it <= );
}
(count == );
cout << << endl;
cout << << endl << endl;
}
{
cout << << endl;
unordered_map<, std::string> umap;
result = umap.({ , });
(result.second == );
(result.first->first == );
(result.first->second == );
cout << << endl;
result2 = umap.({ , });
(resultsecond == );
(resultirst->second == );
cout << << endl;
found = umap.();
(found != umap.());
(found->first == );
(found->second == );
notFound = umap.();
(notFound == umap.());
cout << << endl;
umap.();
(umap.() == umap.());
cout << << endl;
umap[] = ;
(umap.() != umap.());
(umap[] == );
umap[] = ;
(umap[] == );
(umap.() == umap.());
umap[] = ;
(umap.() != umap.());
(umap[] == );
cout << << endl;
umap[] = ;
umap[] = ;
umap[] = ;
count = ;
( it = umap.(); it != umap.(); ++it) {
count++;
(it->first >= && it->first <= );
(!it->second.());
}
(count == );
cout << << endl;
cout << << endl << endl;
}
{
cout << << endl;
HashTable<, , _HashFun<>> ht;
ht.();
ht.();
ht.();
(ht.() != ht.());
(ht.() != ht.());
(ht.() != ht.());
cout << << endl;
cout << << endl << endl;
}
{
cout << << endl;
HashTable<, , _HashFun<>> ht;
COUNT = ;
( i = ; i < COUNT; i++) {
ht.(i);
}
( i = ; i < COUNT; i++) {
(ht.(i) != ht.());
}
cout << << endl;
cout << << endl << endl;
}
{
cout << << endl << endl;
();
();
();
();
();
();
();
();
cout << << endl;
;
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online