关于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];

咱们比照执行工夫：

形式	执行工夫ms
形式1，批量对象删除	25.33
形式2，批量索引删除	15.33

咱们权且疏忽筛选元素以及筛选索引的工夫，他们不会相差很多（都是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 的性能差别，咱们看一下性能测试后果：

类型	100w元素，100w次索引拜访(ms)	1w元素，1w次查找	100w元素内存占用(MB)
NSArray	38.012	597.029	15.266
NSOrderedSet	33.796	1.006	33.398

能够看出，仅从拜访效率来看，两者差异并不大，而在 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

容器/办法	100万次add	100万次随机拜访
NSMutableArray	0.023	69.9
NSPointerArray + Strong Memory	0.024	60
NSPointerArray + Weak Memory	759	224.4

可见，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...