Letcode-HashTable-刷题记录

Hash Table

The Principle of Hash Table

Hash Table 是一种使用组织数据 hash functions 以支持的数据结构 quick insertion and search

设计哈希表的关键：

• 1. 哈希函数 哈希函数将取决于 the range of key values 和 the number of buckets。也就是 values 总数和 buckets 的数量；
  理想情况下，完美的哈希函数将是密钥和桶之间的一对一映射。但是，在大多数情况下，哈希函数并不完美，它是 the amount of buckets 和之间的权衡 the capacity of a bucket。

碰撞解决方案

理想情况下，如果我们的哈希函数是完美的 one-one mapping，我们将不需要处理冲突。不幸的是，在大多数情况下，碰撞几乎都是 inevitable。例如，在我们之前的散列函数（y = x%5）中，1987 和 2 都分配给了 bucket 2. 这是一个 collision。

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

如何在同一个桶中组织值？
如果为同一个存储桶分配了太多值，该怎么办？
如何搜索特定存储桶中的目标值？
这些问题都涉及到 the capacity of the bucket，并 the number of keys 可能被映射到 the same bucket 根据我们的哈希函数。

让我们假设拥有最大密钥数量的存储桶具有 N 密钥。
通常，如果 N 是常量且很小，我们可以简单地使用 a array 动态数组 来存储同一个桶中的密钥。如果 N 是可变的或大的，我们可能需要使用
height-balanced binary search tree 平衡二叉搜索树 。

实现

即实现 插入 查找 删除 动作
Insertion 并且 search 是哈希表中的两个基本操作
remove an element 我们将首先搜索元素，然后如果元素存在则从相应位置移除元素。

design HashSet

    add(value)：将值插入 HashSet。contains(value)：返回值是否存在于 HashSet 中。remove(value)：删除 HashSet 中的值。如果 HashSet 中不存在该值，则不执行任何操作。