技术干货 | iOS 高阶容器详解
導讀:近期,在面試 iOS 工程師的過程中,當我問到候選人小伙伴都了解哪些 iOS 容器類型時,大多數小伙伴能給出的答復就是NSArray、NSDictionary 和 NSSet以及對應的可變類型,有些優秀的小伙伴能夠說出 NSCache,還能對它的原理侃侃而談,這是非常棒的。但是總體而言,高階容器的普及在技術同學中還是比較少。本文,我們就來詳細聊聊我們對 iOS 高階容器類型的深入研究結果,并討論其使用場景。
文|丁文超
網易云信資深 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;獲取數量:
數量+1:
[self.itemCountSet addObject:item];數量-1:
[self.itemCountSet removeObject:item];可以看出,NSCountedSet 就是為這種場景量身定做的。
NSIndexSet && NSMutableIndexSet
NSIndexSet && NSMutableIndexSet是包含不重復整數的容器類型,使得索引訪問具備批量執行的能力。比如我們需要獲取數組的第0,第2,第4個元素組成的子數組:
這樣一看,好像并沒有節省多少代碼量!別急,我們再看下面的例子:在一個長度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(5, 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
| 容器/方法 | 100w次add | 100w次隨機訪問 | 
| NSMutableArray | 0.023 | 69.9 | 
| NSPointerArray+Strong?Memory | 0.024 | 60 | 
| NSPointerArray+Week?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 設成這樣:
需要注意的是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.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 | NSPointerFunctionsObjectPersonalityNSCache
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被淘汰。
總結
近不修,無以行遠路; 低不修,無以登高山。若要成為最炙手可熱的技術人才,打下扎實的地基是必不可少的。面對如今移動端人才市場的飽和,小伙伴們更應該抓住機會,磨礪自己,在行業中不斷成長和進步,最終成為行業內不可或缺的精英人才。
我們同樣也在期待志同道合的小伙伴加入,點擊閱讀原文即可投遞簡歷。
優秀且富有抱負的你,還在等什么呢?
?作者介紹?
丁文超,網易云信資深 iOS 工程師,負責云信 IM、解決方案的設計和研發工作。Github:?WenchaoD
?活動報名中?
4月10日,定位上海的【網易 MCtalk * 掘金 JTalk 娛樂社交技術沙龍 】正在限時免費報名中,歡迎掃碼鎖定席位。
總結
以上是生活随笔為你收集整理的技术干货 | iOS 高阶容器详解的全部內容,希望文章能夠幫你解決所遇到的問題。
 
                            
                        - 上一篇: 云信小课堂|5分钟快速实现安卓端PK连麦
- 下一篇: 趋势|40个统计数据展示CPaaS的20
