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當中使用相等性的時候尤其要注意重載isEqua方法。當然有些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要高效的使用並沒有看起來那麼簡單,當集合類中的元素到達一定量級之後,考慮下背後的算法效率很有必要,這也是為什麼一直強調算法對於程序員的重要性。