導(dǎo)讀：近期，在面試 iOS 工程師的過(guò)程中，當(dāng)我問(wèn)到候選人小伙伴都了解哪些 iOS 容器類(lèi)型時(shí)，大多數(shù)小伙伴能給出的答復(fù)就是NSArray、NSDictionary 和 NSSet以及對(duì)應(yīng)的可變類(lèi)型，有些優(yōu)秀的小伙伴能夠說(shuō)出 NSCache，還能對(duì)它的原理侃侃而談，這是非常棒的。但是總體而言，高階容器的普及在技術(shù)同學(xué)中還是比較少。本文，我們就來(lái)詳細(xì)聊聊我們對(duì) iOS 高階容器類(lèi)型的深入研究結(jié)果，并討論其使用場(chǎng)景。

文｜丁文超

網(wǎng)易云信資深 iOS 工程師

在進(jìn)行具體分析之前，我們先簡(jiǎn)單了解一下 iOS 的容器有哪些。iOS 提供了三種主要的容器類(lèi)型，它們分別是 Array、Set 和 Dictionary，用來(lái)存儲(chǔ)一組值：

• Array：存儲(chǔ)一組有序的值

• Set：存儲(chǔ)一組無(wú)序的、不重復(fù)的值

• Dictionary：存儲(chǔ)一組無(wú)序的鍵-值映射

這些都是我們平時(shí)用到的基礎(chǔ)容器。除此之外，iOS 提供了很多高階容器類(lèi)型，他們分別是：

• NSCountedSet

• NSIndexSet && NSMutableIndexSet

• NSOrderedSet && NSMutableOrderedSet

• NSPointerArray

• NSMapTable

• NSHashTable

• NSCache

今天，我們將對(duì)這些高階容器進(jìn)行詳細(xì)介紹。

NSCountedSet

NSCountedSet 是與 NSMutableSet 用法類(lèi)似的無(wú)序集合，可以添加、移除元素，判斷元素是否存在及保證元素唯一性。不同的是：

• 一個(gè)元素可以添加多次

• 可以獲取元素的數(shù)量

設(shè)想我們要做一個(gè)淘寶購(gòu)物車(chē)的功能，購(gòu)物車(chē)中統(tǒng)計(jì)每一個(gè)商品的數(shù)量，還可以對(duì)數(shù)量進(jìn)行增加和減少。按照慣例，傳統(tǒng)的做法是使用字典：

@property (nonatomic, strong) NSMutableDictinary *itemCountDic;

獲取數(shù)量：

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

數(shù)量+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]; }

數(shù)量-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]; }

這種方式?jīng)]有問(wèn)題，但是有了 NSCountedSet，所有的操作一行代碼就能搞定：

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

獲取數(shù)量：

[self.itemCountSet countForObject:item];

數(shù)量+1：

[self.itemCountSet addObject:item];

數(shù)量-1：

[self.itemCountSet removeObject:item];

可以看出，NSCountedSet 就是為這種場(chǎng)景量身定做的。

NSIndexSet && NSMutableIndexSet

NSIndexSet && NSMutableIndexSet是包含不重復(fù)整數(shù)的容器類(lèi)型，使得索引訪(fǎng)問(wèn)具備批量執(zhí)行的能力。比如我們需要獲取數(shù)組的第0，第2，第4個(gè)元素組成的子數(shù)組：

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

這樣一看，好像并沒(méi)有節(jié)省多少代碼量！別急，我們?cè)倏聪旅娴睦?#xff1a;在一個(gè)長(zhǎng)度100的數(shù)組中，獲取區(qū)間5-8、11-13、19-22、55-99四個(gè)區(qū)間的元素。

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(5, 45)]; // 55，56，57，58.....99 NSArray *newArray = [oldArray objectAtIndexes:indexes];

接下來(lái)我們做一下性能測(cè)量，從一個(gè)長(zhǎng)度10萬(wàn)的隨機(jī)字串中，刪除所有 a 開(kāi)頭的字符串。

• 方式1，批量對(duì)象刪除：

首先篩選元素：

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

執(zhí)行刪除：

[array removeObjectsInArray:subarrayToRemove];

• 方式2，批量索引刪除：

首先篩選索引集：

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

執(zhí)行刪除：

[array removeObjectsAtIndexes:indexesToRemove];

我們對(duì)比執(zhí)行時(shí)間：

方式	執(zhí)行時(shí)間 ms
方式1，批量對(duì)象刪除	25.33
方式2，批量索引刪除	15.33

我們姑且忽略篩選元素以及篩選索引的時(shí)間，他們不會(huì)相差很多（都是O(n)）。后來(lái)實(shí)驗(yàn)證明后者效率更佳。

剖析：方式1比方式2多了一個(gè)步驟，即遍歷每一個(gè)元素以獲得他們的索引值。如果待刪除子集的長(zhǎng)度是 k，這個(gè)多出來(lái)的步驟的時(shí)間復(fù)雜度是是 O(n * k)。隨著 n 和 k 的增加，執(zhí)行時(shí)間的差距將會(huì)更加明顯。

NSOrderedSet && NSMutableOrderedSet

NSOrderedSet && NSMutableOrderedSet 是有序 Set，比 傳統(tǒng) 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

判斷集合包含關(guān)系：

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

判斷集合相交關(guān)系：

[a intersectsSet:b]; // a是否與b有交集。b為NSSet [a intersectsOrderedSet:b]; // a是否與b有交集。b為NSOrderedSet

為了探索 NSOrderedSet 與 NSArray 的性能差異，我們看一下性能測(cè)試結(jié)果：

?類(lèi)型	100w元素，100w次索引訪(fǎng)問(wèn)（ms）	1w元素，1w次查找	100w元素內(nèi)存占用（MB）
NSArray	38.012	597.029	15.266
NSOrderedSet	33.796	1.006	33.398

可以看出，僅從訪(fǎng)問(wèn)效率來(lái)看，兩者差別并不大，而在 1w 次查找的對(duì)比中，NSOrderedSet 竟然快出 590 倍之多！內(nèi)存代價(jià)雖然比較昂貴，但在可接受的范圍之內(nèi)。

NSPointerArray

NSPointerArray 是 NSMutableArray 的高階類(lèi)型，比 NSMutableArray 具備更廣泛的內(nèi)存管理能力，具體如下：

• 和傳統(tǒng) NSArray 一樣，用于有序的插入或移除；

• 與傳統(tǒng) NSArray 不同的是，可以存儲(chǔ) NULL，且 NULL 參與 count 的計(jì)算；

• 與傳統(tǒng) NSArray 不同的是，count 可以被設(shè)置，如果設(shè)置較大的 count 則使用 NULL 占位；

• 可以使用 weak 或 unsafe_unretained 來(lái)修飾成員；

• 可以修改對(duì)象的判等方式；

• 可以使對(duì)象加入時(shí)進(jìn)行拷貝；

• 成員可以是所有指針類(lèi)型，不僅限于 OC 對(duì)象；

我們可以舉個(gè)簡(jiǎn)單的例子看一下，例如它可以存儲(chǔ) weak 引用：

NSPointerArray *pointerArray = NSPointerArray.weakObjectsPointerArray; [pointerArray addPointer:(void *)obj]; // obj的引用計(jì)數(shù)不會(huì)增加

注：obj 被釋放后，pointerArray.count 依然是1，這是因?yàn)?NULL 也會(huì)參與占位。調(diào)用 compact 方法將清空所有的 NULL 占位。

我們可以通過(guò)函數(shù) + pointerArrayWithOptions:指定更多有趣的存儲(chǔ)方式。

上面的NSPointerArray.weakObjectsPointerArray 實(shí)際上是 [NSPointerArray pointerArrayWithOptions:NSPointerFunctionsWeakMemory] 的簡(jiǎn)化版。

NSPointerFunctionsOptions 是一個(gè)選項(xiàng)，不同于枚舉，選項(xiàng)類(lèi)型是可以疊加的。這些選項(xiàng)可以分為內(nèi)存管理、個(gè)性判定、拷貝偏好三大類(lèi)：

?內(nèi)存管理相關(guān)?

• NSPointerFunctionsWeakMemory：弱引用，不增加引用計(jì)數(shù)。元素被釋放后變成 NULL，但 count 保持不變。調(diào)用 compact 方法后將刪除所有 NULL 元素并重新調(diào)整大小。對(duì)應(yīng) ARC 的weak。

• NSPointerFunctionsStrongMemory：強(qiáng)引用，引用計(jì)數(shù)+1。對(duì)應(yīng) ARC 的 strong。

• NSPointerFunctionsOpaqueMemory：不增加引用計(jì)數(shù)，也不創(chuàng)建弱引用，元素釋放后變野指針。對(duì)應(yīng) ARC 的 unsafe_unretained。

• NSPointerFunctionsMallocMemory：移除元素時(shí)調(diào)用 free() 進(jìn)行釋放，添加時(shí)調(diào)用 calloc()。不同于上面三種，這種方式適用于元素為普通指針類(lèi)型的情況。

• NSPointerFunctionsMachVirtualMemory：用于 Mach 的虛擬內(nèi)存管理。

?個(gè)性判定相關(guān)?

什么是個(gè)性判定呢？個(gè)性判定包含以下三個(gè)方面：

• 相等性判定（即判等）。傳統(tǒng)容器都是使用元素的 -isEqual 進(jìn)行相等性判定。當(dāng)對(duì) NSArray 調(diào)用 indexOfObject 方法時(shí)，數(shù)組會(huì)遍歷內(nèi)部元素，對(duì)每個(gè)遍歷到的元素與輸入元素進(jìn)行 isEqual 對(duì)比，直到碰到第一個(gè)判定成功（即 isEqual 返回 YES）的元素并返回其索引；若所有元素均判定失敗則返回 NSNotFound。

• 哈希值判定。如使用對(duì)象的 Hash 方法是一種哈希值判定方式。常見(jiàn)的 NSSet、NSDictionary 都是使用元素的 Hash 方法獲取哈希值，從而決定其索引位置。

• 描述值判定。如使用對(duì)象的 Description 方法是一種描述值判定方式。對(duì)數(shù)組進(jìn)行打印時(shí)，打印的內(nèi)容中包含了所有對(duì)象的 Description 值。

我們來(lái)看下個(gè)性判定相關(guān)的 NSPointerFunctionsOptions 有哪些：

• NSPointerFunctionsObjectPersonality：判定元素為 OC 對(duì)象。用元素的 isEqual 方法判等，Hash 方法計(jì)算哈希值，Description 方法做描述（NSLog 打印）。

• NSPointerFunctionsObjectPointerPersonality：判定元素為對(duì)象指針。通過(guò)對(duì)比指針來(lái)判等，通過(guò)指針左移計(jì)算哈希值，用 Description 方法對(duì)其描述。

• NSPointerFunctionsCStringPersonality：判定元素為 CString。使用 strcmp 判等，對(duì)該字符串求哈希，用 UTF8 編碼格式對(duì)其描述。

• NSPointerFunctionsIntegerPersonality：判定元素為整型值。使用整型值的右移結(jié)果作哈希值和判等條件。

• NSPointerFunctionsStructPersonality:：判定元素為結(jié)構(gòu)體指針。用 memcmp 對(duì)比內(nèi)存判等，對(duì)實(shí)際內(nèi)存求哈希。

• NSPointerFunctionsOpaquePersonality：不確定類(lèi)型。通過(guò)對(duì)比指針來(lái)判等，通過(guò)指針左移計(jì)算哈希值。

?拷貝偏好?

NSPointerFunctionsCopyIn：添加元素時(shí)，實(shí)際添加的是元素的拷貝。

接下來(lái)我們對(duì)比一組數(shù)據(jù)，單位 ms

容器/方法	100w次add	100w次隨機(jī)訪(fǎng)問(wèn)
NSMutableArray	0.023	69.9
NSPointerArray+Strong?Memory	0.024	60
NSPointerArray+Week?Memory	759	224.4

可見(jiàn)，NSMutableArray 與 NSPointerArray+ strong 幾乎沒(méi)有差別，而 NSPointerArray + Weak 的性能開(kāi)銷(xiāo)就不那么樂(lè)觀(guān)了。

那我們?cè)趺蠢斫鈧鹘y(tǒng)數(shù)組與 NSPointerArray 的關(guān)系呢？傳統(tǒng)數(shù)組就相當(dāng)于一個(gè)特殊的 NSPointerArray，把它的 options 設(shè)成這樣：

NSPointerFunctionsStrongMemory | NSPointerFunctionsObjectPersonality

即個(gè)性判定為 OC 對(duì)象，強(qiáng)引用，不進(jìn)行拷貝。

NSMapTable

NSMapTable ?為 NSMutableDictionary 的高階類(lèi)型。它與 NSPointerArray 類(lèi)似，可以指定 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

保留傳統(tǒng)字典的經(jīng)典能力：

[table setObject:obj forKey:key]; // 設(shè)置Key,Value [table objectForKey:key] // 根據(jù)Key獲取Value [table removeObjectForKey:] // 刪除

不同的是，系統(tǒng)并沒(méi)有給它 subscript 支持，即不能使用類(lèi)似 dict[key] = value 的中括號(hào)語(yǔ)法。

那我們?cè)趺蠢斫鈧鹘y(tǒng)字典與 NSMapTable 的關(guān)系呢？傳統(tǒng)字典就相當(dāng)于一個(gè)特殊的 NSMapTable，把它的 keyOptions 設(shè)成這樣：

NSPointerFunctionsStrongMemory | NSPointerFunctionsObjectPersonality| NSPointerFunctionsCopyIn；

需要注意的是NSPointerFunctionsCopyIn, 老字典會(huì)對(duì) key 進(jìn)行 copy，value 不會(huì)。但是如果大家平日里都使用NSString作為 key，那大可不必考慮 copy 的性能損耗（因?yàn)橹皇菧\拷貝）。但如果使用的是NSMutableString或者一些進(jìn)行深拷貝的類(lèi)型，那就另當(dāng)別論了。

再把它的 valueOptions 設(shè)成這樣：

NSPointerFunctionsStrongMemory | NSPointerFunctionsObjectPersonality

即 key 為強(qiáng)引用、個(gè)性判定為 OC 對(duì)象、添加元素時(shí)進(jìn)行拷貝；value 為強(qiáng)引用，個(gè)性判定為 OC 對(duì)象，但不進(jìn)行拷貝。

NSMapTable與老字典的性能不能一概而論，因?yàn)樗麄兊闹饕阅懿顒e也是來(lái)自于NSPointerFunctionsCopyIn與NSPointerFunctionsWeakMemory。后者會(huì)帶來(lái)一定的性能損耗，而前者要看key的NSCopying協(xié)議是如何實(shí)現(xiàn)的。

NSHashTable

NSHashTable ?是 NSMutableSet 的高階類(lèi)型，與 NSPointerArray、NSMapTable 一樣，可以指定 NSPointerFunctionsOptions：

[NSHashTable hashTableWithOptions:options]

便捷的初始化方法：

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

保留傳統(tǒng) Set 的經(jīng)典能力：

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

同樣，如果用 NSHashTable 表示傳統(tǒng)字典，傳統(tǒng)字典應(yīng)該是這樣的 NSHashTable：

NSPointerFunctionsStrongMemory | NSPointerFunctionsObjectPersonality

NSCache

NSCache是Foundation框架提供的緩存類(lèi)的實(shí)現(xiàn)，使用方式類(lèi)似于可變字典，由于NSMutableDictionary的存在，很多人在實(shí)現(xiàn)緩存時(shí)都會(huì)使用可變字典，但這樣是具有很多局限性的。我們可以從3個(gè)方面理清楚它與NSMutableDictionary的區(qū)別：

• NSCache集成了多種緩存淘汰策略（雖然官方文檔沒(méi)有明確指出，但從測(cè)試結(jié)果來(lái)看是 LRU 即 Lease Recent Usage)，且發(fā)生內(nèi)存警告時(shí)會(huì)進(jìn)行清理）, 保證了 cache 不會(huì)占用過(guò)多的內(nèi)存資源。

• NSCache是線(xiàn)程安全的。可以從不同的線(xiàn)程中對(duì)NSCache進(jìn)行增刪改查操作，而不需要自己對(duì)cache加鎖。

• 與NSMutableDictionary不同, ?NSCache不會(huì)對(duì)key進(jìn)行拷貝。

下面簡(jiǎn)單介紹一下 LRU（雙鏈表+散列表）的核心邏輯。

?LRU 緩存淘汰策略核心邏輯?

• 與老字典不同，散列表的 value 變成經(jīng)過(guò)封裝的節(jié)點(diǎn) Node，包含：

• • key: 即字典的key

  • value：即字典的value

  • prev：上一個(gè)節(jié)點(diǎn)

  • next: 下一個(gè)節(jié)點(diǎn)

• 插入散列表的節(jié)點(diǎn)將移到鏈表頭部，時(shí)間復(fù)雜度為O(1)

• 被訪(fǎng)問(wèn)的或更新的節(jié)點(diǎn)將移動(dòng)到鏈表頭部，時(shí)間復(fù)雜度為O(1)

• 當(dāng)容量超限時(shí)，鏈表尾部的節(jié)點(diǎn)將被移除（時(shí)間復(fù)雜度為O(1)），同時(shí)從散列表中移除

我們看到，鏈表的各項(xiàng)操作并沒(méi)有影響散列表的整體時(shí)間復(fù)雜度。

?開(kāi)始使用?

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

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

實(shí)現(xiàn)NSCacheDelegate，元素被淘汰時(shí)會(huì)收到回調(diào)：

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

接下來(lái)分別插入5個(gè)元素：

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

元素按照1、2、3、4、5的順序插入的，意味著下一個(gè)被淘汰的元素是1。

接下來(lái)我們?cè)囍L(fǎng)問(wèn)1，然后插入6：

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

結(jié)果打印：

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

原因是1被訪(fǎng)問(wèn)后被置換成了鏈表的 head，此時(shí) tail 變成了2。再次插入新數(shù)據(jù)后，tail 元素2被淘汰。

總結(jié)

近不修，無(wú)以行遠(yuǎn)路; 低不修，無(wú)以登高山。若要成為最炙手可熱的技術(shù)人才，打下扎實(shí)的地基是必不可少的。面對(duì)如今移動(dòng)端人才市場(chǎng)的飽和，小伙伴們更應(yīng)該抓住機(jī)會(huì)，磨礪自己，在行業(yè)中不斷成長(zhǎng)和進(jìn)步，最終成為行業(yè)內(nèi)不可或缺的精英人才。

我們同樣也在期待志同道合的小伙伴加入，點(diǎn)擊閱讀原文即可投遞簡(jiǎn)歷。

優(yōu)秀且富有抱負(fù)的你，還在等什么呢？

?作者介紹?

丁文超，網(wǎng)易云信資深 iOS 工程師，負(fù)責(zé)云信 IM、解決方案的設(shè)計(jì)和研發(fā)工作。Github:?WenchaoD

?活動(dòng)報(bào)名中?

4月10日，定位上海的【網(wǎng)易 MCtalk * 掘金 JTalk 娛樂(lè)社交技術(shù)沙龍 】正在限時(shí)免費(fèi)報(bào)名中，歡迎掃碼鎖定席位。

總結(jié)

以上是生活随笔為你收集整理的技术干货 | iOS 高阶容器详解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。