数据结构---散列表(Hash Set)

概览

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

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

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

哈希表的原理

哈希表(散列表): 借助 哈希函数, 将键映射到存储桶地址:

• 首先, 开辟一定长度的, 具有连续物理地址的桶数组
• 在插入一个新键时, 哈希函数将决定该键应该分配到哪个桶中, 并将该键存储在相应的桶中
• 在搜索一个键时, 哈希表 将使用哈希函数来找到对应的桶, 并在该桶中进行搜索

什么是哈希函数

哈希函数会起到压缩键的地址空间的作用, 设键的地址空间为S, 桶的地址空间则为 T, 那么 S 远大于 T

• 哈希函数的结果(键)与桶的对应关系具有确定性
• 哈希函数不应该太过复杂
• 哈希函数的结果分布应具有均匀性

理想情况下, 完美的哈希函数是键与桶的一一对应, 但是完美的哈希函数并不常见, 一般来讲, 结果分布越随机, 越均匀的哈希函数, 它的性能越好, 一方面, 如果分布过于集中再某些桶中, 会加剧这些桶发生冲突的概率, 另一方面, 剩余的桶由于没有得到有效利用导致空间利用率较低

负载因子(装填因子)

是哈希表的一个重要参数，它反映了哈希表的装满程度; 假设一个公司的电话共有10个, 每个电话号码是 00000000 到 99999999 内的任意八位数字, 这里有一个方案: 将每个可能的电话号码作为一个桶, 使得电话好嘛与桶一一对应, 则一共需要 100000000 个桶; 其中 实际利用桶的个数 / 桶的总数 则为负载因子. 在这个例子中, 负载因子太小以至于接近于0, 这样的方案是不现实的. 一般情况下, 比较合理的负载因子是 0.7.

哪些因素会影响 哈希函数

哈希函数是导致冲突的原因之一，更进一步，如果我们增加桶的数量，再采用合适的哈希函数，可使发生冲突的可能性大大减小

哈希集合 和 哈希映射 之间的区别

如何正确使用 标准模板库 中的哈希集合及哈希映射

在哈希表中，插入 和 查找 操作的复杂度是多少？

如何使用 哈希集合 解决与重复元素相关的问题

如何使用 哈希映射 解决与滑动窗口相关的问题

如何在使用 哈希表 时设计正确的键