使用Swift了解哈希表，字典和集合

---

在帮助iOS开发人员准备技术面试时，我经常讨论哈希表。 由于效率高，哈希表是候选人在应对编码挑战以及实际应用程序时应考虑的出色工具。 在本文中，我们将探讨哈希表的概念，并将其与其他集合类型（例如字典和集合）进行比较。

词典

要了解为什么哈希表很有用，应该熟悉它们的设计。 当被问到时，许多学生都认为“哈希表就是字典”。为验证这一点，让我们回顾一下标准的Swift字典类型：

 变种  清单=  字典   （）//添加字典值-恒定时间O（1） 
  list [“ WB”] =“ Wayne Bishop” 
  list [“ FB”] =“弗兰克·霍布斯” 
  list [“ LP”] =“拉里·佩奇（Larry Page） 
  list [“ AE”] =“阿尔伯特·爱因斯坦” //检索密钥 
 对于   s在list.keys { 
 打印   （秒） 
  } //获取值 
 对于   v在list.values { 
 打印   （v） 
  } //通过键获取值-恒定时间O（1） 
 让   item = list [“ WB”] //收回“ Wayne Bishop” 

词典是处理许多情况的有用类型。 由于键和值都是在运行时提供的，因此可以编写例程来检索单个键，值或它们的混合。 而且，由于每个提供的值都与一个键相关联，因此还可以在O（1）恒定时间内执行必要的数据插入，查找和检索。

哈希表

哈希表与字典关系密切，但在两个方面有所不同。 哈希表还支持键值对，但是它们的键是通过使用称为哈希算法的附加功能以编程方式生成的。 由于哈希表键是在运行时创建的（并且不会更改），因此它们通常不与数据结构一起存储。 这些功能使哈希表可以在O（1）中执行-恒定时间，同时占用最小空间。 考虑一下本书中的以下自定义实现：

 让  列表= 哈希表 <  串   >（容量：4）//添加哈希表项-恒定时间O（1） 
  = list.insert（“韦恩主教”） 
  = list.insert（“弗兰克·史密斯”） 
  = list.insert（“珍妮弗·霍布斯”） 
  = list.insert（“蒂姆·库克”）//评估测试-恒定时间O（1） 
 如果  清单。  包含   （“蒂姆·库克”）{ 
 打印   （“找到用户！”） 
  } 

如果您有机会使用其他语言（例如Java）编程，您将熟悉HashTable或HashMap类型。 在iOS开发中，没有官方对应的HashTable类型。 但是，取而代之的是我们拥有流行的Hashable协议。 这个想法是，可以扩展任何类型来支持类似哈希表的功能。 考虑以下用于创建区块链算法的组件：

  //自定义类型（用于图形编程） 
 公开课  顶点   { 

  var键：  串   ？ 
  var邻居：  数组    
  var访问过：  布尔   =错误 

 在里面（） { 
 自我邻居=  数组   （） 
  } 
  } 

  ... 

  // Hashable的类型一致性 
  扩展 顶点：可 哈希 { 

  public var hashValue： Int { 

  var余数：  整数   = 0 
  var除数：  整数   = 0 

  //测试提早退出 
 守护  让标量= self.key?。   unicodeScalars  其他{ 
 返回0 
  } 

 对于  标量项目{ 
 除数+ = Int（item.value） 
  } 

 余数=除数％10 

 返回余数 
  } 

  // note：继承的Equatable协议的要求 
  公共静态 函数 ==（lhs： Vertex ，rhs： Vertex ）-> Bool { 
  返回 lhs.key == rhs.key 
  } 
 
  } 

作为一种协议， Hashable确保所有符合类型的索引均使用唯一的数值正确索引。 在此模型下，所需的hashValue计算属性用作哈希算法。 当使用标准Swift集合类型（如Sets）时，我们还可以看到此功能的实际作用：

 变种  项目=  组   （）//注意：Swift字符串符合Hashable 

  //添加设置项-恒定时间O（1） 
  items.insert（“韦恩主教”） 
  items.insert（“弗兰克·霍布斯”） 
  items.insert（“拉里·佩奇”） 
  items.insert（“艾伯特·爱因斯坦”） 

  //获取第一个设置项的哈希索引 
 如果让   itemvalue = items.first？.hashValue { 
 打印   （itemvalue）//打印-312247953819291399 
  } 

由于本机Swift String类型已经符合Hashable，因此它支持hashValue计算属性的内置遵从性。 最后，寻求更大灵活性的iOS开发人员可以完全避开Hashable模型，以创建独特的实现。 知道如何编写简单的哈希算法在技术面试中特别有用。 考虑以下从书中摘录的设计。 此方法通过使用协议扩展来应用面向协议的技术：

 协议  可键控   { 

 变种  关键字：  串   {得到} 

  //注意：在这种情况下，hashValue作为函数运行 
  func hashValue （用于键：  串   ！，使用存储桶：  数组   ）->  整数 
  } 

 延期  可键控   { 

  //计算项目哈希 
  func hashValue （对于密钥：  串   ！，使用存储桶：  数组   ）->  整数   { 

  var余数：  整数   = 0 
  var除数：  整数   = 0 

  //平凡的情况 
 守护  键！=无  其他   { 
 返回-1 
  } 

 对于  键中的项目。   unicodeScalars   { 
 除数+ =  整数   （item.value） 
  } 

 剩余=除数％桶。  计数 
 返回  余 
  } 
  } 

---

喜欢这篇文章吗？ 阅读并发现有关 Medium的 Swift算法书 。