哈希表Hash-Table

概览：

​ 简单来说，哈希表是一种依赖哈希函数组织数据，以达到常数级别时间复杂度，插入和搜索都非常高效的数据结构。

两种哈系表：

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

大多数高级程序设计语言标准库里都内置了哈系表模板。

1、哈希表的原理

哈希表的关键思想是使用哈希函数 将键映射到存储桶。更确切地说，

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

示例

在示例中，我们使用 y = x % 5 作为哈希函数。让我们使用这个例子来完成插入和搜索策略：

1. 插入：我们通过哈希函数解析键，将它们映射到相应的桶中。

   • 例如，1987 分配给桶 2，而 24 分配给桶 4。

2. 搜索：我们通过相同的哈希函数解析键，并仅在特定存储桶中搜索。

   • 如果我们搜索 1987，我们将使用相同的哈希函数将 1987 映射到 2。因此我们在桶 2 中搜索，我们在那个桶中成功找到了 1987。
   • 例如，如果我们搜索 23，将映射 23 到 3，并在桶 3 中搜索。我们发现 23 不在桶 3 中，这意味着 23 不在哈希表中。

<!– 上述示例大多摘自 LeetCode –>

哈希散列函数：

​ 可以看得出元素存储位置与它的关键字建立了一个对应关系 F，在查找时就可以由键通过哈希函数映射出元素的索引位置（桶），而对应关系 F 就是哈希散列函数。哈希函数是哈希表中最重要的组件，哈希表用于将键映射到特定的桶。上述示例中 y = x % 5 作为散列函数，其中 x 是键值，y` 是分配的桶的索引。

<!– 以下示例大多摘自 LeetCode –>

​ 散列函数将取决于 键值的范围 和桶的数量。

下面是一些哈希函数的示例：

​ 哈希函数的设计是一个开放的问题。其思想是尽可能将键分配到桶中，理想情况下，完美的哈希函数将是键和桶之间的一对一映射。然而，在大多数情况下，哈希函数并不完美，它需要在桶的数量和桶的容量之间进行权衡。

2、冲突解决

理想情况下，如果我们的哈希函数是完美的一对一映射，我们将不需要处理冲突。不幸的是，在大多数情况下，冲突几乎是不可避免的。例如，在我们之前的哈希函数（y = x % 5）中，1987 和 2 都分配给了桶 2，这是一个 冲突(所以映射位置称之为桶，因为冲突时还需要在桶内作二次查找找到元素的位置)。

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

3、复杂度分析

如果总共有 M 个键，那么在使用哈希表时，可以达到 O(M) 的空间复杂度。

而哈希表的时间复杂度与设计有很强的关系。

以使用 数组 来将值存储在同一个桶中为例，理想情况下，桶的大小足够小时，可以看作是一个 常数。插入和搜索的时间复杂度都是 O(1)。

但在最坏的情况下，桶大小的最大值将为 N。插入时时间复杂度为 O(1)，搜索时为 O(N)。

内置哈希表的原理

高级程序设计语言内置哈希表的典型设计是：

1. 键值可以是任何 可哈希化的 类型。并且属于可哈希类型的值将具有 哈希码。此哈希码将用于映射函数以获取存储区索引。
2. 每个桶包含一个 数组，用于在初始时将所有值存储在同一个桶中。
3. 如果在同一个桶中有太多的值，这些值将被保留在一个 高度平衡的二叉树搜索树 中。

插入和搜索的平均时间复杂度仍为 O(1)。最坏情况下插入和搜索的时间复杂度是 O(logN)，使用高度平衡的 BST。这是在插入和搜索之间的一种权衡。

欢迎关注微信公众号：爱写 Bug