NSArray, NSSet, NSOrderedSet 和 NSDictionary

基礎(chǔ)集合類是每一個 Mac/iOS 應(yīng)用的基本組成部分。在本文中，我們將對”老類” (NSArray, NSSet)和”新類” (NSMapTable, NSHashTable, NSPointerArray) 進行一個深入的研究，探索每一個的效率細節(jié)，并討論其使用場景。

作者提示：本文包含一些參照結(jié)果，但它們并不意味著絕對精確，也沒有進行均差分析及多次的測試。這些結(jié)果的目的是給出運行時統(tǒng)計，來幫助我們認識到通常來說用什么會更快。所有的測試基于 iPhone 5s，使用 Xcode 5.1b1 和 iOS 7.1b1 的 64 位程序。編譯選項設(shè)置為 -Ofast 的發(fā)布構(gòu)建。Vectorize loops 和 unroll loops (默認設(shè)置) 均設(shè)置為關(guān)閉。

大 O 符號，算法復(fù)雜度計量

首先，我們需要一些理論知識。效率通常用大 O 符號描述。它定義了一個函數(shù)的極限特征，通常被用于描繪其算法效率。O 定義了函數(shù)增長率的上限。不同量級的差異非常巨大，可以看看通常使用的 O 符號的量級以及它們所對應(yīng)需要的操作數(shù)的關(guān)系。

http://wiki.jikexueyuan.com/project/objc/images/7-1.png" alt="" />

例如，如果用算法復(fù)雜度為 O(n^2)的算法對一個有 50 個元素的數(shù)組排序，需要 2,500 步的操作。而且，還有內(nèi)部的系統(tǒng)開銷和方法調(diào)用 — 所以是 250 0個操作的時間常量。 O(1)是理想的復(fù)雜度，代表著恒定的時間。好的排序算法通常需要 O(n*log n) 的時間。

可變性

大多數(shù)的集合類存在兩個版本:可變和不可變(默認)。這和其他大多數(shù)的框架有非常大的不同，一開始會讓人覺得有一點奇怪。然而其他的框架現(xiàn)在也應(yīng)用了這一特性：就在幾個月前，.NET公布了作為官方擴展的不可變集合。

最大的好處是什么？線程安全。不可變的集合完全是線程安全的，可以同時在多個線程中迭代，避免各種轉(zhuǎn)變時出現(xiàn)異常的風(fēng)險。你的 API 絕不應(yīng)該暴露一個可變的集合。

當然從不可變到可變?nèi)缓笤倩貋硎菚幸欢ù鷥r的 — 對象必須被拷貝兩次，所有集合內(nèi)的對象將被 retain/release。有時在內(nèi)部使用一個可變的集合，而在訪問時返回一個不可變的對象副本會更高效。

與其他框架不同的是，蘋果沒有提供一個線程安全的可變集合，NSCache 是例外，但它真的算不上是集合類，因為它不是一個通用的容器。大多數(shù)時候，你不會需要在集合層級的同步特性。想象一段代碼，作用是檢查字典中一個 key 是否存在，并根據(jù)檢查結(jié)果決定設(shè)置一個新的 key 或者返回某些值 — 你通常需要把多個操作歸類，這時線程安全的可變集合并不能對你有所幫助。

其實也有一些同步的，線程安全的可以使用的可變集合案例，它們往往只需要用幾行代碼，通過子類和組合的方法建立，比如這個 NSDictionary 或這個 NSArray。

需要注意的是，一些較新的集合類，如 NSHashTable，NSMapTable 和 NSPointerArray 默認就是可變的，它們并沒有對應(yīng)的不可變的類。它們用于類的內(nèi)部使用，你基本應(yīng)該不會能找到需要它們的不可變版本的應(yīng)用場景。

NSArray

NSArray 作為一個存儲對象的有序集合，可能是被使用最多的集合類。這也是為什么它有自己的比原來的 [NSArray arrayWithObjects:..., nil] 簡短得多的快速語法糖符號 @[...]。 NSArray 實現(xiàn)了 objectAtIndexedSubscript:，因為我們可以使用類 C 的語法 array[0] 來代替原來的 [array objectAtIndex:0]。

性能特征

關(guān)于 NSArray 的內(nèi)容比你想象的要多的多?；诖鎯ο蟮亩嗌伲褂酶鞣N內(nèi)部的變體。最有趣的部分是蘋果對于個別的對象訪問并不保證 O(1) 的訪問時間 — 正如你在 CFArray.h CoreFoundation 頭文件中的關(guān)于算法復(fù)雜度的注解中可以讀到的:

對于 array 中值的訪問時間，不管是在現(xiàn)在還是將來，我們保證在任何一種實現(xiàn)下最壞情況是 O(lg N)。但是通常來說它會是 O(1) (常數(shù)時間)。線性搜索操作很可能在最壞情況下的復(fù)雜度為 O(N*lg N)，但通常來說上限會更小一些。插入和刪除操作耗時通常和數(shù)組中的值的數(shù)量成線性關(guān)系。但在某些實現(xiàn)的最壞情況下會是 O(N*lg N) 。在數(shù)組中，沒有對于性能上特別有優(yōu)勢的數(shù)據(jù)位置，也就是說，為了更快地訪問到元素而將其設(shè)為在較低的 index 上，或者在較高的 index 上進行插入和刪除，或者類似的一些做法，是沒有必要的。

在測量的時候，NSArray 產(chǎn)生了一些有趣的額外的性能特征。在數(shù)組的開頭和結(jié)尾插入/刪除元素通常是一個 O(1)操作，而隨機的插入/刪除通常是 O(N) 的。

有用的方法

NSArray 的大多數(shù)方法使用 isEqual: 來檢查對象間的關(guān)系(例如 containsObject: 中)。有一個特別的方法 indexOfObjectIdenticalTo: 用來檢查指針相等，如果你確保在同一個集合中搜索，那么這個方法可以很大的提升搜索速度。 在 iOS 7 中，我們最終得到了與 lastObject 對應(yīng)的公開的 firstObject 方法，對于空數(shù)組，這兩個方法都會返回 nil — 而常規(guī)的訪問方法會拋出一個 NSRangeException 異常。

關(guān)于構(gòu)造（可變）數(shù)組有一個漂亮的細節(jié)可以節(jié)省代碼量。如果你通過一個可能為 nil 的數(shù)組創(chuàng)建一個可變數(shù)組，通常會這么寫:

NSMutableArray *mutableObjects = [array mutableCopy];
if (!mutableObjects) {
    mutableObjects = [NSMutableArray array];
}

或者通過更簡潔的三元運算符:

NSMutableArray *mutableObjects = [array mutableCopy] ?: [NSMutableArray array];

更好的解決方案是使用arrayWithArray:，即使原數(shù)組為nil，該方法也會返回一個數(shù)組對象:

NSMutableArray *mutableObjects = [NSMutableArray arrayWithArray:array];

這兩個操作在效率上幾乎相等。使用 copy 會快一點點，不過話說回來，這不太可能是你應(yīng)用的瓶頸所在。提醒：不要使用 [@[] mutableCopy]。經(jīng)典的[NSMutableArray array]可讀性更好。

逆序一個數(shù)組非常簡單：array.reverseObjectEnumerator.allObjects。我們使用系統(tǒng)提供的 reverseObjectEnumerator，每一個 NSEnumerator 都實現(xiàn)了 allObjects，該方法返回一個新數(shù)組。雖然沒有原生的 randomObjectEnumerator 方法，你可以寫一個自定義的打亂數(shù)組順序的枚舉器或者使用一些出色的開源代碼。

數(shù)組排序

有很多各種各樣的方法來對一個數(shù)組排序。如果數(shù)組存儲的是字符串對象，sortedArrayUsingSelector:是第一選擇:

NSArray *array = @[@"John Appleseed", @"Tim Cook", @"Hair Force One", @"Michael Jurewitz"];
NSArray *sortedArray = [array sortedArrayUsingSelector:@selector(localizedCaseInsensitiveCompare:)];

下面的代碼對存儲數(shù)字的內(nèi)容同樣很好，因為 NSNumber 實現(xiàn)了 compare::

NSArray *numbers = @[@9, @5, @11, @3, @1];
NSArray *sortedNumbers = [numbers sortedArrayUsingSelector:@selector(compare:)];

如果想更可控，可以使用基于函數(shù)指針的排序方法:

- (NSData *)sortedArrayHint;
- (NSArray *)sortedArrayUsingFunction:(NSInteger (*)(id, id, void *))comparator
                          context:(void *)context;
- (NSArray *)sortedArrayUsingFunction:(NSInteger (*)(id, id, void *))comparator
                          context:(void *)context hint:(NSData *)hint;

蘋果增加了一個方法來加速使用 sortedArrayHint 的排序。

hinted sort 方式在你有一個已排序的大數(shù)組 (N 個元素) 并且只改變其中一小部分（P 個添加和刪除，這里 P遠小于 N）時，會非常有效。你可以重用原來的排序結(jié)果，然后在 N 個老項目和 P 個新項目進行一個概念上的歸并排序。為了得到合適的 hint，你應(yīng)該在原來的數(shù)組排序后使用 sortedArrayHint 來在你需要的時候(比如在數(shù)組改變后想重新排序時)保證持有它。

因為block的引入，也出現(xiàn)了一些基于block的排序方法:

- (NSArray *)sortedArrayUsingComparator:(NSComparator)cmptr;
- (NSArray *)sortedArrayWithOptions:(NSSortOptions)opts
                usingComparator:(NSComparator)cmptr;

性能上來說，不同的方法間并沒有太多的不同。有趣的是，基于 selector 的方式是最快的。你可以在 GitHub 上找到測試用的源代碼:

Sorting 1000000 elements. selector: 4947.90[ms] function: 5618.93[ms] block: 5082.98[ms].

二分查找

NSArray 從 iOS 4 / Snow Leopard 開始內(nèi)置了二分查找

typedef NS_OPTIONS(NSUInteger, NSBinarySearchingOptions) {
    NSBinarySearchingFirstEqual     = (1UL << 8),
    NSBinarySearchingLastEqual      = (1UL << 9),
    NSBinarySearchingInsertionIndex = (1UL << 10),
};

- (NSUInteger)indexOfObject:(id)obj
          inSortedRange:(NSRange)r
                options:(NSBinarySearchingOptions)opts
        usingComparator:(NSComparator)cmp;

為什么要使用這個方法？類似 containsObject: 和 indexOfObject: 這樣的方法從 0 索引開始搜索每個對象直到找到目標 — 這樣不需要數(shù)組被排序，但是卻是 O(n)的效率特性。如果使用二分查找的話，需要數(shù)組事先被排序，但在查找時只需要 O(log n) 的時間。因此，對于 一百萬條記錄，二分查找法最多只需要 21 次比較，而傳統(tǒng)的線性查找則平均需要 500,000 次的比較。

這是個簡單的衡量二分查找有多快的數(shù)據(jù):

Time to search for 1000 entries within 1000000 objects. Linear: 54130.38[ms]. Binary: 7.62[ms]

作為比較，查找 NSOrderedSet 中的指定索引花費 0.23 毫秒 — 就算和二分查找相比也又快了 30 多倍。

記住排序的開銷也是昂貴的。蘋果使用復(fù)雜度為 O(n*log n) 的歸并排序，所以如果你執(zhí)行一次 indexOfObject: 的話，就沒有必要使用二分查找了。

通過指定 NSBinarySearchingInsertionIndex，你可以獲得正確的插入索引，以確保在插入元素后仍然可以保證數(shù)組的順序。

枚舉和總覽

作為測試，我們來看一個普通的使用場景。從一個數(shù)組中過濾出一些元素組成另一個數(shù)組。這些測試都包括了枚舉的方法以及使用 API 進行過濾的方式：

// 第一種方式，使用 `indexesOfObjectsWithOptions:passingTest:`.
NSIndexSet *indexes = [randomArray indexesOfObjectsWithOptions:NSEnumerationConcurrent
                                               passingTest:^BOOL(id obj, NSUInteger idx, BOOL *stop) {
    return testObj(obj);
}];
NSArray *filteredArray = [randomArray objectsAtIndexes:indexes];

// 使用 predicate 過濾，包括 block 的方式和文本 predicate 的方式
NSArray *filteredArray2 = [randomArray filteredArrayUsingPredicate:[NSPredicate predicateWithBlock:^BOOL(id obj, NSDictionary *bindings) {
    return testObj(obj);
}]];

// 基于 block 的枚舉
NSMutableArray *mutableArray = [NSMutableArray array];
[randomArray enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
    if (testObj(obj)) {
        [mutableArray addObject:obj];
    }
}];

// 傳統(tǒng)的枚舉
NSMutableArray *mutableArray = [NSMutableArray array];
for (id obj in randomArray) {
    if (testObj(obj)) {
        [mutableArray addObject:obj];
    }
}

// 使用 NSEnumerator，傳統(tǒng)學(xué)院派
NSMutableArray *mutableArray = [NSMutableArray array];
NSEnumerator *enumerator = [randomArray objectEnumerator];
id obj = nil;
while ((obj = [enumerator nextObject]) != nil) {
    if (testObj(obj)) {
        [mutableArray addObject:obj];
    }
}

// 通過下標使用 objectAtIndex：
NSMutableArray *mutableArray = [NSMutableArray array];
for (NSUInteger idx = 0; idx < randomArray.count; idx++) {
    id obj = randomArray[idx];
    if (testObj(obj)) {
        [mutableArray addObject:obj];
    }
}

為了更好的理解這里的效率測量，我們首先看一下數(shù)組是如何迭代的。

indexesOfObjectsWithOptions:passingTest: 必須每次都執(zhí)行一次 block 因此比傳統(tǒng)的使用 NSFastEnumeration 技術(shù)的基于 for 循環(huán)的枚舉要稍微低效一些。但是如果開啟了并發(fā)枚舉，那么前者的速度則會大大的超過后者幾乎 2 倍。iPhone 5s 是雙核的，所以這說得通。這里并沒有體現(xiàn)出來的是 NSEnumerationConcurrent 只對大量的對象有意義，如果你的集合中的對象數(shù)量很少，用哪個方法就真的無關(guān)緊要。甚至 NSEnumerationConcurrent 上額外的線程管理實際上會使結(jié)果變得更慢。

最大的輸家是 filteredArrayUsingPredicate:。NSPredicate 需要在這里提及是因為，人們可以寫出非常復(fù)雜的表達式，尤其是用不基于 block 的變體。使用 Core Data 的用戶應(yīng)該會很熟悉。

為了比較的完整，我們也加入了 NSEnumerator 作為比較 — 雖然沒有任何理由再使用它了。然而它竟出人意料的快(至少還是比基于 NSPredicate 的過濾要快)，它的運行時消耗無疑比快速枚舉更多 — 現(xiàn)在它只用于向后兼容。甚至沒有優(yōu)化過的 objectAtIndex: 都要更快些。

NSFastEnumeration

在OSX 10.5和iOS的最初版本中，蘋果增加了 NSFastEnumeration。在此之前，只有每次返回一個元素的 NSEnumeration ，每次迭代都有運行時開銷。而快速枚舉，蘋果通過 countByEnumeratingWithState:objects:count: 返回一個數(shù)據(jù)塊。該數(shù)據(jù)塊被解析成 id 類型的 C 數(shù)組。這就是更快的速度的原因；迭代一個 C 數(shù)組要快得多，而且可以被編譯器更深一步的優(yōu)化。手動的實現(xiàn)快速枚舉是十分難辦的，所以蘋果的 FastEnumerationSample 是一個不錯的開始，還有一篇 Mike Ash 的文章也很不錯。

應(yīng)該用arrayWithCapacity:嗎?

初始化NSArray的時候，可以選擇指定數(shù)組的預(yù)期大小。在檢測的時候，結(jié)果是在效率上沒有差別 — 至少在統(tǒng)計誤差范圍內(nèi)的測量的時間幾乎相等。有消息透漏說實際上蘋果根本沒有使用這個參數(shù)。然而使用 arrayWithCapacity: 仍然好處，它可以作為一種隱性的文檔來幫助你理解代碼:

Adding 10.000.000 elements to NSArray. no count 1067.35[ms] with count: 1083.13[ms].

子類化注意事項

很少有理由去子類化基礎(chǔ)集合類。大多數(shù)時候，使用 CoreFoundation 級別的類并且自定義回調(diào)函數(shù)定制自定義行為是更好的解決方案。 創(chuàng)建一個大小寫不敏感的字典，一種方法是子類化 NSDictionary 并且自定義訪問方法，使其將字符串始終變?yōu)樾?或大寫)，并對排序也做類似的修改。更快更好的解決方案是提供一組不同的 CFDictionaryKeyCallBacks 集，你可以提供自定義的 hash 和 isEqual: 回調(diào)。你可以在這里找到一個例子。這種方法的優(yōu)美之處應(yīng)該歸功于 toll-free 橋接)，它仍然是一個簡單的字典，因此可以被任何使用 NSDictionary 作為參數(shù)的API接受。

子類作用的一個例子是有序字典的用例。.NET 提供了一個 SortedDictionary，Java 有 TreeMap，C++ 有 std::map。雖然你可以使用 C++ 的 STL 容器，但卻無法使它自動的 retain/release ，這會讓使用起來笨拙得多。因為 NSDictionary 是一個類簇，所以子類化跟人們想象的相比非常不同。這已經(jīng)超過了本文的討論范疇，這里有一個真實的有序字典的例子。

NSDictionary

一個字典存儲任意的對象鍵值對。 由于歷史原因，初始化方法 [NSDictionary dictionaryWithObjectsAndKeys:object, key, nil] 使用了相反的值到鍵的順序，而新的快捷語法則從 key 開始，@{key : value, ...}。

NSDictionary 中的鍵是被拷貝的并且需要是不變的。如果在一個鍵在被用于在字典中放入一個值后被改變的話，那么這個值就會變得無法獲取了。一個有趣的細節(jié)是，在 NSDictionary 中鍵是被 copy 的，但是在使用一個 toll-free 橋接的 CFDictionary 時卻只會被 retain。CoreFoundation 類沒有通用的拷貝對象的方法，因此這時拷貝是不可能的(*)。這只適用于你使用 CFDictionarySetValue() 的時候。如果你是通過 setObject:forKey 來使用一個 toll-free 橋接的 CFDictionary 的話，蘋果會為其增加額外處理邏輯，使得鍵被拷貝。但是反過來這個結(jié)論則不成立 — 使用已經(jīng)轉(zhuǎn)換為 CFDictionary 的 NSDictionary 對象，并用對其使用 CFDictionarySetValue() 方法，還是會導(dǎo)致調(diào)用回 setObject:forKey 并對鍵進行拷貝。

(*)其實有一個現(xiàn)成的鍵的回調(diào)函數(shù) kCFCopyStringDictionaryKeyCallBacks 可以拷貝字符串，因為對于 ObjC對象來說， CFStringCreateCopy() 會調(diào)用 [NSObject copy]，我們可以巧妙使用這個回調(diào)來創(chuàng)建一個能進行鍵拷貝的 CFDictionary。

性能特征

蘋果在定義字典的計算復(fù)雜度時顯得相當?shù)驼{(diào)。唯一的信息可以在 CFDictionary 的頭文件中找到:

對于字典中值的訪問時間，不管是在現(xiàn)在還是將來，我們保證在任何一種實現(xiàn)下最壞情況是 O(N)。但通常來說它會是 O(1) (常數(shù)時間)。插入和刪除操作一般來說也會是常數(shù)時間，但是在某些實現(xiàn)中最壞情況將為 O(N*N)。通過鍵來訪問值將比直接訪問值要快（如果你有這樣的操作要做的話）。對于同樣數(shù)目的值，字典需要花費比數(shù)組多得多的內(nèi)存空間。

跟數(shù)組相似的，字典根據(jù)尺寸的不同使用不同的實現(xiàn)，并在其中無縫切換。

枚舉和總覽

過濾字典有幾個不同的方法:

// 使用 keysOfEntriesWithOptions:passingTest:，可并行
NSSet *matchingKeys = [randomDict keysOfEntriesWithOptions:NSEnumerationConcurrent
                                               passingTest:^BOOL(id key, id obj, BOOL *stop)
{
    return testObj(obj);
}];
NSArray *keys = matchingKeys.allObjects;
NSArray *values = [randomDict objectsForKeys:keys notFoundMarker:NSNull.null];
__unused NSDictionary *filteredDictionary = [NSDictionary dictionaryWithObjects:values
                                                                        forKeys:keys];

// 基于 block 的枚舉
NSMutableDictionary *mutableDictionary = [NSMutableDictionary dictionary];
[randomDict enumerateKeysAndObjectsUsingBlock:^(id key, id obj, BOOL *stop) {
    if (testObj(obj)) {
        mutableDictionary[key] = obj;
    }
}];

// NSFastEnumeration
NSMutableDictionary *mutableDictionary = [NSMutableDictionary dictionary];
for (id key in randomDict) {
    id obj = randomDict[key];
    if (testObj(obj)) {
        mutableDictionary[key] = obj;
    }
}

 // NSEnumeration
 NSMutableDictionary *mutableDictionary = [NSMutableDictionary dictionary];
 NSEnumerator *enumerator = [randomDict keyEnumerator];
 id key = nil;
 while ((key = [enumerator nextObject]) != nil) {
       id obj = randomDict[key];
       if (testObj(obj)) {
           mutableDictionary[key] = obj;
       }
 }

// 基于 C 數(shù)組，通過 getObjects:andKeys: 枚舉
NSMutableDictionary *mutableDictionary = [NSMutableDictionary dictionary];
id __unsafe_unretained objects[numberOfEntries];
id __unsafe_unretained keys[numberOfEntries];
[randomDict getObjects:objects andKeys:keys];
for (int i = 0; i < numberOfEntries; i++) {
    id obj = objects[i];
    id key = keys[i];
    if (testObj(obj)) {
       mutableDictionary[key] = obj;
    }
 }

(*)使用 getObjects:andKeys: 時需要注意。在上面的代碼例子中，我們使用了可變長度數(shù)組這一 C99 特性(通常，數(shù)組的數(shù)量需要是一個固定值)。這將在棧上分配內(nèi)存，雖然更方便一點，但卻有其限制。上面的代碼在元素數(shù)量很多的時候會崩潰掉，所以我們使用基于 malloc/calloc 的分配 (和 free) 以確保安全。

為什么這次 NSFastEnumeration 這么慢？迭代字典通常需要鍵和值兩者，快速枚舉只能枚舉鍵，我們必須每次都自己獲取值。使用基于 block 的 enumerateKeysAndObjectsUsingBlock: 更高效，因為兩者都可以更高效的被提前獲取。

這次測試的勝利者又是通過 keysOfEntriesWithOptions:passingTest: 和 objectsForKeys:notFoundMarker: 的并發(fā)迭代。代碼稍微多了一點，但是可以用 category 進行漂亮的封裝。

應(yīng)該用 dictionaryWithCapacity: 嗎?

到現(xiàn)在你應(yīng)該已經(jīng)知道該如何測試了，簡單的回答是不，count 參數(shù)沒有改變?nèi)魏问虑?

Adding 10000000 elements to NSDictionary. no count 10786.60[ms] with count: 10798.40[ms].

排序

關(guān)于字典排序沒有太多可說的。你只能將鍵數(shù)組排序為一個新對象，因此你可以使用任何正規(guī)的 NSArray 的排序方法:

- (NSArray *)keysSortedByValueUsingSelector:(SEL)comparator;
- (NSArray *)keysSortedByValueUsingComparator:(NSComparator)cmptr;
- (NSArray *)keysSortedByValueWithOptions:(NSSortOptions)opts
                      usingComparator:(NSComparator)cmptr;

共享鍵

從 iOS 6 和 OS X 10.8 開始，新建的字典可以使用一個預(yù)先生成好的鍵集，使用 sharedKeySetForKeys: 從一個數(shù)組中創(chuàng)建鍵集，然后用 dictionaryWithSharedKeySet: 創(chuàng)建字典。共享鍵集會復(fù)用對象，以節(jié)省內(nèi)存。根據(jù) Foundation Release Notes，sharedKeySetForKeys: 中會計算一個最小完美哈希，這個哈希值可以取代字典查找過程中探索循環(huán)的需要，因此使鍵的訪問更快。

雖然在我們有限的測試中沒有法線蘋果在 NSJSONSerialization 中使用這個特性，但毫無疑問，在處理 JSON 的解析工作時這個特性可以發(fā)揮得淋漓盡致。(使用共享鍵集創(chuàng)建的字典是 NSSharedKeyDictionary 的子類；通常的字典是 __NSDictionaryI / __NSDictionaryM，I / M 表明可變性；可變和不可變的的字典在 toll-free 橋接后對應(yīng)的都是 _NSCFDictionary 類。)

有趣的細節(jié)：共享鍵字典始終是可變的，即使對它們執(zhí)行了”copy”命令后也是。這個行為文檔中并沒有說明，但很容易被測試:

id sharedKeySet = [NSDictionary sharedKeySetForKeys:@[@1, @2, @3]]; // 返回 NSSharedKeySet
NSMutableDictionary *test = [NSMutableDictionary dictionaryWithSharedKeySet:sharedKeySet];
test[@4] = @"First element (not in the shared key set, but will work as well)";
NSDictionary *immutable = [test copy];
NSParameterAssert(immutable.count == 1);
((NSMutableDictionary *)immutable)[@5] = @"Adding objects to an immutable collection should throw an exception.";
NSParameterAssert(immutable.count == 2);

NSSet

NSSet 和它的可變變體 NSMutableSet 是無序?qū)ο蠹?。檢查一個對象是否存在通常是一個 O(1) 的操作，使得比 NSArray 快很多。NSSet 只在被使用的哈希方法平衡的情況下能高效的工作；如果所有的對象都在同一個哈?？饍?nèi)，NSSet 在查找對象是否存在時并不比 NSArray 快多少。

NSSet 還有變體 NSCountedSet，以及非 toll-free 計數(shù)變體 CFBag / CFMutableBag。

NSSet 會 retain 它其中的對象，但是根據(jù) set 的規(guī)定，對象應(yīng)該是不可變的。添加一個對象到 set 中隨后改變它會導(dǎo)致一些奇怪的問題并破壞 set 的狀態(tài)。

NSSet 的方法比 NSArray 少的多。沒有排序方法，但有一些方便的枚舉方法。重要的方法有 allObjects，將對象轉(zhuǎn)化為 NSArray，anyObject 則返回任意的對象，如果 set 為空，則返回 nil。

Set 操作

NSMutableSet 有幾個很強大的方法，例如 intersectSet:，minusSet: 和 unionSet:。

http://wiki.jikexueyuan.com/project/objc/images/7-2.png" alt="" />

應(yīng)該用setWithCapacity:嗎?

我們再一次測試當創(chuàng)建 set 時給定容量大小是否會有顯著的速度差異:

Adding 1.000.000 elements to NSSet. no count 2928.49[ms] with count: 2947.52[ms].

在統(tǒng)計誤差范圍內(nèi)，結(jié)果沒有顯著差異。有一份證據(jù)表明至少在上一個 runtime 版本中，有很多的性能上的影響。

NSSet 性能特征

蘋果在 CFSet 頭文件中沒有提供任何關(guān)于算法復(fù)雜度的注釋。

這個檢測非常符合我們的預(yù)期：NSSet 在每一個被添加的對象上執(zhí)行 hash 和 isEqual: 方法并管理一系列哈希值，所以在添加元素時耗費了更多的時間。set的隨機訪問比較難以測試，因為這里執(zhí)行的都是 anyObject。

這里沒有必要包含 containsObject: 的測試，set 要快幾個數(shù)量級，畢竟這是它的特點。

NSOrderedSet

NSOrderedSet 在 iOS 5 和 Mac OS X 10.7 中第一次被引入，除了 Core Data，幾乎沒有直接使用它的 API?？瓷先ニC合了 NSArray 和 NSSet 兩者的好處，對象查找，對象唯一性，和快速隨機訪問。

NSOrderedSet 有著優(yōu)秀的 API 方法，使得它可以很便利的與其他 set 或者有序 set 對象合作。合并，交集，差集，就像 NSSet 支持的那樣。它有 NSArray 中除了比較陳舊的基于函數(shù)的排序方法和二分查找以外的大多數(shù)排序方法。畢竟 containsObject: 非?？欤詻]有必要再用二分查找了。

NSOrderedSet 的 array 和 set 方法分別返回一個 NSArray 和 NSSet，這些對象表面上是不可變的對象，但實際上在 NSOrderedSet 更新的時候，它們也會更新自己。如果你在不同線程上使用這些對象并發(fā)生了詭異異常的時候，知道這一點是非常有好處的。本質(zhì)上，這些類使用的是 __NSOrderedSetSetProxy 和 __NSOrderedSetArrayProxy。

附注：如果你想知道為什么 NSOrderedSet 不是 NSSet 的子類，NSHipster 上有一篇非常好的文章解釋了可變/不可變類簇的缺點。

NSOrderedSet 性能特征

如果你看到這份測試，你就會知道 NSOrderedSet 代價高昂了，畢竟天下沒有免費的午餐:

這個測試在每一個集合類中添加自定義字符串，隨后隨機訪問它們。

NSOrderedSet 比 NSSet 和 NSArray 占用更多的內(nèi)存，因為它需要同時維護哈希值和索引。

NSHashTable

NSHashTable 效仿了 NSSet，但在對象/內(nèi)存處理時更加的靈活?？梢酝ㄟ^自定義 CFSet 的回調(diào)獲得 NSHashTable 的一些特性，哈希表可以保持對對象的弱引用并在對象被銷毀之后正確的將其移除，有時候如果手動在 NSSet 中添加的話，想做到這個是挺惡心的一件事。它是默認可變的 — 并且這個類沒有相應(yīng)的不可變版本。

NSHashTable 有 ObjC 和原始的 C API，C API 可以用來存儲任意對象。蘋果在 10.5 Leopard 系統(tǒng)中引入了這個類，但是 iOS 的話直到最近的 iOS 6 中才被加入。足夠有趣的是它們只移植了 ObjC API；更多強大的 C API 沒有包括在 iOS 中。

NSHashTable 可以通過 initWithPointerFunctions:capacity: 進行大量的設(shè)置 — 我們只選取使用預(yù)先定義的 hashTableWithOptions: 這一最普遍的使用場景。其中最有用的選項有利用 weakObjectsHashTable 來使用其自身的構(gòu)造函數(shù)。

NSPointerFunctions

這些指針函數(shù)可以被用在 NSHashTable，NSMapTable和 NSPointerArray 中，定義了對存儲在這個集合中的對象的獲取和保留行為。這里只介紹最有用的選項。完整列表參見 NSPointerFunctions.h。

有兩組選項。內(nèi)存選項決定了內(nèi)存管理，個性化定義了哈希和相等。

NSPointerFunctionsStrongMemory 創(chuàng)建了一個r etain/release 對象的集合，非常像常規(guī)的 NSSet 或 NSArray。

NSPointerFunctionsWeakMemory 使用和 __weak 等價的方式來存儲對象并自動移除被銷毀的對象。

NSPointerFunctionsCopyIn 在對象被加入到集合前拷貝它們。

NSPointerFunctionsObjectPersonality 使用對象的 hash 和 isEqual: (默認)。

NSPointerFunctionsObjectPointerPersonality 對于 isEqual: 和 hash 使用直接的指針比較。

NSHashTable 性能特征

如果你只是需要 NSSet 的特性，請堅持使用 NSSet。NSHashTable 在添加對象時花費了將近2倍的時間，但是其他方面的效率卻非常相近。

NSMapTable

NSMapTable 和 NSHashTable 相似，但是效仿的是 NSDictionary。因此，我們可以通過 mapTableWithKeyOptions:valueOptions: 分別控制鍵和值的對象獲取/保留行為。存儲弱引用是 NSMapTable 最有用的特性，這里有4個方便的構(gòu)造函數(shù):

• strongToStrongObjectsMapTable
• weakToStrongObjectsMapTable
• strongToWeakObjectsMapTable
• weakToWeakObjectsMapTable

注意，除了使用 NSPointerFunctionsCopyIn，任何的默認行為都會 retain (或弱引用)鍵對象而不會拷貝它，這與 CFDictionary 的行為相同而與 NSDictionary 不同。當你需要一個字典，它的鍵沒有實現(xiàn) NSCopying 協(xié)議的時候（比如像 UIView），這會非常有用。

如果你好奇為什么蘋果”忘記”為 NSMapTable 增加下標，你現(xiàn)在知道了。下標訪問需要一個 id<NSCopying> 作為 key，對 NSMapTable 來說這不是強制的。如果不通過一個非法的 API 協(xié)議或者移除 NSCopying 協(xié)議來削弱全局下標，是沒有辦法給它增加下標的。

你可以通過 dictionaryRepresentation 把內(nèi)容轉(zhuǎn)換為普通的 NSDictionary。不像 NSOrderedSet，這個方法返回的是一個常規(guī)的字典而不是一個代理。

NSMapTable 性能特征

NSMapTable 只比 NSDictionary 略微慢一點。如果你需要一個不 retain 鍵的字典，放棄 CFDictionary 而使用它吧。

NSPointerArray

NSPointerArray類是一個稀疏數(shù)組，工作起來與 NSMutableArray 相似，但可以存儲 NULL 值，并且 count 方法會反應(yīng)這些空點。可以用 NSPointerFunctions 對其進行各種設(shè)置，也有應(yīng)對常見的使用場景的快捷構(gòu)造函數(shù) strongObjectsPointerArray 和 weakObjectsPointerArray。

在能使用 insertPointer:atIndex: 之前，我們需要通過直接設(shè)置 count 屬性來申請空間，否則會產(chǎn)生一個異常。另一種選擇是使用 addPointer:，這個方法可以自動根據(jù)需要增加數(shù)組的大小。

你可以通過 allObjects 將一個 NSPointerArray 轉(zhuǎn)換成常規(guī)的 NSArray。這時所有的 NULL 值會被去掉，只有真正存在的對象被加入到數(shù)組 — 因此數(shù)組的對象索引很有可能會跟指針數(shù)組的不同。注意：如果向指針數(shù)組中存入任何非對象的東西，試圖執(zhí)行 allObjects 都會造成 EXC_BAD_ACCESS 崩潰，因為它會一個一個地去 retain ”對象”。

從調(diào)試的角度講，NSPointerArray沒有受到太多歡迎。description方法只是簡單的返回了<NSConcretePointerArray: 0x17015ac50>。為了得到所有的對象需要執(zhí)行[pointerArray allObjects]，當然，如果存在NULL的話會改變索引。

NSPointerArray 性能特征

在性能方面， NSPointerArray 真的非常非常慢，所以當你打算在一個很大的數(shù)據(jù)集合上使用它的時候一定要三思。在本測試中我們比較了使用 NSNull 作為空標記的 NSMutableArray ，而對 NSPointerArray 我們用 NSPointerFunctionsStrongMemory 來進行設(shè)置 (這樣對象會被適當?shù)?retain)。在一個有 10,000 個元素的數(shù)組中，我們每隔十個插入一個字符串 ”Entry %d”。此測試包括了用 NSNull.null 填充 NSMutableArray 的總時間。對于 NSPointerArray，我們使用 setCount: 來代替:

注意 NSPointerArray 需要的時間比 NSMutableArray 多了超過 250 倍(!) 。這非常奇怪和意外。跟蹤內(nèi)存是比較困難的，所以按理說 NSPointerArray 會更高效才對。不過由于我們使用的是同一個 NSNull 來標記空對象，所以除了指針也沒有什么更多的消耗。

NSCache

NSCache 是一個非常奇怪的集合。在 iOS 4 / Snow Leopa