哈希表寓言

在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）。

在这篇文章中，我选择使用称为“单独链接”的碰撞解决方案。

通过单独的链接，我们仍将使用键的哈希值来获取数组中的索引。 但是，这次我们将在该索引处有一系列键值对。 这使我们可以将可解析为相同索引的键值对放在可搜索链中。 为了简单起见，我们将使用数组来实现这些链（通常使用链表）。

这是“单独链接”的样子：

基本上，我们有一个很大的数组（最好是很小的）。 当我们将键解析为索引时，可以在数组上使用它来获取键值对链。 然后，我们遍历我们的链以实际找到所需的一对。 这就是为什么人们经常说哈希表不是真正的O（1）的原因。 例如，如果出于某种可怕的原因，您所有的键都映射到索引1，我们将只有一条很大的链！ 这意味着我们将回到O（n）访问时间。 这就是为什么使键统一哈希非常重要的原因，如果您有一些自定义哈希函数或独特的数据行为（例如，您的键是呈指数增长的整数），则要牢记这一点。

对我们来说幸运的是，Swift的内置类型很好地实现了哈希，因此我们不必太担心哈希值的分布。 在Swift中，散列发生在Hashable协议所需的hashValue变量中。 这是Swift的字符串“ Manny”的默认hashValue是：

  print（“ Manny” .hashValue）// 4799463752060760361 

最后让我们做这件事！

首先，让我们将键值对放入结构中，以便易于理解：

  struct KeyValuePair  { 
 让钥匙：钥匙 
  var值：值 
  } 

KeyValuePair是通用类型。 这意味着在中，我们描述了它可以容纳的类型。 密钥必须符合Hashable协议，因为稍后我们需要从其获取hashValue 。 另外， Hashable也需要Equatable一致性。 值类型可以是任何值 。

现在，让我们来制作我们的哈希图：

  struct HashMap  { 
  var链：[[KeyValuePair ]] 

 初始化（容量：整数）{ 
 链= [[KeyValuePair]]（重复：[]，计数：容量） 
  } 
  } 

注意事项：

1. 像我们的KeyValuePair结构一样，我们的HashMap是泛型的。
2. 我们的链对象是KeyValuePairs的数组。 因此[[KeyValuePair]]
3. 为简单起见，我们将哈希映射设为静态大小。 这意味着我们将立即初始化所有链。 我们的哈希值必须解析为index < Capacity 。

现在让我们做一些基本的方法。

组

 变异函数集（值：值，forKey键：键）{ 
 让索引= abs（key.hashValue）％chains.count 

 如果让subIndex = chains [index] .index（其中：{$ 0.key == key}）{ 
  //此键已经存在，因此我们将只更新值 
  Chains [index] [subIndex] .value =值 
 返回 
  }其他{ 
  //如果没有预先存在的密钥，我们只需追加一对 
  Chains [index] .append（KeyValuePair（key：key，value：value）） 
  } 
  } 

通过此方法，我们可以为键设置一个值。 最重要的一行是：

 让索引= abs（key.hashValue）％chains.count 

我们的hashValue可以为负，因此我们必须确保它对我们的数组为正。 它也可以是任意大的数字。 使用％运算符，我们将hashValue限制为chains数组的大小。 ％又是什么？ 模运算符（％）计算除法的余数：10％6 =4。这使得我们永远都不会超过数组的大小。 例如，字符串“ Manny”的hashValue为4799463752060760361。如果我们有1000个链，我们将做4799463752060760361％1000。其余为361，这是我们链数组中的索引。

其余代码只是检查链中是否已有键，并更新其值，或者如果还不存在则添加新的键值对。

得到

  func getValue（forKey key：Key）->值？  { 
 让索引= key.hashValue％chains.count 

 让链=链[索引] 
 保护让对= chain.first（其中：{$ 0.key == key}）else { 
 返回零 
  } 

 返回pair.value 
  } 

与之前类似，我们使用hashValue和％运算符将密钥范围缩小到特定链。 然后，我们在链中搜索键值对，如果存在，则返回该值。

删除

最后，我们应该能够删除密钥：

 变异func delete（key：Key）{ 
 让索引= key.hashValue％chains.count 

 代表subIndex in 0 .. <chains [index] .count { 
 如果Chains [index] [subIndex] .key ==键{ 
  Chains [index] .remove（at：subIndex） 
  //只有一把钥匙，所以我们现在可以返回 
 返回 
  } 
  } 
  } 

让我们测试一下！

  var myHashMap = HashMap （容量：100） 

  assert（myHashMap.getValue（forKey：“ Manny”）== nil） 

  myHashMap.set（值：30，forKey：“ Manny”） 
  assert（myHashMap.getValue（forKey：“ Manny”）== 30） 

  myHashMap.set（值：32，forKey：“ Kenz”） 
  assert（myHashMap.getValue（forKey：“ Manny”）== 30） 
  assert（myHashMap.getValue（forKey：“ Kenz”）== 32） 

  myHashMap.set（值：31，forKey：“ Manny”） 
  assert（myHashMap.getValue（forKey：“ Manny”）== 31） 

  myHashMap.delete（键：“ Manny”） 
  assert（myHashMap.getValue（forKey：“ Manny”）== nil） 
  assert（myHashMap.getValue（forKey：“ Kenz”）== 32） 

其作品！

统计资料

我认为将一堆随机字符串放在一个小的哈希图中并分析数据以查看冲突的分布情况会很有趣。

在以下代码中，我创建了一个容量为1k的HashMap，并用10k个随机字符串填充了它：

  func randomString（length：Int）->字符串{ 
  let chars =“ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789” 

 让allowCharsCount = UInt32（chars.count） 
  var randomString =“” 

  for _ in 0 .. <length { 
 让rand = Int（arc4random_uniform（allowedCharsCount）） 
 让索引= chars.index（chars.startIndex，offsetBy：rand） 
 让newCharacter = chars [index] 
  randomString + =字符串（newCharacter） 
  } 

 返回randomString 
  } 

  var testHashMap = HashMap （容量：1000） 

  for _ in 0 .. <10000 { 
 让字符串= randomString（长度：6） 
  testHashMap.set（值：（），forKey：字符串） 
  } 

 用于testHashMap.chains { 
 打印（chain.count） 
  } 

这是所有链数的图表：

该图从本质上表示每条链碰撞的频率。 它是一个美丽，均匀分布的频率图。 现在我们知道，在这种特定情况下，不必筛选10,000个键值对来找到我们的键，我们只需要映射到索引并搜索21个值的最坏情况。 这好得多了，为什么哈希表很棒。 应该注意的是，更大的数组将具有较少的冲突，但会占用更多的内存，反之亦然。

我还使用此处的流行名称列表进行了相同的分析，只是为了确保这不是我分配值的随机字符串代码。 结果相似：

这次最大的冲突计数较低，因为我使用的字符串数是4275，而不是10k。

菲尼托

我希望这是一个易于理解的哈希表分解。

  salutationsTable.getValue（forKey：“ Manny”）==“干杯！”