🖐️ 🔖 😡 您需要了解的基于哈希的集合 👨‍🎓 🐹 🏢

大家好。联系弗拉迪斯拉夫·罗丹（Vladislav Rodin）。我目前是OTUS高负载架构师课程的负责人，并且还教授软件架构课程。

如您所见，除了教学之外，我还在哈布雷（Habré）上为OTUS博客编写版权材料，并且我想将今天的文章专门用于开辟“开发者算法”课程的新流。

介绍

哈希表（HashMap）和动态数组是生产中最流行的数据结构。很多时候，您会在面试中听到有关其用途，内部结构特征以及相关算法的问题。这种数据结构是经典的，不仅可以在Java中找到，而且可以在许多其他编程语言中找到。

问题的提法

让我们设定一个目标来创建一个允许您执行以下操作的数据结构：

contains（Element element）检查元素是否在其中，用于O（1）
添加（元素元素）在O中添加元素（1）
delete（Element element）删除O中的元素（1）

数组

让我们尝试在数组（最简单的数据结构）上执行这些操作。我们同意，如果单元格包含null，我们将认为它为空。

可用性检查

有必要对数组进行线性搜索，因为该元素可能位于任何单元格中。渐近地，这可以在O（n）中完成，其中n是数组的大小。

新增中

如果需要在任何位置添加元素，则首先需要找到一个空单元格，然后将其写入其中。因此，我们再次进行线性搜索并获得O（n）的渐近行为。

删除

要删除元素，必须首先找到它，然后将null写入找到的单元格。再次线性搜索将我们引向O（n）。

最简单的哈希集

请注意，在每次操作中，我们首先搜索所需单元格的索引，然后执行该操作，而这种搜索会破坏我们的渐近性！如果我们学会了获得O（1）的索引，那么原来的问题将得到解决。

现在，用以下算法替换线性搜索：我们将计算某个函数的值-一个将类对象映射到整数的哈希函数。之后，我们将所得的整数与数组单元的索引进行比较（这很容易做到，例如，将这个数字除以数组大小即可得到余数）。如果哈希函数的写法被认为是O（1）（通常这样写），那么我们将获得哈希集的最简单实现。就哈希集而言，数组单元可以称为存储桶。

哈希集最简单实现的问题

无论散列函数如何编写，数组中的单元数始终是有限的，而我们要存储在数据结构中的元素集是无限的。毕竟，如果只需要保存十个以前已知的元素，我们就不会理会数据结构，对吗？这种事态导致不可避免的冲突。当添加不同的对象时，当我们落入数组中的同一单元格时，就会发生冲突。

发明了两种解决冲突的方法：链接方法和开放寻址方法。

链接方式

链接方法是解决冲突的最简单方法。在数组的单元格中，我们将不存储元素，而是存储这些元素的链表。因为添加到列表的顶部（并且我们不在乎向元素的列表的哪一部分添加）具有O（1）的渐近行为，所以我们不会破坏一般的渐近行为，并且它将保持等于O（1）。

这个实现有一个问题：如果列表增长很多（作为最后的选择，我们可以考虑一个散列函数，该哈希函数为任何对象返回一个常数），那么我们得到渐近O（m），其中m是集合中元素的数量，如果大小数组是固定的。为避免此类麻烦，引入了占空比的概念。（它可以等于1.5）。如果在添加元素时发现数据结构中的元素数量相对于数组大小的分数超过填充因子，则发生以下情况：选择一个新数组，其大小超过旧数组的大小（例如2倍），并重建数据结构在新阵列上。

解决冲突的这种方法在Java中使用，数据结构称为HashSet。

开放式寻址方法

在这种方法中，细胞本身被存储在细胞中，并且在发生碰撞的情况下，会发生一系列样本，也就是说，我们开始使用某种算法对细胞进行分类，以期找到一个自由的细胞。这可以通过不同的算法（样本的线性/二次序列，双重哈希）来完成，每种算法都有其自身的问题（例如，主要或次要群集的出现）。

从哈希集到哈希表（HashMap）

让我们创建一个数据结构，该结构允许您添加，删除，搜索项目，但是通过某种键，其速度与哈希集一样快（即，超过O（1））。

我们将使用与哈希集相同的数据结构，但我们将不存储元素，而是存储成对的元素。

因此，插入（put（键key，值value））将按以下方式实现：我们将通过Key类型的对象计算数组的单元格，我们将获得存储桶的数量让我们浏览存储桶中的列表，将密钥与存储对中的密钥进行比较。如果找到相同的密钥-挤压旧值，如果找不到，则添加一对。

钥匙如何接收物品？是的，根据相似的原理：我们通过键获取存储桶，遍历所有对并返回一对中的值，如果存在这样的对，则该键等于请求中的键，否则返回null。

该数据结构称为哈希表。

典型面试题

问：HashSet和HashMap如何安排？这些集合中的主要操作如何进行？如何应用equals（）和hashCode（）方法？
答：这些问题的答案可以在上面找到。

问：equals（）和hashCode（）的协定是什么？是什么原因
答：如果对象相等，则它们必须具有相等的hashCode。因此，hashCode必须由等于中涉及的字段的能力来确定。违反合同可能会产生非常有趣的效果。如果对象相等，但是它们的hashCode不同，则您可能无法获得与将对象添加到HashSet或HashMap的键对应的值。

结论

在面试时，他们喜欢询问与这些数据结构有关的不同案例。此外，可以通过了解他们的工作原理来推导出他们中任何一个的决定，而无需“塞满”。

就这样。如果您已阅读完该材料，请邀请我的同事Evgeny Volosatov向您展示如何使用动态编程的思想来解决奥林匹克竞赛问题，以免费课程 “动态编程的秘密”为主题。

您需要了解的基于哈希的集合

介绍