# 哈希表

> 关键词： hash, 哈希表, 哈希函数

<!-- TOC depthFrom:2 depthTo:2 -->

- [简介](#简介)
- [原理](#原理)
- [更多内容](#更多内容)

<!-- /TOC -->

## 简介

---

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

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

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

在`标准模板库`的帮助下，哈希表是`易于使用的`。大多数常见语言（如 Java，C ++ 和 Python）都支持哈希集合和哈希映射。

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

## 原理

---

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

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

### 哈希函数示例

<div align="center"><img src="https://gitee.com/turnon/images/raw/master/images/data-structure/hash/哈希函数.png"/></div>

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

1. 插入：我们通过哈希函数解析键，将它们映射到相应的桶中。
   - 例如，1987 分配给桶 2，而 24 分配给桶 4。
2. 搜索：我们通过相同的哈希函数解析键，并仅在特定存储桶中搜索。
   - 如果我们搜索 1987，我们将使用相同的哈希函数将 1987 映射到 2。因此我们在桶 2 中搜索，我们在那个桶中成功找到了 1987。
   - 例如，如果我们搜索 23，将映射 23 到 3，并在桶 3 中搜索。我们发现 23 不在桶 3 中，这意味着 23 不在哈希表中。

### 哈希表的关键

#### 1. 哈希函数

哈希函数是哈希表中最重要的组件，该哈希表用于将键映射到特定的桶。在上一节的示例中，我们使用 `y = x % 5` 作为散列函数，其中 `x` 是键值，`y` 是分配的桶的索引。

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

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

<div align="center"><img src="https://gitee.com/turnon/images/raw/master/images/data-structure/hash/哈希函数示例.png"/></div>

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

#### 2. 冲突解决

理想情况下，如果我们的哈希函数是完美的一对一映射，我们将不需要处理冲突。不幸的是，在大多数情况下，冲突几乎是不可避免的。例如，在我们之前的哈希函数（_y = x ％ 5_）中，1987 和 2 都分配给了桶 2，这是一个`冲突`。

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

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

根据我们的哈希函数，这些问题与`桶的容量`和可能映射到`同一个桶`的`键的数目`有关。

让我们假设存储最大键数的桶有 `N` 个键。

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

## 更多内容

https://leetcode-cn.com/explore/learn/card/hash-table/