哈希表、哈希集合(HashSet)、哈希映射(HashMap)_哈希集合和哈希表

哈希表

哈希表 是一种 使用 哈希函数 组织数据，以支持 快速插入和搜索 的 数据结构

有两种不同类型的哈希表：哈希集合和哈希映射

• 哈希集合 是 集合数据结构的实现之一，用于存储非重复值
• 哈希映射 是 映射数据结构的实现之一，用于存储(key, value)键值对

通过选择合适的哈希函数，哈希表可以在插入和搜索方面实现出色的性能

阅读参考：
https://leetcode-cn.com/leetbook/read/hash-table/x6sast/

哈希表的原理

哈希表的关键思想 是 使用 哈希函数 将 键 映射到 存储桶。更确切地说
当插入一个新的键时，哈希函数 将决定 该键 应该分配到 哪个桶中，并将该键存储在相应的桶中
当想要搜索一个键时，哈希表 将使用 相同的哈希函数 来查找 对应的桶，并只在特定的桶中进行搜索

在设计哈希表时，应该注意两个基本因素，一个是哈希函数、一个是键冲突
冲突解决算法应该解决以下几个问题：

• 如何组织在同一个桶中的值？
• 如果为同一个桶分配了太多的值，该怎么办？
• 如何在特定的桶中搜索目标值？

键冲突一般与三种办法：线性试探法、链地址法(就是数组 + 链表中的链表)、再哈希法、公共溢出区法

• 线性试探法，当 查找 某个键时，首先会通过哈希函数计算出桶的地址，然后比较该桶中保存的值是否为该键，如果不是，则继续向下寻找。如果查找到末尾，则会从头开始查找。而 删除 某个键时，为了避免查找过程中出现信息丢失，会将删除位置标记为 deleted，这样当进行线性查找时，遇到 deleted 会继续向下查找而不会中断
• 双重哈希法存在一些问题：与线性试探法相比，双重哈希法会消耗较多的时间。在双重哈希法中，删除会使问题变复杂，如果逻辑删除数量太多，则应重新构造哈希表
• 公共溢出区法，建立另一个哈希表 dict_overflow 作为公共溢出区，当发成冲突时则将该键保存在该哈希表中。若查找的键发生冲突，则在公共溢出区进行线性查找

通常，如果 N(一个桶中键的最大数) 是常数且很小，可以简单地使用一个数组将键存储在同一个桶中。如果 N 是可变的或很大，可能需要使用高度平衡的二叉树来代替

阅读参考：
https://leetcode-cn.com/leetbook/read/hash-table/xht3is/
https://leetcode-cn.com/leetbook/read/hash-table/xh8uld/

哈希集合-HashSet

哈希集是集合的实现之一，它是一种 存储 不重复值 的 数据结构
插入新值 并 检查 值 是否在哈希集中 是 简单有效的，通常使用 哈希集 来检查 该值是否已经出现过

阅读参考：
https://leetcode-cn.com/leetbook/read/hash-table/xhge27/
https://leetcode-cn.com/leetbook/read/hash-table/xhzxa5/

哈希映射

哈希映射 是用于 存储 (key, value) 键值对 的 一种实现
使用哈希映射的第一个场景是，需要更多的信息，而不仅仅是键。然后 通过 哈希映射 建立 密钥 与 信息之间 的 映射关系

在某些情况下，需要更多信息，不仅要返回更多信息，还要帮助做出决策，当遇到重复的键时，将立即返回相应的信息。但有时，可能想先检查键的值是否可以接受

另一个常见的场景是按键聚合所有信息。也可以使用哈希映射来实现这一目标，解决此类问题的关键是 在遇到 现有键时 确定策略

除此之外，根据值类别的不同，常用的构造方式还有以下几种：

• {键:频次}：使用频率最高，将元素出现的次数作为值
• {键:数组}：如果一个键对应的信息是一组元素，可使用数组或链表存储
• {键:平面坐标}：某些矩阵类习题可能会存储坐标
• {键:其他}：一般出现在模拟题中，根据实际需要设计哈希表

因此，当遇到某个问题可使用哈希表解决时，可以从以上几种构造方法中进行筛选

阅读参考：
https://leetcode-cn.com/leetbook/read/hash-table/xhy35e/
https://leetcode-cn.com/leetbook/read/hash-table/xhcuhg/
https://leetcode-cn.com/leetbook/read/hash-table-plus/x7exjr/

键 的 设计

设计 关键是在 原始信息 和 哈希映射 使用的 实际键之间 建立映射关系
设计键时，需要保证：

• 属于同一组的所有值都将映射到同一组中
• 需要分成不同组的值不会映射到同一组

此过程类似于设计哈希函数，但这是一个本质区别。哈希函数满足第一个规则但可能不满足第二个规则。但是映射函数应该满足它们

阅读参考：
https://leetcode-cn.com/leetbook/read/hash-table/xxez6m/
https://leetcode-cn.com/leetbook/read/hash-table/xxavl2/，这里有设计键的建议!!!