技术干货 | 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；
复制代码

技术干货 | iOS 高阶容器详解

正文