Tag: 哈希表

哈希表寓言

在Swift中从头开始创建哈希表 理论 哈希表是一个强大的数据结构，大多数开发人员每天都在有意或无意地使用它们。 在Swift字典中是哈希表。 我们应该了解它们是如何工作的，以便我们可以最好地使用它们。 在本文中，我将介绍如何在Swift中制作哈希表的简化版本。 我建议，如果您想了解哈希表的内部工作原理，请遵循并与我一起做一个！ 什么是哈希表，我为什么要关心？ 哈希表是一种使用键存储和检索值的数据结构。 例如，我可以有一个名称和年龄的哈希表： myHashTable.set（值：30，forKey：“ Manny”） myHashTable.getValue（forKey：“ Manny”）//应该返回30 哈希表的特别之处在于，在正常情况下，我们可以使用键来获取值，而无需遍历数组。 如果我们有一个键值对数组，则必须在整个数组中搜索以找到特定的键值。 这通常称为O（n）访问时间，这意味着获取值的时间基于元素的数量（n）是线性的。 由于哈希表的强大功能，我们可以近似地将值取回O（1）（恒定时间），这使得哈希表非常适合存储我们要基于唯一键快速检索的数据。 重要的是要注意，哈希表不能保持顺序，并且不如用于遍历元素的数组好。 那么，这是什么O（1）法术？ 假设您将衣服堆成一堆。 每天早晨，您将不得不在堆里过筛以寻找当天的服装。 现在想象一下，您拥有的所有衣物都有一个抽屉，而这些物品总是放在同一抽屉中。 您将能够非常快速地检索每件衣服！ 过于简单的解释是，使用魔术哈希函数，我们的密钥被映射为整数。 该整数将对应于数组中的索引。 这个概念可能看起来像这样： 那么魔术散列函数会是什么样子？ 也许为了生成字符串“ Manny”的哈希值，我们可以获得每个字符的整数表示并将它们加在一起。 因此，“ Manny”的哈希值可能等于515。您可能会意识到，由于交换属性“ Manny”将具有与“ Mynan”相同的哈希值。 进行字符串哈希处理有很多更好的方法，但最终它们都只是将字符串转换为整数。 请注意，键不必是字符串，它们可以是任何具有哈希函数的对象。 在理想情况下，每个键都将具有唯一的哈希值，但实际上这是不可行的。 仅根据字符串大小，可能会有数十亿个排列。 如果我们的字母表中只有小写字母，则五个字符的字符串的排列将为26⁵！ 想一想，如果您的每件衣服都在自己的独特抽屉中，那么您将需要多少个抽屉。 那么，如何将所有可能的键唯一地映射到数组索引？ 我们不！ 碰撞和单独链接 哈希函数的目标是将所有可能的键均匀分布到整数范围内。 通过一点数学，我们可以减少这些整数，以便将它们包含在数组大小内。 这将不可避免地导致我们的某些键解析为相同的索引，但不要担心，有几种方法可以处理冲突。 什么是最好的解决方案，让您只用几个抽屉就能穿衣服？ 如果您回答将成组的衣服放到抽屉里，那么您是正确的。 如果您只是大堆衣服，那么您的早晨一定很O（n）。 在这篇文章中，我选择使用称为“单独链接”的碰撞解决方案。 通过单独的链接，我们仍将使用键的哈希值来获取数组中的索引。 但是，这次我们将在该索引处有一系列键值对。 这使我们可以将可解析为相同索引的键值对放在可搜索链中。 为了简单起见，我们将使用数组来实现这些链（通常使用链表）。 这是“单独链接”的样子： […]