哈希表简介
引言
哈希表是一种包含键值对的数据结构。哈希表使用称为哈希函数的机制来存储和检索数据。哈希函数可以将键映射到哈希码，从而检索所需数据的索引。这类似于图书馆中的杜威十进制分类法，图书的查找依据是十进制编号。在杜威十进制分类法中，图书按类型分类，并被分配一个特定范围内的编号。
存储的数据
哈希表具有预定的长度，其中每个单元格存储一个键值对。这些单元格通常被称为“桶”。数据通常存储在一个数组中，每个桶都是该数组的一个索引。
哈希函数
正如我在本博客开头提到的，哈希表使用哈希函数。该函数通过输入键值来告诉我们如何在数组中找到某个元素。简而言之，该函数会将字符串映射到数字。理想情况下，哈希函数会为每个键值输出唯一的索引号。否则，检索元素的时间复杂度将接近 O(n)，其中 n 是数据集中的元素数量。当哈希函数对两个或多个不同的键值返回相同的索引时，就称为哈希冲突。
碰撞
当两个键映射到同一个数字或索引时，就会发生冲突。处理这种情况有几种不同的方法。一种方法是将具有相同索引的键值对存储在链表中。这称为分离链接法。使用这种方法，您需要遍历这些键值对才能找到所需的项。如果冲突很多，这种方法效率会很低，并且时间复杂度会接近 O(n)。
这里有一个包含冲突的例子。在这个例子中，键是狗的名字，值是狗的品种。我们对狗的名字进行哈希处理，以获得存储其数据的索引。Cruiser 和 Ranger 的名字哈希后都指向索引 7，因此它们被存储在链表的索引 7 处。
另一种处理冲突的方法是开放寻址，也称为封闭哈希。这种方法首先使用键值来确定数组中要查找的位置。如果该位置已满，则会使用某种方案来探测数组中的另一个位置。如此反复，直到找到一个空桶来存储数据。一种可用的方案是线性探测，即如果前一个位置已满，则查找数组中的下一个位置。这里有一篇很棒的 Stack Overflow 文章，对比了开放寻址和链式寻址。
通常情况下，开放寻址比单独链接更快。但是，如果所有存储桶都接近满，开放寻址就会变慢，因为它需要花费大量时间遍历所有存储桶并找到空闲位置。
运行时间
哈希表在数据检索、插入和删除方面速度很快，但在需要搜索/遍历数据时速度就比较慢了。例如，如果需要遍历数据以查找最大值，哈希表就不是最有效的数据结构。
从哈希表中检索、插入和删除操作的时间复杂度应该是 O(1)，除非哈希函数没有优化，并且存在冲突。例如，如果冲突很多，并且使用了分离链接法，则需要遍历列表才能找到所需的键值对。
关门时间
您在应用程序中何时使用过哈希表？非常希望听到一些关于这种数据结构的优秀用例。