[轉]一些NSArray,NSDictionary,NSSet相關的演算法知識

iOS編程當中的幾個集合類：NSArray，NSDictionary，NSSet以及對應的Mutable版本，應該所有人都用過。只是簡單使用的話，相信沒人會用錯，但要做到高效（時間複雜度）精確（業務準確性），還需要瞭解其中所隱藏的演算法知識。在項目當中使用集合類幾乎是不可避免的，集合類的使用場景其實 ...

iOS編程當中的幾個集合類：NSArray，NSDictionary，NSSet以及對應的Mutable版本，應該所有人都用過。只是簡單使用的話，相信沒人會用錯，但要做到高效（時間複雜度）精確（業務準確性），還需要瞭解其中所隱藏的演算法知識。

在項目當中使用集合類幾乎是不可避免的，集合類的使用場景其實可以進行抽象的歸類。大多數時候我們需要將若幹個對象（object）暫時保存起來，以備後續的業務邏輯進行操作，「保存和操作」，或者說「存與取」，對應到電腦世界的術語就是讀和寫。最初保存的時候我們Insert，下次進行更新的時候我們再Get，不再需要的時候我們調用Delete，所以你看集合類的操作場景其實就那麼多，關鍵在於我們存的方式，和取的方式不同。

最初我們學習數據結構和演算法的時候，知道數據的組織方式不同，比如Array, List, Stack, Heap, Tree，其對應的讀和取效率（時間複雜度）也不同。如果insert的效率高，下次get的時候效率就低，比如無序的Array，插入的時候O（1），查找的時候就變O（N）。如果想要查找的速度快，比如排序過的Array，查找的速度在O（logN），插入的時候就必須要保持Array有序這一特性O（N）。所以插入和查找是魚與熊掌，想要下次快速的找到一本書，就必須在整理書架的時候多花些心思分門別類。或者我們跳出時間的維度，用更多的空間來做彌補，使用哈希表或者Dictionary來存儲數據，查找的速度可以快至O（1），缺點是犧牲了更多的空間。

當我們預先存好Array之後，使用的時候大多是以下幾種場景：

場景一

for (NSObject* obj in self.arr) {
    //update each object
}

場景二

if ([self.arr containsObject:obj] == false) {
    [self.arr addObject:obj];
}

場景三

if ([self.arr containsObject:obj] == true) {
    [self.arr removeObject:obj];
}

第一種場景沒有多少可發掘的，一次乾凈利索的遍歷費時O（N）。唯一需要註意的是切忌在遍歷的時候改變集合對象，比如：

for (NSObject* obj in self.arr) {
    if(obj.isInvalid){
        [self.arr removeObject:obj];
    }
}

如果要在遍歷的時候刪除可以換種寫法，比如：

for (int i = self.arr.count-1; i > 0; i --) {
    NSObject* obj = self.arr[i];
    if (obj.isInvalid) {
        [self.arr removeObject:obj];
    }
}

場景二和場景三需要特別留意，containsObject，removeObject都涉及到一個集合當中的重要概念，即相等性。

值的相等性很簡單，不用思索就能得出直觀的答案，比如1==1，2.0f==2.0f。

對象的相等性就不那麼簡單了。什麼時候我們認為兩個對象是相等的呢？我們可以從兩個維度去理解相等性。

同一對象相等：

理論上說兩個對象的指針如果是指向同一塊記憶體區域，那麼他們一定是相等的，一定是指向同一個對象。這種情況下我們判斷相等性是通過

if (obj1 == obj2)

業務屬性相等：

兩個對象即使不指向同一塊記憶體區域，但他們的所有（或者部分關鍵的）property是相等的，我們也可以認為這兩個對象是相等的，比如連個UserProfile對象，他們的name，gener，age屬性都相等，在業務層面，我們可以認為他們是相等的，此時我們不能用==來判斷相等性了，需要重載isEqual，或者自己實現isEqualToXXX：

@implementation MyObject

- (BOOL)isEqual:(id)object
{
    if (self == object) {
        return true;
    }
    if ([object isKindOfClass:[self class]] == false) {
        return false;
    }
    
    MyObject* myObject = object;
    if ([self.name isEqualToString:myObject.name]) {
        return true;
    }
    
    return false;
}

@end

所以當我們判斷兩個集合當中對象是否相等時，一定要心中明確是那種相等。當調用containsObject，removeObject的時候，如果我們重載了isEqual，系統就通過我們的isEqual方法來判斷相等性，如果沒有重載，那麼系統就會通過判斷記憶體地址來判斷相等性了。

有些架構model layer的設計會允許同一個業務對象在應用層存在多份拷貝，此時在Array當中使用相等性的時候尤其要註意重載isEqual方法。當然有些mode layer只允許一份拷貝，一個業務對象永遠只對應一個記憶體地址，isEqual方法就變得多餘了。

和isEqual配套的另一個方法hash也經常被提起，官方文檔甚至規定isEqual和hash必須被同時實現。學習過hash表之後，我們知道如果兩個對象業務上相等，那麼他們的hash值一定是相等的，hash方法的用處還是在於判斷相等性，系統預設的hash方法實際上返回的就是對象的記憶體地址。問題是我們已經有isEqual方法來判斷相等性了，為什麼還需要一個hash呢？

答案是hash可以更加高效快速的判斷一個對象是否存在集合當中，在NSArray當中我們需要遍歷Array，調用N次isEqual才能知道對象是否存在集合當中，時間複雜度是O（N）。在調用isEqual之前，可以通過調用hash來判斷是否相等，如果hash值不等就沒有進一步調用isEqual的必要了，如果相等必須再調用一次isEqual來確認是否真正相等。但是hash為什麼會比isEqual的效率要高呢？看下hash的聲明就明白了。

- (NSUInteger)hash
{
    return [_name hash];
}

hash方法的返回值是一個NSUInteger，這個值往往和對象在記憶體當中的存儲位置直接相關，也就是說我們可以通過這個值以O（1）的複雜度快速讀取到某個對象來判斷相等性，和Array O（N）的複雜度相比快了太多了，Array顯然不具備這種特性，Array當中的元素是在一片記憶體空間當中連續排放的，和hash的返回值沒任何關係。

但這種使用hash的便捷性有一個前提：對象在集合當中是唯一的，也就是說集合當中不允許存在重覆的元素，比如NSDictionary，NSSet。我們在使用下列方法的時候：

[dictionary objectForKey:key];
[set addObject:object];

為了保證唯一性，都需要先判斷對象是否存在集合當中，此時一個高效的判斷機制十分重要，這也就是hash發揮作用的地方，這也是為什麼使用NSArray的時候只會調用
isEqual，而使用NSDictionary，NSSet的時候會頻繁調用hash的原因。

所以當我們使用NSDictionary，NSSet的時候，同時重載isEqual和hash方法對性能至關重要。hash方法的選擇並不需要過分挑剔，對關鍵的property做下運算，保證絕大部分場景下hash值不同即可，畢竟hash調用之後還是會調用isEqual做進一步判斷，並不會對我們業務的準確性產生影響。

Objective C當中的幾個關鍵集合類：NSArray，NSDictionary，NSSet要高效的使用並沒有看起來那麼簡單，當集合類中的元素到達一定量級之後，考慮下背後的演算法效率很有必要，這也是為什麼一直強調演算法對於程式員的重要性。

轉自：一些NSArray,NSDictionary,NSSet相關的演算法知識