iOS 開發中的幾個集合類別——NSArray、NSDictionary、NSSet 以及它們的 Mutable 版本——相信每個人都用過。單純使用不會出錯,但要同時做到高效(時間複雜度)與精確(業務正確性),就得理解它們背後藏著的演算法。
專案裡幾乎不可能不用集合類別。把使用情境抽象化,其實就是:暫存一批物件,供後續業務邏輯操作。保存時 Insert,更新時 Get,不再需要時 Delete——對應到電腦世界的術語就是讀與寫。操作場景就這麼多,差別只在於你怎麼存、怎麼取。
唸資料結構時我們知道,資料的組織方式不同,讀寫效率也不同。插入快,查找往往就慢:無序陣列插入是 O(1),查找卻是 O(N);想要查找快,比如排序過的陣列,查找來到 O(logN),但插入時必須維持有序,代價是 O(N)。插入與查找就像魚與熊掌——想下次快速找到一本書,整理書架時就得先花心思分類。或者跳出時間維度,用空間來補償:改用雜湊表或 Dictionary 儲存,查找可以快到 O(1),代價是吃掉更多記憶體。
先把陣列存好,使用時大致就這三種:
// 場景一:遍歷
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、gender、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,系統就走你的邏輯;若沒重寫,系統就用記憶體位址來比。
有些 model layer 的設計允許同一個業務物件在 App 內存在多份複本,這種架構下使用 Array 判斷相等時,特別容易出問題,務必記得重寫 isEqual。反之,若你的 model layer 保證一個業務物件永遠只對應一個位址,那 isEqual 就是多餘的。
和 isEqual 成雙成對的 hash 常被提起,官方文件甚至明文規定兩者必須同時實作。學過雜湊表就知道:業務上相等的兩個物件,hash 值必定相同。系統預設的 hash 其實就是回傳物件的記憶體位址。
問題來了:既然已經有 isEqual 可以判斷相等,為什麼還需要 hash?
答案是 hash 能更快排除不可能相等的情況。在 NSArray 中判斷某物件是否存在,需要遍歷並呼叫 N 次 isEqual,複雜度 O(N);若在呼叫 isEqual 之前先比 hash,值不同就直接跳過,值相同才再補一次 isEqual 做確認。而 hash 之所以快,看它的宣告就明白了:
- (NSUInteger)hash {
return [_name hash];
}回傳值是一個 NSUInteger,往往與物件的儲存位置直接相關,因此可以 O(1) 的代價快速定位。相較之下,Array 裡的元素是在一片連續記憶體中排列的,與 hash 值毫無關聯,只能逐一比對。
不過這種便捷有個前提:集合中的物件必須唯一,也就是不允許重複元素——例如 NSDictionary 與 NSSet。當你呼叫:
[dictionary objectForKey:key]; [set addObject:object];
為了維持唯一性,都必須先判斷物件是否已存在,這正是 hash 發揮作用的地方。這也解釋了為什麼用 NSArray 時只會觸發 isEqual,而用 NSDictionary、NSSet 時 hash 會被頻繁呼叫。
所以使用 NSDictionary、NSSet 時,同時重寫 isEqual 與 hash 對效能至關重要。hash 的實作不必過度糾結,對關鍵 property 做點運算、確保絕大部分情境下值不相同即可——反正 hash 之後還會走一次 isEqual,不會影響業務的正確性。
Objective-C 這幾個集合類別要用得高效,並沒有表面看起來那麼簡單。當集合規模上了量級,背後的演算法效率就值得細究——這也正是人們一再強調演算法對工程師的重要性。