iOS 2018系列：破解iOS采访或成为iOS专家（8）

快速的泛型和LRU缓存

我们将通过此博客学习Swift和LRU算法中的泛型。 当您的面试官要求您在纸上编写通用LRU缓存的代码时，对于iOS开发人员来说，这是第3轮或第4轮的热门问题，根据面试官的知识，实现语言可能会有所不同……哈哈哈！ 希望你有一个好的面试官🙂

通用 代码使您可以编写灵活，可重用的函数和类型，这些函数和类型可根据您定义的要求与任何类型一起使用。

泛型函数 

  func swapTwoValues （_ a：inout T，_ b：inout T）{ 
 令tempA = a 
  a = b 
  b =温度 
  }

该函数的通用版本使用占位符类型名称（在这种情况下称为T ），而不是实际的类型名称（例如Int ， String或Double ）。 占位符类型名称并没有说明T必须是什么，但它确实说a和b必须具有相同的T类型，无论T代表什么。 每次swapTwoValues(_:_:)函数时， swapTwoValues(_:_:)确定要代替T使用的实际类型。

泛型函数和非泛型函数之间的另一个区别是，泛型函数的名称（ swapTwoValues(_:_:) ）后跟尖括号（ ）中的占位符类型名称（ T ）。 方括号告诉Swift， T是swapTwoValues(_:_:)函数定义中的占位符类型名称。 因为T是一个占位符，所以Swift不会查找名为T的实际类型。

在大多数情况下，类型参数具有描述性名称，例如Dictionary Key和Value和Array ，它向读者介绍类型参数与其所使用的泛型类型或函数之间的关系。但是，当它们之间没有有意义的关系时，通常使用单个字母（例如T ， U和V来命名它们，例如下面的class中的T

除了编写有关泛型的理论外，我们不妨看一下用例，但对于那些需要更多详细信息的人，请参考本文下面给出的链接。

为什么我们需要LRU Cache，甚至是通用的。为什么？

让我们考虑一下它在我们的应用程序中的使用。

  1. 显示基于用户使用情况的列表。
  2. 基于用户使用情况的功能顺序。
  3. 应用程序设置选项基于它的频繁使用。
  4. 根据用户的应用使用情况在Android手机上创建触摸biz屏幕。
  5. 在列表视图中显示大量图像
  6. 将大文本内容加载到内存中

这么多用例..对！！！

让我们从实现通用LRU缓存开始，它将采用不同类型的key，value对并​​存储在其中。 泛型函数可以使用任何类型。

我们使用两种数据结构来实现LRU缓存。

  1. 使用通用双链表实现的队列 。 队列的最大大小将等于可用帧的总数（缓存大小）。最近使用的页面将在前端附近，最少的页面将在后端附近。
  2. 以泛型为键且相应队列节点的地址为值的哈希 。

创建一个LRUNode类，它将成为双链表类的节点。 我们将存储通用类型的键，值信息，init方法将有助于初始化类。 

 类LRUNode  
  { 
  var键：K 
  var值：V 
  var next：LRUNode？ 
  var prev：LRUNode？ 
 初始化（键：K，值：V） 
  { 
  self.key =键 
  self.value =值 
  self.next =无 
  self.prev =零 
  } 
  }

我们将实现一个双向链接列表，该列表将帮助我们维护最近最少使用的信息项，最近使用的项将位于双向链接列表的headNode上 ，而最少使用的项将位于其tailNode上。

为此，我们将实现一个名为DLinkList的类，它将具有两个功能。

  1. addToHead它将把我们的节点作为输入并将其添加到headNode 。
  2. removeNode将以我们的节点为输入，并根据其删除逻辑检查其headNode ， tailNode或inbetween节点是否有效。 
 类DLinkList  
  { 
  var headNode：LRUNode ？ 
  var tailNode：LRUNode ？ 
 在里面 （） 
  { 
  } 
  func addToHead（节点：LRUNode ） 
  { 
 如果self.headNode！  =无{ 
  //在临时存储中获取头节点 
 让tNode = self.headNode 
  //分配tNode的前一个，以便我们可以在开始时插入节点 
  tNode？.prev =节点 
  self.headNode =节点 
  self.headNode？.next = tNode 
  } 
 其他{ 
  self.headNode =节点 
  self.tailNode =节点 
  } 
  } 
  func removeNode（node：LRUNode ） 
  { 
  // ===用于节点之间的比较 
 如果self.headNode！  =零&& self.headNode！  = = =节点{ 
 如果self.headNode？.next = = nil { 
  self.headNode =零 
  self.tailNode =零 
  } 
 其他{ 
  self.headNode = self.headNode？.next 
  self.headNode？.prev =无 
  } 
  } 
 否则为node.next！  =无{ 
  //节点不在起点或终点 
  node.next?.prev = node.prev 
  node.prev？.next = node.next 
  } 
 其他{ 
  //如果节点在尾部位置 
  node.prev？.next =无 
  self.tailNode = node.prev 
  } 
  } 
  }

Swift提供了两个标识运算符（===和！==），您可以使用它们来测试两个对象引用是否都引用同一对象实例。

这样我们就可以使用双链表了。

让我们创建一个哈希映射，以便更快地访问LRU。 在实现通用哈希图时，我们需要注意密钥是否应为可哈希的，并且是否需要遵循NSCopying协议的值。

LRUCache类将具有一个队列，该队列表示一个双链表，提供addToHead，removeNode功能，hashTable字典，其中包含通用密钥和LRUNode作为值。 多线程访问已通过使用dispatchQueue和barrier标志来处理。 

  LRUCache类 
  { 
 无功容量 ：整数 
  var length ：整数 
 专用让队列 ： DLinkList  
 专用var hashTable ： [K：LRUNode ] 
  private let dispatchQueue ： DispatchQueue = DispatchQueue.init（标签：“ CacheQueue”） 
  初始化（大小：整数） 
  { 
  self.capacity =大小self.length = 0 self.queue = DLinkList.init（） 
  hashTable = [K：LRUNode ] 
  （最小容量：大小） 
  } 下标（键：K）-> V？  { 
  //从原来的位置移开，并确保它在双链表中移到最前面 

  得到 { 
  var node：LRUNode ？ 
  dispatchQueue.sync { 
 节点= hashTable [键] 
 如果节点！  =无{ 
  self.queue.removeNode（节点：节点！） 
  self.queue.addToHead（节点：节点！） 
  } 
  } 
 如果node = = nil { 
 返回零 
  } 
 返回节点！。值 
  } 
  设置 （newValue） 
  { 
  dispatchQueue.async（标志：.barrier） 
  { 
 如果newValue = = nil { 
 返回 
  } 
 如果让node = self.hashTable [key] 
  { 
  node.value = newValue！ 
  self.queue.removeNode（节点：节点） 
  self.queue.addToHead（node：节点） 
  } 
 否则{self.hashTable.removeValue（forKey：self.queue.tailNode！.key） 
  self.queue.tailNode = self.queue.tailNode？.prev 
 如果让node = self.queue.tailNode { 
  node.next =无 
  } 
  self.queue.addToHead（node：节点） 
  self.hashTable [key] =节点 
  } 
  } 
  } 
  } 
  }

此实现有助于理解swift和LRU算法实现中的泛型概念。

使用LRU缓存 

 让lruCache = LRUCache （大小：7）lruCache [“印度”] = 150000000

有关泛型的更多详细信息，请单击此处： 快速泛型

Swift 4中的 private ， public ， internal ， open 和 fileprivate 访问级别有 什么区别 ？

在Swift中，封装是通过使用以下五个访问控制关键字来实现的： private ， fileprivate ， internal ， public和open 。 这些访问级别在文件或模块范围内限制或打开访问。 让我们看一下它们中的每一个，从限制性最高的， private到限制性最低的open 。

Private是最严格的。 如果您将某些内容定义为private则意味着它对该声明范围是私有的，并且不能从外部访问。

Fileprivate访问是第二限制的。 将某些内容定义为fileprivate意味着只能在声明它的文件范围内访问它。

Internal访问权限是默认访问级别，如果您没有明确说明，则将设置该级别。 Internal意味着该事物可以在其定义的模块内的任何地方使用。 基本上，如果您正在构建应用程序，则internal意味着它可以在该应用程序中的任何位置使用。 如果您要构建库/框架，则internal意味着它可以在该库/框架内使用，但不能在使用该库的应用程序之外使用。

Public访问意味着不仅可以在定义文件和模块中访问某些内容，而且还可以从将定义内容导入到其中的外部模块进行访问。 实际上， public声明了该模块的公共接口。

Open访问意味着某些东西是public并且不仅可以在定义它的模块内进行子类化，还可以由导入它的任何人进行子类化。

希望您喜欢本文并对希望了解泛型的使用和泛型LRU Cache的实现的人们有所帮助，请❤️将这篇文章推荐给其他人😊。 让我知道您的反馈。 🙂

下一章： 快速枚举，免费电话桥接和必须了解iOS基础知识

Interesting Posts