前言

哈希(Hash)或者說散列表，它是一種基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)。Hash 表是一種特殊的數(shù)據(jù)結(jié)構(gòu)，它同數(shù)組、鏈表以及二叉排序樹等相比較有很明顯的區(qū)別，但它又是是數(shù)組和鏈表的基礎(chǔ)上演化而來，既具有數(shù)組的有點，又具有鏈表的有點。能夠快速定位到想要查找的記錄，而不是與表中存在的記錄的關(guān)鍵字進(jìn)行比較來進(jìn)行查找。應(yīng)用了函數(shù)映射的思想將記錄的存儲位置與記錄的關(guān)鍵字關(guān)聯(lián)起來，從而能夠很快速地進(jìn)行查找。

一、Hash設(shè)計思想

試想如果我們對一個數(shù)組進(jìn)行查詢，這個數(shù)組里，每一個元素都是一個字符串。我們知道數(shù)組最快的檢索辦法是通過數(shù)組的下標(biāo)進(jìn)行檢索，但是對于這種場景，我們無能為力，只能從頭查到尾，從而查詢出目標(biāo)元素。

如果我們要根據(jù)名字找到其中的任何一個元素，就需要遍歷整個數(shù)組。最壞情況下時間復(fù)雜度是O(n) ,但是借助 Hash 可以將時間復(fù)雜度降為O(1)。

Hash表采用一個映射函數(shù) f :key —> address 將關(guān)鍵字映射到該記錄在表中的存儲位置，從而在想要查找該記錄時，可以直接根據(jù)關(guān)鍵字和映射關(guān)系計算出該記錄在表中的存儲位置，通常情況下，這種映射關(guān)系稱作為Hash函數(shù)，而通過Hash函數(shù)和關(guān)鍵字計算出來的存儲位置（注意這里的存儲位置只是表中的存儲位置，并不是實際的物理地址）稱作為Hash地址。比如上述例子中，假如聯(lián)系人信息采用Hash表存儲，則當(dāng)想要找到 “l(fā)isi” 的信息時，直接根據(jù) “l(fā)isi” 和 Hash 函數(shù)計算出 Hash 地址即可。

哈希算法歷史悠久，業(yè)界著名的哈希算法也有很多，比如 MD5、SHA。哈希算法是指將任意長度的二進(jìn)制值串映射為固定長度的二進(jìn)制值串，這個映射的規(guī)則就是哈希算法，而通過原始數(shù)據(jù)映射之后得到的二進(jìn)制值串就是哈希值。有以下幾個特點：

• 從哈希值不能反向推導(dǎo)出原始數(shù)據(jù)（所以哈希算法也叫單向哈希算法或單向散列函數(shù))。
• 對輸入數(shù)據(jù)非常敏感，哪怕原始數(shù)據(jù)只修改了一個 Bit，最后得到的哈希值也大不相同。
• 散列沖突的概率要很小，對于不同的原始數(shù)據(jù)，哈希值相同的概率非常小。
• 哈希算法的執(zhí)行效率要盡量高效，針對較長的文本，也能快速地計算出哈希值。

為了更好說明這種設(shè)計思想，筆者先設(shè)計出一種最笨的 Hash 函數(shù)，將所有字符串中的字符轉(zhuǎn)化為數(shù)字后相加。

上表中數(shù)組的下標(biāo)就是字符串對應(yīng)的數(shù)字值。根據(jù)對應(yīng)的數(shù)字值，我們就能輕易找到任何想要的對象，時間復(fù)雜度為O(1)。

二、Hash函數(shù)設(shè)計

所謂的 hash 算法就是將字符串轉(zhuǎn)換為數(shù)字的算法。通常有以下幾種構(gòu)造 Hash 函數(shù)的方法：

2.1 直接定址法

取關(guān)鍵字或者關(guān)鍵字的某個線性函數(shù)為 Hash 地址，即address(key) = a * key + b; 如知道學(xué)生的學(xué)號從2000開始，最大為4000，則可以將address(key)=key-2000(其中a = 1)作為Hash地址。

2.2 平方取中法

對關(guān)鍵字進(jìn)行平方計算，取結(jié)果的中間幾位作為 Hash 地址。如有以下關(guān)鍵字序列 {421，423，436} ，平方之后的結(jié)果為 {177241，178929，190096} ，那么可以取中間的兩位數(shù) {72，89，00} 作為 Hash 地址。

2.3 折疊法

將關(guān)鍵字拆分成幾部分，然后將這幾部分組合在一起，以特定的方式進(jìn)行轉(zhuǎn)化形成Hash地址。如圖書的 ISBN 號為 8903-241-23，可以將 address(key)=89+03+24+12+3 作為 Hash 地址。

2.4 除留取余法

如果知道 Hash 表的最大長度為 m，可以取不大于m的最大質(zhì)數(shù) p，然后對關(guān)鍵字進(jìn)行取余運算，address(key)=key % p。這里 p 的選取非常關(guān)鍵，p 選擇的好的話，能夠最大程度地減少沖突，p 一般取不大于m的最大質(zhì)數(shù)。

三、Hash表大小的確定

Hash 表的空間如果遠(yuǎn)遠(yuǎn)大于實際存儲的記錄數(shù)據(jù)的個數(shù)，則造成空間浪費；如果過小，則容易造成沖突。Hash 表大小確定通常有這兩種思路：

• 如果最初知道存儲的數(shù)據(jù)量，則需要根據(jù)存儲個數(shù) 和 關(guān)鍵字的分布特點來確定 Hash 表的大小。
• 事先不知道最終需要存儲的記錄個數(shù)，需要動態(tài)維護(hù)Hash表的容量，此時可能需要重新計算 Hash 地址。

四、Hash 沖突及解決方案

4.1 Hash沖突產(chǎn)生

有這樣一個問題：因為我們是用數(shù)組大小對哈希值進(jìn)行取模，有可能不同鍵值所得到的索引值相同，這里就是沖突。如在最初的實例中，如果多出了sizhang這樣一個元素，那么就存在兩個 756。

顯然出現(xiàn)的這種情況是不合理的，解決該沖突的方法就是改變數(shù)據(jù)結(jié)構(gòu)。我們將數(shù)組內(nèi)的元素改變?yōu)橐粋€鏈表，這樣就能容下足夠多的元素了，沖突問題也能得到解決。具體如何解決請看下面的鏈地址法。

4.2 Hash 沖突解決

4.2.1 開放定址法

發(fā)生沖突時，使用某種探測技術(shù)在 Hash 表中形成一個探測序列，然后沿著這個探測序列依次查找下去，當(dāng)碰到一個空的單元時，則插入其中。比較常用的探測方法有線性探測法，如有一組關(guān)鍵字{12，13，25，23，38，34，6，84，91}，Hash 表長為14，Hash 函數(shù)為 address(key) = key % 11，當(dāng)插入12，13，25時可以直接插入，而當(dāng)插入 23 時，地址 1 被占用了（因為 12%11 和 23%11 的結(jié)果相同）。此時沿著地址 1 依次往下探測(探測步長可以根據(jù)情況而定)，直到探測到地址4，發(fā)現(xiàn)為空，則將 23 插入其中。

4.2.2 鏈地址法

采用數(shù)組和鏈表相結(jié)合的數(shù)據(jù)結(jié)構(gòu)，將 Hash 地址相同的記錄存儲在一張線性表中，而每張表的表頭的序號即為計算得到的Hash地址。如下圖最左邊是數(shù)組結(jié)構(gòu)，數(shù)組內(nèi)的元素為鏈表結(jié)構(gòu)。

image

所以針對之前案列沖突的解決方案如下：

image

檢索的時候可以這樣檢索，首先找到gaofei后，之后再遍歷鏈表，找到feigao了。同理對于 sizhang 的沖突也是如此解決。

五、Hash 表的用處以及優(yōu)劣

5.1 Hash 表的實際應(yīng)用

上述說了這么多關(guān)于 Hash 表的知識點，但是 Hash 表在代碼的世界中，實際上又有什么應(yīng)用場景，可能有些讀者會一頭霧水，這里筆者就以簡單的三個例子來說明 Hash 表的實際應(yīng)用場景。

• 1 、找出兩文件找出重復(fù)的元素
  假設(shè)有兩個文件，文件中均包含一些短字符串，字符串個數(shù)分別為n。它們是有重復(fù)的字符串，現(xiàn)在需要找出所有重復(fù)的字符串。
  最笨的解決辦法可能是：遍歷文件 1 中的每個元素，取出每一個元素分別去文件 2 中進(jìn)行查找，這樣的時間復(fù)雜度為O（n^2）。
  但是借助 Hash 表可以有一種相對巧妙的方法，分別遍歷文件 1 中的元素和文件 2 中的元素，然后放入 Hash Table 中，對于遍歷的每一個元素我們只要簡單的做一下計數(shù)處理即可。最后遍歷整個 Hash 列表，找出所有個數(shù)大于 1 的元素即為重復(fù)的元素。

• 2、找出兩文件找出出現(xiàn)次數(shù)最多的元素
  同找出兩文件找出重復(fù)的元素這樣的問題解決方案類似，只是在最后遍歷的時找計數(shù)最大的元素，即為出現(xiàn)次數(shù)最多的元素。

• 3、路由算法
  多線程處理數(shù)據(jù)的場景下，通常需要將一個數(shù)據(jù)集分給不同的線程進(jìn)行處理，同時要保證，相同的元素需要分到相同的處理線程上。這
  其實這個就是一個很典型的 Hash 值應(yīng)用場景，對于很多的計算引擎默認(rèn)都是用 Hash 算法去解決這個問題。因為相同元素的 Hash 值相同，那么我們可以取 Hash 之后進(jìn)行模運算，運算結(jié)果分配到不同的線程。

image

5.2 Hash 表的優(yōu)缺點及注意點

• 優(yōu)點
  哈希表的效率非常高，查找、插入、刪除操作只需要接近常量的時間即0(1）的時間級。如果需要在一秒種內(nèi)查找上千條記錄通常使用哈希表，哈希表的速度明顯比樹快，樹的操作通常需要O(N)的時間級。哈希表不僅速度快，編程實現(xiàn)也相對容易。如果不需要遍歷數(shù)據(jù)，不二的選擇。
• 缺點
  它是基于數(shù)組的，數(shù)組創(chuàng)建后難于擴(kuò)展。有些情況下，哈希表被基本填滿時，性能下降得非常嚴(yán)重，所以開發(fā)者必須要清楚表中將要存儲的數(shù)據(jù)量?；蛘咭部梢远ㄆ诘匕褦?shù)據(jù)轉(zhuǎn)移到更大的哈希表中，不過這個過程耗時相對比較大。
• 注意點
  在設(shè)計Hash算法的時候。一定要保證相同字符串產(chǎn)生的 Hash 值相同，同時要盡量的減小Hash沖突的發(fā)生，這樣才算是好的 hash 算法。

六、Hash 在 iOS 中的應(yīng)用

這一部分的篇幅可能稍稍有點大，筆者原本打算給這一部分抽出來單獨寫一篇文章，但是發(fā)現(xiàn)沒有 Hash 概念做鋪墊，文章略顯空洞，所以這里干脆把所有東西整合到一起，請讀者耐下心來看。

這一部分的內(nèi)容就以下面的一個問題為中心。并在此問題上不斷的擴(kuò)充，以點帶面。

iOS系統(tǒng)API給我們提供一個自動過濾重復(fù)元素的容器 NSMutableSet/NSSet，如：當(dāng)我們向該實例對象中添加字符串時，如果重復(fù)添加兩個相同的字符串，集合中只會保留一個。NSMutableSet/NSSet內(nèi)部一些實現(xiàn)機制要比我們自己寫的濾重方法效率高。但是對于自定義一個類如Person，如果想利用NSMutableSet/NSSet來過濾重復(fù)元素（如多個Person實例的uid相同），我們必須要同時實現(xiàn)- (BOOL)isEqual:和- (NSUInteger)hash這兩個方法。這里先簡單介紹他們的關(guān)系：兩個相等的實例，他們的hash值一定相等。但是hash值相等的兩個實例，不一定相等。重點來了，利用 NSMutableSet/NSSet 具體如何實現(xiàn)過濾 Person 重復(fù)元素 ？

在解決這個問題之前我先用簡單的篇幅 6.1 小結(jié) 和 6.2 小結(jié) 分別介紹- (BOOL)isEqual:和- (NSUInteger)hash這兩個方法。具體可以參考這篇文章。

6.1 關(guān)于- (BOOL)isEqual:方法

• 為什么要有isEqual方法？
  OC 中 == 運算符只是簡單地判斷是否是同一個對象, 而 isEqual 方法可以判斷對象是否相同。

• 如何重寫isEqual方法？
  但對于自定義類型來說, 做判等時通常需要重寫isEqual方法。

@interface Person : NSObject
@property (nonatomic, copy) NSString *name;
@property (nonatomic, strong) NSDate *birthday;
@end

- (BOOL)isEqual:(id)object {
    if (self == object) {
        return YES;
    }

    if (![object isKindOfClass:[Person class]]) {
        return NO;
    }

    return [self isEqualToPerson:(Person *)object];
}

- (BOOL)isEqualToPerson:(Person *)person {
    if (!person) {
        return NO;
    }

    BOOL haveEqualNames = (!self.name && !person.name) || [self.name isEqualToString:person.name];
    BOOL haveEqualBirthdays = (!self.birthday && !person.birthday) || [self.birthday isEqualToDate:person.birthday];

    return haveEqualNames && haveEqualBirthdays;
}

上述代碼主要步驟如下:
1、 ==運算符判斷是否是同一對象, 因為同一對象必然完全相同
2、 判斷是否是同一類型, 這樣不僅可以提高判等的效率, 還可以避免隱式類型轉(zhuǎn)換帶來的潛在風(fēng)險
3、通過封裝的isEqualToPerson方法, 提高代碼復(fù)用性
4、 判斷person是否是nil, 做參數(shù)有效性檢查
5、 對各個屬性分別使用默認(rèn)判等方法進(jìn)行判斷
6、 返回所有屬性判等的與結(jié)果

6.2 關(guān)于- (NSUInteger)hash方法

• hash方法什么時候被調(diào)用?
  如果在 Person 類中重寫- (NSUInteger)hash方法，該方法只在 Person 實例對象被添加至NSSet或?qū)erson實例對象設(shè)置為NSDictionary的 key 時會調(diào)用。注意是設(shè)置為 key 而不是 value

• hash方法和判等的關(guān)系？
  為了優(yōu)化判等的效率, 基于 hash 的 NSSet 和 NSDictionary 在判斷成員是否相等時, 通常會這樣做:
  首先判斷 hash 值是否和目標(biāo) hash 值相等。如果相同再進(jìn)行對象之后的判等邏輯, 作為判等的結(jié)果； 如果不等, 直接判斷為不相等。
  簡單地說:hash值是對象判等的必要非充分條件。

• 如何重寫 hash 方法？
  很多人在iOS開發(fā)中, 都是這么重寫hash方法的，如果自己親自測試一下會發(fā)現(xiàn)直接重寫父類方法并不能實現(xiàn)過濾重復(fù)元素的功能。

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

對于上面的 Person 類正確的 Hash 實現(xiàn)方法應(yīng)該是借助位運算。代碼如下：

- (NSUInteger)hash {
    return [self.name hash] ^ [self.birthday hash];
}

6.3 同時實現(xiàn)- (BOOL)isEqual: 和 - (NSUInteger)hash方法，實現(xiàn)過濾自定義實例的功能

6.3.1 代碼實現(xiàn)

@interface Person : NSObject
@property (nonatomic, assign) NSInteger uid;
@property (nonatomic, strong) NSString *name;
@end

@implementation Person
- (instancetype)initWithID:(NSInteger)uid name:(NSString *)name{
    if (self = [super init]) {
        self.uid = uid;
        self.name = name;
    }
    return self;
}

- (BOOL)isEqual:(Person *)object{
    BOOL result;
    if (self == object) {
        result = YES;
    }else{
        if (object.uid == self.uid) {
            result = YES;
        }else{
            result = NO;
        }
    }
    NSLog(@"%@ compare with %@ result = %@",self,object,result ? @"Equal":@"NO Equal");
    return result;
}

- (NSString *)description{
    return [NSString stringWithFormat:@"%p(%ld,%@)",self,self.uid,self.name];
}

- (NSUInteger)hash{
    NSUInteger hashValue = self.uid; //在這里只需要比較uid就行。這
    樣的話就滿足如果兩個實例相等，那么他們的 hash 一定相等，但反過
    來hash值相等，那么兩個實例不一定相等。但是在 Person 這個實例
    中，hash值相等那么實例一定相等。（不考慮繼承之類的）
    NSLog(@"hash = %lu,addressValue = %lu,address = %p",(NSUInteger)hashValue,(NSUInteger)self,self);
    return hashValue;
}
@end

//調(diào)用重寫hash后的方法
- (void)viewDidLoad {
    [super viewDidLoad];
    self.mutSet = [NSMutableSet set];
    Person *person1 = [[Person alloc] initWithID:1 name:@"nihao"];
    Person *person2 = [[Person alloc] initWithID:2 name:@"nihao2"];
    NSLog(@"begin add %@",person1);
    [self.mutSet addObject:person1];
    NSLog(@"after add %@",person1);

    NSLog(@"begin add %@",person2);
    [self.mutSet addObject:person2];
    NSLog(@"after add %@",person2);

    NSLog(@"count = %d",self.mutSet.count);

    Person *person3 = [[Person alloc] initWithID:1 name:@"nihao"];
    NSLog(@"begin add %@",person3);
    [self.mutSet addObject:person3];
    NSLog(@"after add %@",person3);

    NSLog(@"count = %d",self.mutSet.count);
}

6.3.2 關(guān)于一些結(jié)論

• NSMutableSet/NSSet中添加 Person 對象的時候，就會調(diào)用- (NSUInteger)hash方法。

• NSMutableSet/NSSet中添加 personA 對象的時候，如果NSMutableSet/NSSet 中之前就已經(jīng)存在 personB對象，且 personB 對象的 - (NSUInteger)hash返回值和personA的- (NSUInteger)hash返回值相等, 則 personA 會繼續(xù)調(diào)用- (BOOL)isEqual:方法 ，其中此方法以personB為參數(shù)；否則不等, 繼續(xù)下一個元素判斷。

• 具體的判等過程如下。
  1、如果 personB 的- (NSUInteger)hash返回值是否和 personA 的- (NSUInteger)hash返回值相等,則直接執(zhí)行第 3 步；如果不相等，則執(zhí)行第 2 步。
  2、判斷 NSMutableSet/NSSet 中是否存在下一個沒有比較過的元素，如果有繼續(xù)執(zhí)行第 1 步；如果沒有，則personA 會被添加到NSMutableSet/NSSet 集合中，執(zhí)行結(jié)束命令。
  3、調(diào)用 personA 的- (BOOL)isEqual:其中該方法 以personB為參數(shù)，如果返回結(jié)果為 NO(兩者不相等)， 則執(zhí)行第 2 步；如果返回結(jié)果為Yes(兩者是相同元素)，則 NSMutableSet/NSSet 中存在和 personA 相同的元素，personA不會被添加到集合中，直接執(zhí)行結(jié)束命令。

七、總結(jié)

本文章主要講解了 Hash 的設(shè)計思想、Hash 函數(shù)設(shè)計、Hash 沖突的產(chǎn)生和解決、 Hash 的優(yōu)缺點以及應(yīng)用，最后結(jié)合實際代碼，說明了 Hash 在 iOS 判等過程中的實際應(yīng)用。關(guān)于 Hash 實際上還有很多值得我們研究的問題，就單單是 Hash 函數(shù)設(shè)計而言，就足夠我們花上很多功夫去研究，當(dāng)然感興趣的同學(xué)可以去仔細(xì)研究下。

來源：
鏈接：http://m.itdecent.cn/p/2a71b027b723