哈希表

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

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

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

哈希表的原理

使用哈希函数将键映射到存储桶

1. 当我们想插入一个新的键时，哈希函数将决定该键应该分配到哪个桶中，并将该键存储在相应的桶中
2. 当我们想搜索一个键时，哈希表将使用相同的哈希函数来查找对应的桶，并只在特定的桶中进行搜索

设计哈希表的关键

哈希函数

哈希函数是哈希表的最重要的组件，该哈希表用于将映射到特定的桶

冲突解决

冲突解决算法应该解决以下几个问题：

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

设计哈希集合

不使用任何内建哈希表库设计一个哈希集合

应该包含：

• add(value)：向哈希集合中插入一个值。
• contains(value)：返回哈希集合中是否存在这个值。
• remove(value)：将给定值从哈希集合中删除。如果哈希集合中没有这个值，什么都不做

设计哈希映射

不使用任何内建的哈希表设计一个哈希映射

• put(key, value)：向哈希映射中插入（键、值）的数值对。如果键对应的值已经存在，更新这个值
• get(key)：返回给定的键所对应的值，如果映射中不包含这个键，返回-1
• remove(key：如果隐射中存在这个键，删除这个数值对

实际应用-哈希集合

使用哈希集查重

插入新值并检查值是否在哈希集中是简单有效的。

存在重复元素

只出现一次的数字

列表操作

1. 遍历nums中的每一个元素
2. 如果某个nums中的数字是新出现的，则将它添加到列表中
3. 如果某个数字已经在列表中，删除它

两个数组的交集

快乐数