哈希表简介

哈希表非常高效。假设我们要在数组中查找某个特定的人：我们必须遍历每一个元素来寻找这个人！这种情况下，时间复杂度为 O(n)，因为我们需要遍历数组中的每一个元素。

为了更高效地查找数据，可以使用哈希表！哈希表由两部分组成：一个用于存储数据的对象（即表格），以及一个哈希函数（或映射函数）。该函数通过将输入数据映射到数组中的一个特定索引，实现快速定位！这个函数接收一个键，并且对于同一个键，总是返回相同的索引！如果对同一个键多次调用该函数，都会得到相同的索引。

当我们实现并输出这个哈希表时，会得到如下结果：

1{
2   values: {
3      0: { "Mara": "BN" },
4      1: { "Sarah": "US" },
5      3: { "Emil": "SE" },
6      5: { "Lydia": "NL" },
7   },
8   length: 4,
9   size: 6,
10}

由于哈希函数对每个键始终生成相同的哈希值，我们可以轻松查找键值对。无需遍历整个对象，只需将目标键传入哈希函数，它就会返回该键值对存储的索引位置！

然而，有时不同的键可能会被哈希函数映射到同一个索引上。这种情况称为冲突。

此时，索引 0 处出现了两个键值对。如果我们现在要查找键为 “Lydia” 的键值对，就必须遍历该桶中的所有元素，直到找到正确的键（该桶以绿色显示）。

在下一节课中，我将讲解这种数据结构的具体实现方式。