关于iOS开发:技术干货-iOS-高阶容器详解

近期，在面试 iOS 工程师的过程中，当我问到候选人小伙伴都理解哪些 iOS 容器类型时，大多数小伙伴能给出的回答就是 NSArray、NSDictionary 和 NSSet 以及对应的可变类型，有些优良的小伙伴可能说出 NSCache，还能对它的原理娓娓而谈，这是十分棒的。然而总体而言，高阶容器的遍及在技术同学中还是比拟少。本文，咱们就来具体聊聊咱们对 iOS 高阶容器类型的深入研究后果，并探讨其应用场景。

在进行具体分析之前，咱们先简略理解一下 iOS 的容器有哪些。iOS 提供了三种次要的容器类型，它们别离是 Array、Set 和 Dictionary，用来存储一组值：

• Array：存储一组有序的值
• Set：存储一组无序的、不反复的值
• Dictionary：存储一组无序的键 - 值映射

这些都是咱们平时用到的根底容器。除此之外，iOS 提供了很多高阶容器类型，他们别离是：

• NSCountedSet
• NSIndexSet && NSMutableIndexSet
• NSOrderedSet && NSMutableOrderedSet
• NSPointerArray
• NSMapTable
• NSHashTable
• NSCache

明天，咱们将对这些高阶容器进行具体介绍。

NSCountedSet

NSCountedSet 是与 NSMutableSet 用法相似的无序汇合，能够增加、移除元素，判断元素是否存在及保障元素唯一性。不同的是：

• 一个元素能够增加屡次
• 能够获取元素的数量

构想咱们要做一个 淘宝购物车 的性能，购物车中统计每一个商品的数量，还能够对数量进行减少和缩小。依照常规，传统的做法是应用字典：

@property (nonatomic, strong) NSMutableDictinary *itemCountDic;

获取数量：

NSNumber *num = [self.itemCountDic objectForKey:item]; 
if (num == nil) {return 0;} 
return num.integerValue;

数量 +1：

NSNumber *num = [self.itemCountDic objectForKey:item]; 
if (num == nil) {[self.itemCountDic setObject:@1 forKey:item];     
} else {[self.itemCountDic setObject:@(num.integerValue+1) forKey:item]; 
}

数量 -1：

NSNumber *num = [self.itemCountDic objectForKey:item]; 
if (num == nil) {return;}  
if (nums.integerValue == 1) {[self.itemCountDic removeObjectForKey:item]; 
} else {[self.itemCountDic setObject:@(num.integerValue-1) forKey:item]; 
}

这种形式没有问题，然而有了 NSCountedSet，所有的操作一行代码就能搞定：

@property (nonatomic, strong) NSCountedSet<CartItem *> itemCountSet;

获取数量：

[self.itemCountSet countForObject:item];

数量 +1：

[self.itemCountSet addObject:item];

数量 -1:

[self.itemCountSet removeObject:item];

能够看出，NSCountedSet 就是为这种场景量身定做的。

NSIndexSet && NSMutableIndexSet

NSIndexSet && NSMutableIndexSet 是蕴含不反复整数的容器类型，使得索引拜访具备批量执行的能力。比方咱们须要获取数组的第 0，第 2，第 4 个元素组成的子数组：

NSMutableIndexSet *indexes = [[NSMutableIndexSet alloc] init]; 
[indexes addIndex:0]; 
[indexes addIndex:2]; 
[indexes addIndex:4]; 
NSArray *newArray = [oldArray objectAtIndexes:indexes];

这样一看，如同并没有节俭多少代码量！别急，咱们再看上面的例子：在一个长度 100 的数组中，获取区间 5 -8、11-13、19-22、55-99 四个区间的元素。

NSMutableIndexSet *indexes = [[NSMutableIndexSet alloc] init];
[indexes addIndexesInRange:NSMakeRange(5, 4)]; // 5，6，7，8 
[indexes addIndexesInRange:NSMakeRange(11, 3)]; // 11，12，13 
[indexes addIndexesInRange:NSMakeRange(19, 4)]; // 19，20，21，22 
[indexes addIndexesInRange:NSMakeRange(55, 45)]; // 55，56，57，58.....99 
NSArray *newArray = [oldArray objectAtIndexes:indexes];

接下来咱们做一下性能测量，从一个长度 10 万的随机字串中，删除所有 a 结尾的字符串。

形式 1，批量对象 删除：

首先筛选元素：

NSArray *subarrayToRemove = [array filteredArrayUsingPredicate:[NSPredicate                                           predicateWithBlock:^BOOL(id _Nullable evaluatedObject, NSDictionary<NSString *,id> * _Nullable bindings) {return [evaluatedObject hasPrefix:@"a"]; 
}]];

执行删除：

[array removeObjectsInArray:subarrayToRemove];

形式 2，批量索引 删除：

首先筛选索引集：

NSIndexSet *indexesToRemove = [array indexesOfObjectsPassingTest: 
    ^BOOL(id  _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {return [obj hasPrefix:@"a"];     
}];

执行删除：

[array removeObjectsAtIndexes:indexesToRemove];

咱们比照执行工夫：

咱们权且疏忽筛选元素以及筛选索引的工夫，他们不会相差很多（都是 O(n)）。起初试验证实后者效率更佳。

分析：形式 1 比形式 2 多了一个步骤，即遍历每一个元素以取得他们的索引值。如果待删除子集的长度是 k，这个多进去的步骤的工夫复杂度是是 O(n * k)。随着 n 和 k 的减少，执行工夫的差距将会更加显著。

NSOrderedSet && NSMutableOrderedSet

NSOrderedSet && NSMutableOrderedSet 是有序 Set，比 传统 NSSet 减少了索引性能，且可能放弃元素的插入程序。

索引示例：

NSString *o1 = @"3"; 
NSString *o2 = @"2"; 
NSString *o3 = @"1"; 
NSOrderedSet *orderedSet = [NSOrderedSet 
                                orderedSetWithObjects:o1, o2, o3, nil]; 
[orderedSet indexOfObject:o2]; // 1 
[orderedSet indexOfObject:o3]; // 2 
[orderedSet objectAtIndex:0];  // o1

令人惊喜的是，NSOrderedSet && NSMutableOrderedSet 反对 subscript：

orderedSet[1];  // o2

判断汇合蕴含关系：

[a isSubsetOfSet:b]; // a 是否为 b 的子集。b 为 NSSet。[a isSubsetOfOrderedSet:b]; // a 是否为 b 的子集。b 为 NSOrderedSet。

判断汇合相交关系：

[a intersectsSet:b]; // a 是否与 b 有交加。b 为 NSSet 
[a intersectsOrderedSet:b];  // a 是否与 b 有交加。b 为 NSOrderedSet

为了摸索 NSOrderedSet 与 NSArray 的性能差别，咱们看一下性能测试后果：

能够看出，仅从拜访效率来看，两者差异并不大，而在 1w 次查找的比照中，NSOrderedSet 居然快出 590 倍之多！内存代价尽管比拟低廉，但在可承受的范畴之内。

NSPointerArray

NSPointerArray 是 NSMutableArray 的高阶类型，比 NSMutableArray 具备更宽泛的内存治理能力，具体如下：

• 和传统 NSArray 一样，用于有序的插入或移除；
• 与传统 NSArray 不同的是，能够存储 NULL，且 NULL 参加 count 的计算；
• 与传统 NSArray 不同的是，count 能够被设置，如果设置较大的 count 则应用 NULL 占位；
• 能够应用 weak 或 unsafe_unretained 来润饰成员；
• 能够批改对象的判等形式；
• 能够使对象退出时进行拷贝；
• 成员能够是所有指针类型，不仅限于 OC 对象；

咱们能够举个简略的例子看一下，例如它能够存储 weak 援用：

NSPointerArray *pointerArray = NSPointerArray.weakObjectsPointerArray; 
[pointerArray addPointer:(void *)obj]; // obj 的援用计数不会减少

注：obj 被开释后，pointerArray.count 仍然是 1，这是因为 NULL 也会参加占位。调用 compact 办法将清空所有的 NULL 占位。

咱们能够通过函数 + pointerArrayWithOptions: 指定更多乏味的存储形式。下面的 NSPointerArray.weakObjectsPointerArray 实际上是 [NSPointerArray pointerArrayWithOptions:NSPointerFunctionsWeakMemory] 的简化版。

NSPointerFunctionsOptions 是一个选项，不同于枚举，选项类型是能够叠加的。这些选项能够分为内存治理、共性断定、拷贝偏好三大类：

内存治理相干

• NSPointerFunctionsWeakMemory：弱援用，不减少援用计数。元素被开释后变成 NULL，但 count 放弃不变。调用 compact 办法后将删除所有 NULL 元素并从新调整大小。对应 ARC 的 weak。
• NSPointerFunctionsStrongMemory：强援用，援用计数 +1。对应 ARC 的 strong。
• NSPointerFunctionsOpaqueMemory：不减少援用计数，也不创立弱援用，元素开释后变野指针。对应 ARC 的 unsafe_unretained。
• NSPointerFunctionsMallocMemory：移除元素时调用 free() 进行开释，增加时调用 calloc()。不同于下面三种，这种形式实用于元素为一般指针类型的状况。
• NSPointerFunctionsMachVirtualMemory：用于 Mach 的虚拟内存治理。

共性断定相干

什么是共性断定呢？共性断定蕴含以下三个方面：

• 相等性断定（即判等）。传统容器都是应用元素的 -isEqual 进行相等性断定。当对 NSArray 调用 indexOfObject 办法时，数组会遍历外部元素，对每个遍历到的元素与输出元素进行 isEqual 比照，直到碰到第一个断定胜利（即 isEqual 返回 YES）的元素并返回其索引；若所有元素均断定失败则返回 NSNotFound。
• 哈希值断定。如应用对象的 Hash 办法是一种哈希值断定形式。常见的 NSSet、NSDictionary 都是应用元素的 Hash 办法获取哈希值，从而决定其索引地位。
• 形容值断定。如应用对象的 Description 办法是一种形容值断定形式。对数组进行打印时，打印的内容中蕴含了所有对象的 Description 值。

咱们来看下共性断定相干的 NSPointerFunctionsOptions 有哪些：

• NSPointerFunctionsObjectPersonality：断定元素为 OC 对象。用元素的 isEqual 办法判等，Hash 办法计算哈希值，Description 办法做形容（NSLog 打印）。
• NSPointerFunctionsObjectPointerPersonality：断定元素为对象指针。通过比照指针来判等，通过指针左移计算哈希值，用 Description 办法对其形容。
• NSPointerFunctionsCStringPersonality：断定元素为 CString。应用 strcmp 判等，对该字符串求哈希，用 UTF8 编码格局对其形容。
• NSPointerFunctionsIntegerPersonality：断定元素为整型值。应用整型值的右移后果作哈希值和判等条件。
• NSPointerFunctionsStructPersonality:：断定元素为构造体指针。用 memcmp 比照内存判等，对理论内存求哈希。
• NSPointerFunctionsOpaquePersonality：不确定类型。通过比照指针来判等，通过指针左移计算哈希值。

拷贝偏好

NSPointerFunctionsCopyIn：增加元素时，理论增加的是元素的拷贝。

接下来咱们比照一组数据，单位 ms

可见，NSMutableArray 与 NSPointerArray+ strong 简直没有差异，而 NSPointerArray + Weak 的性能开销就不那么乐观了。

那咱们怎么了解传统数组与 NSPointerArray 的关系呢？传统数组就相当于一个非凡的 NSPointerArray，把它的 options 设成这样：

NSPointerFunctionsStrongMemory | NSPointerFunctionsObjectPersonality

即共性断定为 OC 对象，强援用，不进行拷贝。

NSMapTable

NSMapTable 为 NSMutableDictionary 的高阶类型。它与 NSPointerArray 相似，能够指定 NSPointerFunctionsOptions，不同的是 NSMapTable 的 key 和 value 都能够指定 options：

[NSMapTable mapTableWithKeyOptions:keyOptions valueOptions:valueOptions]

更便捷的初始化办法：

NSMapTable.strongToStrongObjectsMapTable // key 为 strong，value 为 strong NSMapTable.weakToStrongObjectsMapTable // key 为 weak，value 为 strong NSMapTable.strongToWeakObjectsMapTable // key 为 strong，value 为 weak NSMapTable.weakToWeakObjectsMapTable; // key 为 weak，value 为 weak

保留传统字典的经典能力：

[table setObject:obj forKey:key]; // 设置 Key,Value 
[table objectForKey:key] // 依据 Key 获取 Value 
[table removeObjectForKey:] // 删除

不同的是，零碎并没有给它 subscript 反对，即不能应用相似 dict[key] = value 的中括号语法。

那咱们怎么了解传统字典与 NSMapTable 的关系呢？传统字典就相当于一个非凡的 NSMapTable，把它的 keyOptions 设成这样：

NSPointerFunctionsStrongMemory  | 
NSPointerFunctionsObjectPersonality|
NSPointerFunctionsCopyIn；

须要留神的是 NSPointerFunctionsCopyIn, 老字典会对 key 进行 copy，value 不会。然而如果大家素日里都应用 NSString 作为 key，那大可不必思考 copy 的性能损耗（因为只是浅拷贝）。但如果应用的是 NSMutableString 或者一些进行深拷贝的类型，那就另当别论了。

再把它的 valueOptions 设成这样：

NSPointerFunctionsStrongMemory | NSPointerFunctionsObjectPersonality

即 key 为强援用、共性断定为 OC 对象、增加元素时进行拷贝；value 为强援用，共性断定为 OC 对象，但不进行拷贝。

NSMapTable 与老字典的性能不能一概而论，因为他们的次要性能差异也是来自于 NSPointerFunctionsCopyIn 与 NSPointerFunctionsWeakMemory。后者会带来肯定的性能损耗，而前者要看 key 的 NSCopying 协定是如何实现的。

NSHashTable

NSHashTable 是 NSMutableSet 的高阶类型，与 NSPointerArray、NSMapTable 一样，能够指定 NSPointerFunctionsOptions：

[NSHashTable hashTableWithOptions:options]

便捷的初始化办法：

NSHashTable.weakObjectsHashTable // weak set 
NSHashTable.strongObjectsHashTable // strong set

保留传统 Set 的经典能力：

[table addObject:obj] // 增加 obj，去重 
[table removeObject:obj] // 移除 obj 
[table containsObject:obj] // 是否蕴含 obj 
[table intersectsHashTable:anotherTable] // 是否与 anotherTable 有交加 
[table isSubsetOfHashTable:anotherTable] // 是否是 anotherTable 的子集

同样，如果用 NSHashTable 示意传统字典，传统字典应该是这样的 NSHashTable：

NSPointerFunctionsStrongMemory | NSPointerFunctionsObjectPersonality

NSCache

NSCache 是 Foundation 框架提供的缓存类的实现，应用形式相似于可变字典，因为 NSMutableDictionary 的存在，很多人在实现缓存时都会应用可变字典，但这样是具备很多局限性的。咱们能够从 3 个方面理分明它与 NSMutableDictionary 的区别：

• NSCache 集成了多种缓存淘汰策略（尽管官网文档没有明确指出，但从测试后果来看是 LRU 即 Lease Recent Usage)，且产生内存正告时会进行清理）, 保障了 cache 不会占用过多的内存资源。
• NSCache 是线程平安的。能够从不同的线程中对 NSCache 进行增删改查操作，而不须要本人对 cache 加锁。
• 与 NSMutableDictionary 不同, NSCache 不会对 key 进行拷贝。

上面简略介绍一下 LRU（双链表 + 散列表）的外围逻辑。

LRU 缓存淘汰策略外围逻辑

• 与老字典不同，散列表的 value 变成通过封装的节点 Node，蕴含：

  • key: 即字典的 key
  • value：即字典的 value
  • prev：上一个节点
  • next: 下一个节点
• 插入散列表的节点将移到链表头部，工夫复杂度为 O(1)
• 被拜访的或更新的节点将挪动到链表头部，工夫复杂度为 O(1)
• 当容量超限时，链表尾部的节点将被移除（工夫复杂度为 O(1)），同时从散列表中移除

咱们看到，链表的各项操作并没有影响散列表的整体工夫复杂度。

开始应用

首先，初始化容量为 5 的 cache：

self.cache = [[NSCache alloc] init];
self.cache.totalCostLimit = 5;
self.cache.delegate = self;

实现 NSCacheDelegate，元素被淘汰时会收到回调：

- (void)cache:(NSCache *)cache willEvictObject:(id)obj {NSLog(@"%@", [NSString stringWithFormat:@"%@ will be evict",obj]);
}

接下来别离插入 5 个元素：

for (int i = 0; i < 5; i++) {[self.cache setObject:@(i) forKey:@(i) cost:1]; 
 }

元素依照 1、2、3、4、5 的程序插入的，意味着下一个被淘汰的元素是 1。

接下来咱们试着拜访 1，而后插入 6：

NSNumber *num = [self.cache objectForKey:@(1)];
[self.cache setObject:@6 forKey:@6 cost:1];

后果打印：

2020-07-31 09:30:56.486382+0800 Test_Example[52839:214698] 2 will be evict

起因是 1 被拜访后被置换成了链表的 head，此时 tail 变成了 2。再次插入新数据后，tail 元素 2 被淘汰。

总结

近不修，无以行远路; 低不修，无以登平地。若要成为最煊赫一时的技术人才，打下扎实的地基是必不可少的。面对现在挪动端人才市场的饱和，小伙伴们更应该抓住机会，磨砺本人，在行业中一直成长和提高，最终成为行业内不可或缺的精英人才。

咱们同样也在期待气味相投的小伙伴退出，欢送投递咱们：https://hr.163.com/job-detail.html?id=27614&lang=zh

优良且富裕抱负的你，还在等什么呢？

作者简介

丁文超，网易云信资深 iOS 工程师，负责云信 IM、解决方案的设计和研发工作。Github: WenchaoD

流动收费报名中

4 月 10 日，娱乐社交技术沙龙，邀请来自快手、网易云音乐、Bilibili、网易音视频实验室的技术大咖们，从音视频创作、音视频技术、直播多样化、互动视频多样化等方向，为大家分享泛娱乐利用在音视频上的技术实际，深入探讨音视频技术如何赋能业务，以满足用户多样化需要。

点击链接即可报名：https://segmentfault.com/e/11…