导入
哈希表介绍
本课程简要介绍了哈希表数据结构及其基本实现原理。
哈希
到目前为止，大多数数据结构在插入、删除和搜索操作上的总体时间复杂度最高为 O(logn)，这已经相当不错了。但当数据量非常大时，这种复杂度开始对算法的效率产生不利影响。
理想的数据结构应当在执行所有三种操作时都只需常数时间。而这就正是哈希技术发挥作用的地方！
哈希是一种根据唯一键来存储对象的过程。这意味着哈希始终会创建一个键值对。多个这样的键值对组合在一起就构成了一个字典，其中每个对象或值都可以通过其键进行查找。因此，搜索操作的时间复杂度可以达到 O(1)。
哈希的概念催生了多种新的数据结构，其中最突出的是哈希表。
哈希表
如果你的算法特别注重搜索操作，那么哈希表就是最适合你的数据结构。在 C++ 中，哈希表通常使用数组实现，因为数组能够以常数时间访问元素。请看下图，了解键与数据对是如何存储在哈希表中的。
[(键, 数据) 对]
在本节中，我们将自行实现一个哈希表，因为它在编程面试中是一个非常热门的话题。让我们先从定义高效哈希表的基本构成开始。在进入具体实现之前，我们先来看一下影响哈希表性能的三个关键因素。
哈希表的性能取决于三个基本因素：
- 哈希函数
- 哈希表的大小
- 冲突处理方法