1. 什么是Hash表

先看一下hash表的結(jié)構(gòu)圖：

image.png

數(shù)組 + 鏈表

哈希表（Hash table，也叫散列表）遍搞，是根據(jù)鍵（Key）而直接訪問在內(nèi)存存儲(chǔ)位置的數(shù)據(jù)結(jié)構(gòu)固额。也就是說，它通過計(jì)算一個(gè)關(guān)于鍵值的函數(shù)辐董，將所需查詢的數(shù)據(jù)映射到表中一個(gè)位置來訪問記錄扫尖，這加快了查找速度白对。這個(gè)映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表
白話一點(diǎn)的說就是通過把Key通過一個(gè)固定的算法函數(shù)（hash函數(shù)）轉(zhuǎn)換成一個(gè)整型數(shù)字换怖，然后就對(duì)該數(shù)字對(duì)數(shù)組的長度進(jìn)行取余甩恼，取余結(jié)果就當(dāng)作數(shù)組的下標(biāo)，將value存儲(chǔ)在以該數(shù)字為下標(biāo)的數(shù)組空間里沉颂。

當(dāng)使用hash表查詢時(shí)条摸，就是使用hash函數(shù)將key轉(zhuǎn)換成對(duì)應(yīng)的數(shù)組下標(biāo)，并定位到該下標(biāo)的數(shù)組空間里獲取value铸屉，這樣就充分利用到數(shù)組的定位性能進(jìn)行數(shù)據(jù)定位钉蒲。

先了解一下下面幾個(gè)常說的幾個(gè)關(guān)鍵字是什么：
key：我們輸入待查找的值
value：我們想要獲取的內(nèi)容
hash值：key通過hash函數(shù)算出的值（對(duì)數(shù)組長度取模，便可得到數(shù)組下標(biāo)）
hash函數(shù)（散列函數(shù)）：存在一種函數(shù)F彻坛，根據(jù)這個(gè)函數(shù)和查找關(guān)鍵字key顷啼，可以直接確定查找值所在位置，而不需要一個(gè)個(gè)遍歷比較昌屉。這樣就預(yù)先知道key在的位置钙蒙，直接找到數(shù)據(jù)，提升效率间驮。
即
地址index=F(key)
hash函數(shù)就是根據(jù)key計(jì)算出該存儲(chǔ)地址的位置躬厌，hash表就是基于hash函數(shù)建立的一種查找表。

2. Hash函數(shù)的構(gòu)造方法

方法

方法有很多種蜻牢，比如直接定址法烤咧、數(shù)字分析法偏陪、平方取中法抢呆、折疊法、隨機(jī)數(shù)法笛谦、除留余數(shù)法等抱虐，網(wǎng)上相關(guān)介紹有很多，這里就不重點(diǎn)說這個(gè)了

hash函數(shù)設(shè)計(jì)的考慮因素

• 計(jì)算hash地址所需時(shí)間（沒有必要搞一個(gè)很復(fù)雜的函數(shù)去計(jì)算）
• 關(guān)鍵字的長度
• 表長
• 關(guān)鍵字分布是否均勻饥脑，是否有規(guī)律可循
• 盡量減少?zèng)_突

3. hash沖突

什么是hash沖突

對(duì)不同的關(guān)鍵字可能得到同一散列地址恳邀，即k1≠k2懦冰，而f(k1)=f(k2)，或f(k1) MOD 容量 =f(k2) MOD 容量谣沸，這種現(xiàn)象稱為碰撞刷钢，亦稱沖突。
通過構(gòu)造性能良好的hash函數(shù)乳附，可以減少?zèng)_突内地，但一般不可能完全避免沖突，因此解決沖突是hash表的另一個(gè)關(guān)鍵問題赋除。
創(chuàng)建和查找hash表都會(huì)遇到?jīng)_突阱缓，兩種情況下解決沖突的方法應(yīng)該一致。

解決hash沖突

• 開放定址法
  這種方法也稱再散列法举农，基本思想是：當(dāng)關(guān)鍵字key的hash地址p=F(key)出現(xiàn)沖突時(shí)荆针，以p為基礎(chǔ)，產(chǎn)生另一個(gè)hash地址p1颁糟，如果p1仍然沖突航背，再以p為基礎(chǔ)，再產(chǎn)生另一個(gè)hash地址p2棱貌，沃粗。。键畴。知道找出一個(gè)不沖突的hash地址pi最盅，然后將元素存入其中。
  通用的再散列函數(shù)的形式：
  H = (F(key) + di) MOD m
  其中i=1起惕，2涡贱，。惹想。问词。，m-1 為碰撞次數(shù)
  m為表長嘀粱。
  F(key)為hash函數(shù)激挪。
  di為增量序列，增量序列的取值方式不同锋叨，相應(yīng)的再散列方式也不同垄分。
  1） 線性探測(cè)再散列
  di = 1，2娃磺，3薄湿，。。豺瘤。吆倦，m-1
  沖突發(fā)生時(shí)，順序查看表中下一單元坐求，直到找出一個(gè)空單元或查遍全表蚕泽。
  2）二次探測(cè)再散列
  di = 1^2, -1^2, 2^2, -2^2,..., k^2, -k^2 (k <= m-1)
  發(fā)生沖突時(shí)，在表的左右進(jìn)行跳躍式探測(cè)桥嗤，比較靈活赛糟。
  3）偽隨機(jī)數(shù)探測(cè)再散列
  di = 偽隨機(jī)序列
  下面有個(gè)網(wǎng)上的示列：
  現(xiàn)有一個(gè)長度為11的哈希表，已填有關(guān)鍵字分別為17砸逊，60璧南，29的三條記錄。其中采用的哈希函數(shù)為f(key)= key MOD 11∈σ荩現(xiàn)有第四個(gè)記錄司倚，關(guān)鍵字為38。根據(jù)以上哈希算法篓像，得出哈希地址為5动知，跟關(guān)鍵字60的哈希地址一樣，產(chǎn)生了沖突员辩。根據(jù)增量d的取法的不同盒粮，有一下三種場(chǎng)景：
  
  image.png
  
  線性探測(cè)法： 當(dāng)發(fā)生沖突時(shí)，因?yàn)閒(key) + d奠滑，所以首先5 + 1 = 6丹皱，得到下一個(gè)hash地址為6，又沖突宋税，依次類推摊崭，最后得到空閑的hash地址是8，然后將數(shù)據(jù)填入hash地址為8的空閑區(qū)域杰赛。
  二次探測(cè)法： 當(dāng)發(fā)生沖突時(shí)呢簸，因?yàn)閐 = 1^2，所以5 + 1 = 6乏屯，得到的下一個(gè)hash地址為6根时，又沖突，因?yàn)閐 = -1^2,所以5 + (-1) = 4辰晕，得到下一個(gè)hash地址為4蛤迎，是空閑則將數(shù)據(jù)填入該區(qū)域。
  偽隨機(jī)數(shù)探測(cè)法： 隨機(jī)數(shù)法就是完全根據(jù)偽隨機(jī)序列來決定的伞芹，如果根據(jù)一個(gè)隨機(jī)數(shù)種子得到一個(gè)偽隨機(jī)序列{1忘苛，-2蝉娜，2唱较，扎唾。。南缓。胸遇，k}，那么首先得到的地址為6汉形，第二個(gè)是3纸镊，依次類推，空閑則將數(shù)據(jù)填入概疆。
• 鏈地址法（拉鏈法逗威，位桶法）
  將產(chǎn)生沖突的關(guān)鍵字的數(shù)據(jù)存儲(chǔ)在沖突hash地址的一個(gè)線性鏈表中。實(shí)現(xiàn)時(shí)岔冀，一種策略是散列表同一位置的所有沖突結(jié)果都是用棧存放的凯旭，新元素被插入到表的前端還是后端完全取決于怎樣方便。
  
  image.png

4. 負(fù)載因子（load factor）

這里要提到兩個(gè)參數(shù)：初始容量使套，加載因子罐呼，這兩個(gè)參數(shù)是影響hash表性能的重要參數(shù)。
容量： 表示hash表中數(shù)組的長度侦高，初始容量是創(chuàng)建hash表時(shí)的容量嫉柴。
加載因子： 是hash表在其容量自動(dòng)增加之前可以達(dá)到多滿的一種尺度（存儲(chǔ)元素的個(gè)數(shù)），它衡量的是一個(gè)散列表的空間的使用程度奉呛。
loadFactor = 加載因子 / 容量
一般情況下计螺，當(dāng)loadFactor <= 1時(shí)，hash表查找的期望復(fù)雜度為O(1).
對(duì)使用鏈表法的散列表來說瞧壮，負(fù)載因子越大危尿，對(duì)空間的利用更充分，然后后果是查找效率的降低馁痴；如果負(fù)載因子太小谊娇，那么散列表的數(shù)據(jù)將過于稀疏，對(duì)空間造成嚴(yán)重浪費(fèi)罗晕。系統(tǒng)默認(rèn)負(fù)載因子為0.75济欢。

5. 擴(kuò)容

當(dāng)hash表中元素越來越多的時(shí)候，碰撞的幾率也就越來越高（因?yàn)閿?shù)組的長度是固定的）小渊，所以為了提高查詢的效率法褥，就要對(duì)數(shù)組進(jìn)行擴(kuò)容。而在數(shù)組擴(kuò)容之后酬屉，最消耗性能的點(diǎn)就出現(xiàn)了半等，原數(shù)組中的數(shù)據(jù)必須重新計(jì)算其在新數(shù)組中的位置揍愁，并放進(jìn)去，這就是擴(kuò)容杀饵。
什么時(shí)候進(jìn)行擴(kuò)容呢莽囤？當(dāng)表中元素個(gè)數(shù)超過了容量 * loadFactor時(shí)，就會(huì)進(jìn)行數(shù)組擴(kuò)容切距。

6. 集合NSSet朽缎、字典NSDictionary的底層實(shí)現(xiàn)原理

Foundation框架下提供了很多高級(jí)數(shù)據(jù)結(jié)構(gòu)，很多都是和Core Foundation下的相對(duì)應(yīng)谜悟，例如NSSet就是和_CFSet相對(duì)應(yīng)话肖，NSDictionary就是和_CFDictionary相對(duì)應(yīng)。源碼

hash

這里說的hash并不是之前說的hash表葡幸，而是一個(gè)方法最筒。為什么要有hash方法？
這個(gè)問題需要從hash表數(shù)據(jù)結(jié)構(gòu)說起蔚叨，首先看下如何在數(shù)組中查找某個(gè)成員

• 先遍歷數(shù)組中的成員
• 將取出的值與目標(biāo)值比較床蜘，如果相等，則返回改成員

在數(shù)組未排序的情況下缅叠，查找的時(shí)間復(fù)雜度是O(n)（n為數(shù)組長度）悄泥。hash表的出現(xiàn)，提高了查找速度肤粱，當(dāng)成員被加入到hash表中時(shí)弹囚，會(huì)計(jì)算出一個(gè)hash值，hash值對(duì)數(shù)組長度取模领曼，會(huì)得到該成員在數(shù)組中的位置鸥鹉。
通過這個(gè)位置可以將查找的時(shí)間復(fù)雜度優(yōu)化到O(1)，前提是在不發(fā)生沖突的情況下庶骄。
這里的hash值是通過hash方法計(jì)算出來的毁渗，且hash方法返回的hash值最好唯一
和數(shù)組相比，基于hash值索引的hash表查找某個(gè)成員的過程：

• 通過hash值直接查找到目標(biāo)值的位置
• 如果目標(biāo)上有很多相同hash值成員单刁，在利用hash表解決沖突的方式進(jìn)行查找

可以看出優(yōu)勢(shì)比較明顯灸异，最壞的情況和數(shù)組也相差無幾。

hash方法什么時(shí)候被調(diào)用

    NSMutableArray *array1 = [NSMutableArray array];
    [array1 addObject:person1];
    NSMutableArray *array2 = [NSMutableArray array];
    [array2 addObject:person2];
    NSLog(@"array end -------------------------------");
    
    NSMutableSet *set1 = [NSMutableSet set];
    [set1 addObject:person1];
    NSMutableSet *set2 = [NSMutableSet set];
    [set2 addObject:person2];
    NSLog(@"set end -------------------------------");
    
    NSMutableDictionary *dictionaryValue1 = [NSMutableDictionary dictionary];
    [dictionaryValue1 setObject:person1 forKey:@"kKey1"];
    NSMutableDictionary *dictionaryValue2 = [NSMutableDictionary dictionary];
    [dictionaryValue2 setObject:person2 forKey:@"kKey2"];
    NSLog(@"dictionary value end -------------------------------");
    
    NSMutableDictionary *dictionaryKey1 = [NSMutableDictionary dictionary];
    [dictionaryKey1 setObject:@"kValue1" forKey:person1];
    NSMutableDictionary *dictionaryKey2 = [NSMutableDictionary dictionary];
    [dictionaryKey2 setObject:@"kValue2" forKey:person2];
    NSLog(@"dictionary key end -------------------------------");

重寫person的hash方法和copyWithZone方法羔飞，方便查看hash方法是否被調(diào)用：

- (id)copyWithZone:(NSZone *)zone{
    //這里必須是self本身對(duì)象
    return self;
}

- (NSUInteger)hash {
    NSUInteger hash = [super hash];
    NSLog(@"走過 hash：%ld", hash);
    return hash;
}

打印結(jié)果：

 array end -------------------------------
 走過 hash：105553148651392
 走過 hash：105553148651328
 set end -------------------------------
 dictionary value end -------------------------------
 走過 hash：105553148651392
 走過 hash：105553148651328
 dictionary key end -------------------------------

可以了解到：hash方法只在對(duì)象被添加到NSSet和設(shè)置為NSDictionary的key時(shí)被調(diào)用
NSSet添加新成員時(shí)肺樟，需要根據(jù)hash值來快速查找成員，以保證集合中是否已經(jīng)存在該成員逻淌。
NSDictionary在查找key時(shí)么伯，也是利用了key的hash值來提高查找的效率。
這里可以得到這個(gè)結(jié)論：
相等變量的hash結(jié)果總是相同的卡儒，不相等變量的hash結(jié)果有可能相同

NSSet

struct __CFSet {
    CFRuntimeBase _base;
    CFIndex _count;     /* number of values */
    CFIndex _capacity;      /* maximum number of values */
    CFIndex _bucketsNum;    /* number of slots */
    uintptr_t _marker;
    void *_context;     /* private */
    CFIndex _deletes;
    CFOptionFlags _xflags;      /* bits for GC */
    const void **_keys;     /* can be NULL if not allocated yet */
};

根據(jù)數(shù)據(jù)結(jié)構(gòu)可以發(fā)現(xiàn)set內(nèi)部使用了指針數(shù)組來保存keys田柔，可以從源碼中了解到采用的是連續(xù)存儲(chǔ)的方式存儲(chǔ)俐巴。

NSSet添加key，key值會(huì)根據(jù)特定的hash函數(shù)算出hash值硬爆，然后存儲(chǔ)數(shù)據(jù)的時(shí)候欣舵，會(huì)根據(jù)hash函數(shù)算出來的值，找到對(duì)應(yīng)的下標(biāo)摆屯，如果該下標(biāo)下已有數(shù)據(jù)邻遏，開放定址法后移動(dòng)插入糠亩，如果數(shù)組到達(dá)閾值虐骑，這個(gè)時(shí)候就會(huì)進(jìn)行擴(kuò)容，然后重新hash插入赎线。查詢速度就可以和連續(xù)性存儲(chǔ)的數(shù)據(jù)一樣接近O(1)了廷没。

NSDictionary

struct __CFDictionary {
    CFRuntimeBase _base;
    CFIndex _count;     /* number of values */
    CFIndex _capacity;      /* maximum number of values */
    CFIndex _bucketsNum;    /* number of slots */
    uintptr_t _marker;
    void *_context;     /* private */
    CFIndex _deletes;
    CFOptionFlags _xflags;      /* bits for GC */
    const void **_keys;     /* can be NULL if not allocated yet */
    const void **_values;   /* can be NULL if not allocated yet */
};

和上面的集合NSSet相比較，多了一個(gè)指針數(shù)組values垂寥。

通過比較集合NSSet和字典NSDictionary的源碼可以知道兩者實(shí)現(xiàn)的原理差不多颠黎，而字典則用了兩個(gè)數(shù)組keys和values，說明這兩個(gè)數(shù)據(jù)是被分開存儲(chǔ)的滞项。

通過源碼可以看到狭归，當(dāng)有重復(fù)的key插入到字典NSDictionary時(shí)，會(huì)覆蓋舊值文判，而集合NSSet則什么都不做过椎，保證了里面的元素不會(huì)重復(fù)。
大家都知道戏仓，字典里的鍵值對(duì)key-value是一一對(duì)應(yīng)的關(guān)系疚宇，從數(shù)據(jù)結(jié)構(gòu)可以看出，key和value是分別存儲(chǔ)在兩個(gè)不同的數(shù)組里赏殃，這里面是如何對(duì)key敷待、value進(jìn)行綁定的呢？
首先key利用hash函數(shù)算出hash值仁热，然后對(duì)數(shù)組的長度取模榜揖，得到數(shù)組下標(biāo)的位置，同樣將這個(gè)地址對(duì)應(yīng)到values數(shù)組的下標(biāo)抗蠢，就匹配到相應(yīng)的value举哟。 注意到上面的這句話，要保證一點(diǎn)物蝙，就是keys和values這兩個(gè)數(shù)組的長度要一致炎滞。所以擴(kuò)容的時(shí)候，需要對(duì)keys和values兩個(gè)數(shù)組一起擴(kuò)容诬乞。

對(duì)于字典NSDictionary設(shè)置的key和value册赛，key值會(huì)根據(jù)特定的hash函數(shù)算出hash值钠导，keys和values同樣多，利用hash值對(duì)數(shù)組長度取模森瘪，得到其對(duì)應(yīng)的下標(biāo)index牡属，如果下標(biāo)已有數(shù)據(jù)，開放定址法后移插入扼睬，如果數(shù)組達(dá)到閾值逮栅，就擴(kuò)容，然后重新hash插入窗宇。這樣的機(jī)制就把一些不連續(xù)的key-value值插入到能建立起關(guān)系的hash表中措伐。
查找的時(shí)候，key根據(jù)hash函數(shù)以及數(shù)組長度军俊，得到下標(biāo)侥加，然后根據(jù)下標(biāo)直接訪問hash表的keys和values，這樣查詢速度就可以和連續(xù)線性存儲(chǔ)的數(shù)據(jù)一樣接近O(1)了粪躬。

參考文章：筆記-數(shù)據(jù)結(jié)構(gòu)之 Hash（OC的粗略實(shí)現(xiàn)）