? ? ? ? ? ? ? ? ? ? ? ? ?搞iOS的讳嘱，面試官問(wèn)Hash干嘛？原因遠(yuǎn)比我下面要介紹的多
一酿愧、了解hash的重要性
在?iOS開發(fā)中?隨處可見?Hash?的身影沥潭，難道我們不好奇嗎？
下圖只是列出了部分知識(shí)點(diǎn)（Hash在iOS中的應(yīng)用分析整理）
摘自知乎的一句話：
算法嬉挡、數(shù)據(jù)結(jié)構(gòu)钝鸽、通信協(xié)議汇恤、文件系統(tǒng)、驅(qū)動(dòng)等拔恰，雖然自己不寫那些東西因谎，但是了解其原理對(duì)于排錯(cuò)、優(yōu)化自己的代碼有很大幫助仁连，就好比雖然你不設(shè)計(jì)制造汽車蓝角，但如果你了解發(fā)動(dòng)機(jī)、變速器饭冬、安全氣囊等幾項(xiàng)原理，對(duì)于你駕車如何省油揪阶、延長(zhǎng)使用壽命昌抠、保證自身安全有很大好處學(xué)而不思則罔、思而不學(xué)則殆鲁僚，開發(fā)人員就是個(gè)隨波而進(jìn)的行業(yè)炊苫，無(wú)論何時(shí)何地，保持學(xué)習(xí)的深度和廣度對(duì)于自身發(fā)展是很重要的冰沙，誰(shuí)都不想60歲退休了還停留在增刪查改的層面侨艾。
1.1、關(guān)聯(lián)對(duì)象的實(shí)現(xiàn)原理：
詳細(xì)的原理可以查閱其他資料拓挥，這里只介紹一下實(shí)現(xiàn)中使用的基本數(shù)據(jù)結(jié)構(gòu)唠梨。關(guān)聯(lián)對(duì)象采用的是HashMap嵌套HashMap的結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)的，簡(jiǎn)單來(lái)說(shuō)就是根據(jù)對(duì)象從第一個(gè)HashMap中取出存儲(chǔ)對(duì)象所有關(guān)聯(lián)對(duì)象的第二個(gè)HashMap侥啤，然后根據(jù)屬性名從第二個(gè)HashMap中取出屬性對(duì)應(yīng)的值和策略当叭。
設(shè)計(jì)關(guān)聯(lián)對(duì)象的初衷是，通過(guò)傳入 對(duì)象 + 屬性名字 盖灸，就可以找到屬性值蚁鳖。方案設(shè)計(jì)實(shí)現(xiàn)好后，查找一個(gè)對(duì)象的關(guān)聯(lián)對(duì)象的基本步驟：
- 1赁炎、?已知條件一：對(duì)象?醉箕，因此引出第一個(gè)HashMap（AssociationsHashMap），用一個(gè)能唯一代表對(duì)象的值作為key徙垫，用存儲(chǔ)對(duì)象的所有關(guān)聯(lián)對(duì)象的結(jié)構(gòu)（名字：值+策略）作為value
- 2讥裤、?已知條件二：屬性名字?，因此引出第二個(gè)HashMap（ObjectAssociationMap）松邪，用屬性名字作為key坞琴，用屬性名字對(duì)應(yīng)的結(jié)構(gòu)體（值+策略）作為value
參考資料：
iOS底層原理總結(jié) - 關(guān)聯(lián)對(duì)象實(shí)現(xiàn)原理
關(guān)聯(lián)對(duì)象 AssociatedObject 完全解析
1.2、weak的實(shí)現(xiàn)原理：
同樣詳細(xì)的原理可以查閱其他資料逗抑，這里只介紹一下實(shí)現(xiàn)中使用的基本數(shù)據(jù)結(jié)構(gòu)剧辐。weak采用的是一個(gè)全局的HashMap嵌套數(shù)組的結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)的寒亥，銷毀對(duì)象（weak指針指向的對(duì)象）的時(shí)候，根據(jù)對(duì)象從HashMap中找到存放所有指向該對(duì)象的weak指針的數(shù)組荧关，然后將數(shù)組中的所有元素都置為nil溉奕。
weak的最大特點(diǎn)就是在對(duì)象銷毀的時(shí)候，自動(dòng)置nil忍啤，減少訪問(wèn)野指針的風(fēng)險(xiǎn)加勤，這也是設(shè)計(jì)weak的初衷。方案設(shè)計(jì)實(shí)現(xiàn)好后同波，weak指針置nil的基本步驟：
?- 1鳄梅、對(duì)象dealloc的時(shí)候，從全局的HashMap中未檩，根據(jù)一個(gè)唯一代表對(duì)象的值作為key戴尸，找到存儲(chǔ)所有指向該對(duì)象的weak指針的數(shù)組
?- 2、將數(shù)組中的所有元素都置為nil
參考資料：
iOS 底層解析weak的實(shí)現(xiàn)原理（包含weak對(duì)象的初始化冤狡，引用孙蒙，釋放的分析）
1.3、KVO實(shí)現(xiàn)使用的基本數(shù)據(jù)結(jié)構(gòu)
比較復(fù)雜悲雳，一個(gè)對(duì)象可以被n個(gè)對(duì)象觀察挎峦，一對(duì)象的n個(gè)屬性又可以分別被n個(gè)對(duì)象觀察。
詳細(xì)參考：?GNUstep KVC/KVO探索（二）：KVO的內(nèi)部實(shí)現(xiàn)
1.4合瓢、iOS App簽名的原理
一句話：一致性哈希算法 + 非對(duì)稱加解密算法
詳細(xì)參考：?iOS App 簽名的原理
1.5坦胶、對(duì)象的引用計(jì)數(shù)存儲(chǔ)的位置
具體參考 ：蘋果iOS系統(tǒng)源碼思考：對(duì)象的引用計(jì)數(shù)存儲(chǔ)在哪里？--從runtime源碼得到的啟示
if對(duì)象支持TaggedPointer?{
? ? ? ? ? ? ?return直接將對(duì)象的指針值作為引用計(jì)數(shù)返回
} ?elseif設(shè)備是64位環(huán)境?&&?Objective-C2.0{
? ? ? ? ? return對(duì)象isa指針的一部分空間(bits_extra_rc)
} else{
? ? ? ? returnhash表
}
1.6歪玲、Runloop與線程的存儲(chǔ)關(guān)系
線程和 RunLoop 之間是一一（子線程可以沒(méi)有）對(duì)應(yīng)的迁央，其關(guān)系是保存在一個(gè)全局的 Dictionary 里。線程剛創(chuàng)建時(shí)并沒(méi)有 RunLoop滥崩，如果你不主動(dòng)獲取岖圈，那它一直都不會(huì)有。RunLoop 的創(chuàng)建是發(fā)生在第一次獲取時(shí)钙皮，RunLoop 的銷毀是發(fā)生在線程結(jié)束時(shí)蜂科。你只能在一個(gè)線程的內(nèi)部獲取其 RunLoop（主線程除外）。
1.7短条、NSDictionary的原理：
解釋完Hash表后导匣，下面簡(jiǎn)單解釋下
二、哈希表
2.1茸时、哈希表定義
哈希表（hash table贡定，也叫散列表），是根據(jù)鍵（key）直接訪問(wèn)訪問(wèn)在內(nèi)存儲(chǔ)存位置的數(shù)據(jù)結(jié)構(gòu)可都。
哈希表本質(zhì)是一個(gè)數(shù)組缓待，數(shù)組中的每一個(gè)元素成為一個(gè)箱子蚓耽，箱子中存放的是鍵值對(duì)。根據(jù)下標(biāo)index從數(shù)組中取value旋炒。關(guān)鍵是如何獲取index步悠，這就需要一個(gè)固定的函數(shù)（哈希函數(shù)），將key轉(zhuǎn)換成index瘫镇。不論哈希函數(shù)設(shè)計(jì)的如何完美鼎兽，都可能出現(xiàn)不同的key經(jīng)過(guò)hash處理后得到相同的hash值，這時(shí)候就需要處理哈希沖突铣除。
2.2谚咬、哈希表優(yōu)缺點(diǎn)
優(yōu)點(diǎn) ：哈希表可以提供快速的操作。
缺點(diǎn) ：哈希表通常是基于數(shù)組的尚粘，數(shù)組創(chuàng)建后難于擴(kuò)展序宦。 ? ? ? ?也沒(méi)有一種簡(jiǎn)便的方法可以以任何一種順序〔例如從小到大）遍歷表中的數(shù)據(jù)項(xiàng)。
綜上背苦，如果不需要有序遍歷數(shù)據(jù)，井且可以提前預(yù)測(cè)數(shù)據(jù)量的大小潘明。那么哈希表在速度和易用性方面是無(wú)與倫比的行剂。
2.3、哈希查找步驟
?- 1钳降、使用哈希函數(shù)將被查找的鍵映射（轉(zhuǎn)換）為數(shù)組的索引厚宰，理想情況下（hash函數(shù)設(shè)計(jì)合理）不同的鍵映射的數(shù)組下標(biāo)也不同，所有的查找時(shí)間復(fù)雜度為O(1)遂填。但是實(shí)際情況下不是這樣的铲觉，所以哈希查找的第二步就是處理哈希沖突。
?- 2吓坚、處理哈希碰撞沖突撵幽。處理方法有很多，比如拉鏈法礁击、線性探測(cè)法盐杂。
2.4、哈希表存儲(chǔ)過(guò)程：
?- 1哆窿、使用hash函數(shù)根據(jù)key得到哈希值h
?- 2链烈、如果箱子的個(gè)數(shù)為n，那么值應(yīng)該存放在底(h%n)個(gè)箱子中挚躯。h%n的值范圍為[0, n-1]强衡。
?- 3、如果該箱子非空（已經(jīng)存放了一個(gè)值）即不同的key得到了相同的h產(chǎn)生了哈希沖突码荔，此時(shí)需要使用拉鏈法或者開放定址線性探測(cè)法解決沖突漩勤。
hash("張三")?=?23;
hash("李四")?=?30;
hash("王五")?=?23;
2.5感挥、常用哈希函數(shù)：
哈希查找第一步就是使用哈希函數(shù)將鍵映射成索引。這種映射函數(shù)就是哈希函數(shù)锯七。如果我們有一個(gè)保存0-M數(shù)組链快，那么我們就需要一個(gè)能夠?qū)⑷我怄I轉(zhuǎn)換為該數(shù)組范圍內(nèi)的索引（0~M-1）的哈希函數(shù)。哈希函數(shù)需要易于計(jì)算并且能夠均勻分布所有鍵眉尸。比如舉個(gè)簡(jiǎn)單的例子域蜗，使用手機(jī)號(hào)碼后三位就比前三位作為key更好，因?yàn)榍叭皇謾C(jī)號(hào)碼的重復(fù)率很高噪猾。再比如使用身份證號(hào)碼出生年月位數(shù)要比使用前幾位數(shù)要更好霉祸。
在實(shí)際中，我們的鍵并不都是數(shù)字袱蜡，有可能是字符串丝蹭，還有可能是幾個(gè)值的組合等，所以我們需要實(shí)現(xiàn)自己的哈希函數(shù)坪蚁。
?- 1奔穿、直接尋址法
?- 2、數(shù)字分析法
?- 3敏晤、平方取中法
?- 4贱田、折疊法
?- 5、隨機(jī)數(shù)法
?- 6嘴脾、除留余數(shù)法
要想設(shè)計(jì)一個(gè)優(yōu)秀的哈希算法并不容易男摧，根據(jù)經(jīng)驗(yàn)，總結(jié)了需要滿足的幾點(diǎn)要求：
?從哈希值不能反向推導(dǎo)出原始數(shù)據(jù)（所以哈希算法也叫單向哈希算法）译打；
?對(duì)輸入數(shù)據(jù)非常敏感耗拓，哪怕原始數(shù)據(jù)只修改了一個(gè) Bit，最后得到的哈希值也大不相同奏司；
?散列沖突的概率要很小乔询，對(duì)于不同的原始數(shù)據(jù)，哈希值相同的概率非常薪岢巍哥谷；
?哈希算法的執(zhí)行效率要盡量高效，針對(duì)較長(zhǎng)的文本麻献，也能快速地計(jì)算出哈希值们妥。
2.6、負(fù)載因子 = 總鍵值對(duì)數(shù)/數(shù)組的個(gè)數(shù)
負(fù)載因子是哈希表的一個(gè)重要屬性勉吻，用來(lái)衡量哈希表的空/滿程度监婶，一定程度也可以提現(xiàn)查詢的效率。負(fù)載因子越大，意味著哈希表越滿惑惶，越容易導(dǎo)致沖突煮盼，性能也就越低。所以當(dāng)負(fù)載因子大于某個(gè)常數(shù)（一般是0.75）時(shí)带污，哈希表將自動(dòng)擴(kuò)容僵控。哈希表擴(kuò)容時(shí)，一般會(huì)創(chuàng)建兩倍于原來(lái)的數(shù)組長(zhǎng)度鱼冀。因此即使key的哈希值沒(méi)有變化报破，對(duì)數(shù)組個(gè)數(shù)取余的結(jié)果會(huì)隨著數(shù)組個(gè)數(shù)的擴(kuò)容發(fā)生變化，因此鍵值對(duì)的位置都有可能發(fā)生變化千绪，這個(gè)過(guò)程也成為重哈希（rehash）充易。
哈希表擴(kuò)容?在數(shù)組比較多的時(shí)候，需要重新哈希并移動(dòng)數(shù)據(jù)荸型，性能影響較大盹靴。
哈希表擴(kuò)容?雖然能夠使負(fù)載因子降低，但并不總是能有效提高哈希表的查詢性能瑞妇。比如哈希函數(shù)設(shè)計(jì)的不合理稿静，導(dǎo)致所有的key計(jì)算出的哈希值都相同，那么即使擴(kuò)容他們的位置還是在同一條鏈表上辕狰，變成了線性表自赔，性能極低，查詢的時(shí)候時(shí)間復(fù)雜度就變成了O(n)柳琢。
2.7、哈希沖突的解決方法：
方法一：拉鏈法
簡(jiǎn)單來(lái)說(shuō)就是?數(shù)組 + 鏈表?润脸。將鍵通過(guò)hash函數(shù)映射為大小為M的數(shù)組的下標(biāo)索引柬脸，數(shù)組的每一個(gè)元素指向一個(gè)鏈表，鏈表中的每一個(gè)結(jié)點(diǎn)存儲(chǔ)著hash出來(lái)的索引值為結(jié)點(diǎn)下標(biāo)的鍵值對(duì)毙驯。
Java 8解決哈希沖突采用的就是拉鏈法倒堕。在處理哈希函數(shù)設(shè)計(jì)不合理導(dǎo)致鏈表很長(zhǎng)時(shí)（鏈表長(zhǎng)度超過(guò)8切換為紅黑樹，小于6重新退化為鏈表）爆价。將鏈表切換為紅黑樹能夠保證插入和查找的效率垦巴，缺點(diǎn)是當(dāng)哈希表比較大時(shí)，哈希表擴(kuò)容會(huì)導(dǎo)致瞬時(shí)效率降低铭段。
Redis解決哈希沖突采用的也是拉鏈法骤宣。通過(guò)增量式擴(kuò)容解決了Java 8中的瞬時(shí)擴(kuò)容導(dǎo)致的瞬時(shí)效率降低的缺點(diǎn)，同時(shí)拉鏈法的實(shí)現(xiàn)方式（新插入的鍵值對(duì)放在鏈表頭部）帶來(lái)了兩個(gè)好處：
?- 一序愚、頭插法可以節(jié)省插入耗時(shí)憔披。如果插到尾部，則需要時(shí)間復(fù)雜度為O(n)的操作找到鏈表尾部，或者需要額外的內(nèi)存地址來(lái)保存尾部鏈表的位置芬膝。
?- 二望门、頭插法可以節(jié)省查找耗時(shí)。對(duì)于一個(gè)數(shù)據(jù)系統(tǒng)來(lái)說(shuō)锰霜，最新插入的數(shù)據(jù)往往可能頻繁的被查詢筹误。
方法二：開放定址線性探測(cè)法
使用兩個(gè)大小為N的數(shù)組（一個(gè)存放keys，另一個(gè)存放values）癣缅。使用數(shù)組中的空位解決碰撞厨剪，當(dāng)碰撞發(fā)生時(shí)（即一個(gè)鍵的hash值對(duì)應(yīng)數(shù)組的下標(biāo)被兩外一個(gè)鍵占用）直接將下標(biāo)索引加一（index += 1），這樣會(huì)出現(xiàn)三種結(jié)果：
?- 1所灸、未命中（數(shù)組下標(biāo)中的值為空丽惶，沒(méi)有占用）。keys[index] = key爬立，values[index] = value钾唬。
?- 2、命中（數(shù)組下標(biāo)中的值不為空侠驯，占用）抡秆。keys[index] == key，values[index] == value吟策。
?- 3儒士、命中（數(shù)組下標(biāo)中的值不為空，占用）檩坚。keys[index] != key着撩，繼續(xù)index += 1，直到遇到結(jié)果1或2停止匾委。
拉鏈法的優(yōu)點(diǎn)
與開放定址線性探測(cè)法相比拖叙，拉鏈法有如下幾個(gè)優(yōu)點(diǎn)：
- ①、拉鏈法處理沖突簡(jiǎn)單赂乐，且無(wú)堆積現(xiàn)象薯鳍，即非同義詞決不會(huì)發(fā)生沖突，因此平均查找長(zhǎng)度較短挨措；
?- ②挖滤、由于拉鏈法中各鏈表上的結(jié)點(diǎn)空間是動(dòng)態(tài)申請(qǐng)的，故它更適合于造表前無(wú)法確定表長(zhǎng)的情況浅役；
?- ③斩松、開放定址線性探測(cè)法為減少?zèng)_突，要求裝填因子α較小觉既，故當(dāng)結(jié)點(diǎn)規(guī)模較大時(shí)會(huì)浪費(fèi)很多空間砸民。而拉鏈法中可取α≥1，且結(jié)點(diǎn)較大時(shí)，拉鏈法中增加的指針域可忽略不計(jì)岭参，因此節(jié)省空間反惕；
④、在用拉鏈法構(gòu)造的散列表中演侯，刪除結(jié)點(diǎn)的操作易于實(shí)現(xiàn)姿染。只要簡(jiǎn)單地刪去鏈表上相應(yīng)的結(jié)點(diǎn)即可。而對(duì)開放定址線性探測(cè)法構(gòu)造的散列表秒际，刪除結(jié)點(diǎn)不能簡(jiǎn)單地將被刪結(jié) 點(diǎn)的空間置為空悬赏，否則將截?cái)嘣谒筇钊松⒘斜淼耐x詞結(jié)點(diǎn)的查找路徑。這是因?yàn)楦鞣N開放定址線性探測(cè)法中娄徊，空地址單元(即開放地址)都是查找失敗的條件闽颇。因此在用開放定址線性探測(cè)法處理沖突的散列表上執(zhí)行刪除操作，只能在被刪結(jié)點(diǎn)上做刪除標(biāo)記寄锐，而不能真正刪除結(jié)點(diǎn)兵多。
拉鏈法的缺點(diǎn)
指針需要額外的空間，故當(dāng)結(jié)點(diǎn)規(guī)模較小時(shí)，開放定址線性探測(cè)法較為節(jié)省空間，而若將節(jié)省的指針空間用來(lái)擴(kuò)大散列表的規(guī)模喉悴，可使裝填因子變小，這又減少了開放定址線性探測(cè)法中的沖突咖熟，從而提高平均查找速度。
開放定址線性探測(cè)法缺點(diǎn)
?- 1、容易產(chǎn)生堆積問(wèn)題；
?- 2奈懒、不適于大規(guī)模的數(shù)據(jù)存儲(chǔ)；
?- 3宪巨、散列函數(shù)的設(shè)計(jì)對(duì)沖突會(huì)有很大的影響筐赔；
?- 4、插入時(shí)可能會(huì)出現(xiàn)多次沖突的現(xiàn)象揖铜，刪除的元素是多個(gè)沖突元素中的一個(gè)，需要對(duì)后面的元素作處理达皿，實(shí)現(xiàn)較復(fù)雜天吓；
?- 5、結(jié)點(diǎn)規(guī)模很大時(shí)會(huì)浪費(fèi)很多空間峦椰；
2.8龄寞、Hash表的平均查找長(zhǎng)度
Hash表的平均查找長(zhǎng)度包括查找成功時(shí)的平均查找長(zhǎng)度和查找失敗時(shí)的平均查找長(zhǎng)度。
查找成功時(shí)的平均查找長(zhǎng)度=表中每個(gè)元素查找成功時(shí)的比較次數(shù)之和/表中元素個(gè)數(shù)汤功；
查找不成功時(shí)的平均查找長(zhǎng)度相當(dāng)于在表中查找元素不成功時(shí)的平均比較次數(shù)物邑，可以理解為向表中插入某個(gè)元素，該元素在每個(gè)位置都有可能，然后計(jì)算出在每個(gè)位置能夠插入時(shí)需要比較的次數(shù)色解，再除以表長(zhǎng)即為查找不成功時(shí)的平均查找長(zhǎng)度茂嗓。
例子：
給定一組數(shù)據(jù){32，14科阎，23述吸，01，42锣笨，20蝌矛，45，27错英，55入撒，24，10椭岩，53}茅逮，假設(shè)散列表的長(zhǎng)度為13（最接近n的質(zhì)數(shù)），散列函數(shù)為H(k) = k簿煌。分別畫出用 線性探測(cè)法 和 拉鏈法 解決沖突時(shí)構(gòu)造的哈希表氮唯，并求出在等概率下情況，這兩種方法查找成功和查找不成功的平均查找長(zhǎng)度姨伟。
一惩琉、拉鏈法
查找成功時(shí)的平均查找長(zhǎng)度：
1ASL?=?(1*6+2*4+3*1+4*1)/12=?7/4
查找不成功時(shí)的平均查找長(zhǎng)度：
1ASL?=?(4+2+2+1+2+1)/13
二、線性探測(cè)法
查找成功時(shí)查找次數(shù)=插入元素時(shí)的比較次數(shù)夺荒，查找成功的平均查找長(zhǎng)度：
1ASL?=?(1+2+1+4+3+1+1+1+3+9+1+1+3)/12=2.5
查找不成功時(shí)的查找次數(shù)=第n個(gè)位置不成功時(shí)的比較次數(shù)為瞒渠，第n個(gè)位置到第1個(gè)沒(méi)有數(shù)據(jù)位置的距離：如第0個(gè)位置取值為1，第1個(gè)位置取值為2.查找不成功時(shí)的平均查找長(zhǎng)度：
1ASL?=?（1+2+3+4+5+6+7+8+9+10+11+12）/?13=?91/13
2.9技扼、NSDictionary解釋版本一：是使用NSMapTable實(shí)現(xiàn)的伍玖，采用拉鏈法解決哈希沖突
1
2
3
4
5
typedef?struct?{
???NSMapTable????????*table;
???NSInteger??????????i;
???struct?_NSMapNode?*j;
}?NSMapEnumerator;
上述結(jié)構(gòu)體描述了遍歷一個(gè)NSMapTable時(shí)的一個(gè)指針對(duì)象，其中包含table對(duì)象自身的指針剿吻，計(jì)數(shù)值窍箍，和節(jié)點(diǎn)指針。
1
2
3
4
5
6
7
8
typedef?struct?{
???NSUInteger?(*hash)(NSMapTable?*table,constvoid*);
???BOOL?(*isEqual)(NSMapTable?*table,constvoid*,constvoid*);
???void(*retain)(NSMapTable?*table,constvoid*);
???void(*release)(NSMapTable?*table,void*);
???NSString??*(*describe)(NSMapTable?*table,constvoid*);
???constvoid*notAKeyMarker;
}?NSMapTableKeyCallBacks;
上述結(jié)構(gòu)體中存放的是幾個(gè)函數(shù)指針丽旅，用于計(jì)算key的hash值椰棘，判斷key是否相等，retain榄笙，release操作邪狞。
1
2
3
4
5
typedef?struct?{
???void(*retain)(NSMapTable?*table,constvoid*);
???void(*release)(NSMapTable?*table,void*);
???NSString??*(*describe)(NSMapTable?*table,?constvoid*);
}?NSMapTableValueCallBacks;
上述存放的三個(gè)函數(shù)指針，定義在對(duì)NSMapTable插入一對(duì)key－value時(shí)茅撞，對(duì)value對(duì)象的操作帆卓。
1
2
3
4
5
6
7
@interfaceNSMapTable?:?NSObject?{
???NSMapTableKeyCallBacks???*keyCallBacks;
???NSMapTableValueCallBacks?*valueCallBacks;
???NSUInteger?????????????count;
???NSUInteger?????????????nBuckets;
???struct?_NSMapNode??**buckets;
}
從上面的結(jié)構(gòu)真的能看出NSMapTable是一個(gè) 哈希表 + 鏈表 的數(shù)據(jù)結(jié)構(gòu)嗎巨朦？在NSMapTbale中插入或者刪除一個(gè)對(duì)象的尋找時(shí)間 = O(1) + O(m) ，m為最壞時(shí)可能為n剑令。
O(1)?：對(duì)key進(jìn)行hash得到bucket的位置
O(m)?：不同的key得到相同的hash值的value存放到鏈表中糊啡，遍歷鏈表的時(shí)間
上面的結(jié)論和對(duì)應(yīng)的解釋似乎很合理？看看下面的分析再說(shuō)也不遲尚洽！
2.10悔橄、NSDictionary解釋版本二：是對(duì)_CFDictionary的封裝，解決哈希沖突使用的是開放定址線性探測(cè)法
1
2
3
4
5
6
7
8
9
10
11
12
struct?__CFDictionary?{
????CFRuntimeBase?_base;
????CFIndex?_count;
????CFIndex?_capacity;
????CFIndex?_bucketsNum;
????uintptr_t?_marker;
????void*_context;
????CFIndex?_deletes;
????CFOptionFlags?_xflags;
????constvoid**_keys;
????constvoid**_values;
};
從上面的數(shù)據(jù)結(jié)構(gòu)可以看出NSDictionary內(nèi)部使用了兩個(gè)指針數(shù)組分別保存keys和values腺毫。采用的是連續(xù)方式存儲(chǔ)鍵值對(duì)癣疟。拉鏈法會(huì)將key和value包裝成一個(gè)結(jié)果存儲(chǔ)（鏈表結(jié)點(diǎn)），而Dictionary的結(jié)構(gòu)擁有keys和values兩個(gè)數(shù)組（開放尋址線性探測(cè)法解決哈希沖突的用的就是兩個(gè)數(shù)組）潮酒，說(shuō)明兩個(gè)數(shù)據(jù)是被分開存儲(chǔ)的睛挚，不像是拉鏈法。
NSDictionary使用開放定址線性探測(cè)法解決哈希沖突的原理：
可以看到急黎，NSDictionary設(shè)置的key和value扎狱，key值會(huì)根據(jù)特定的hash函數(shù)算出建立的空桶數(shù)組，keys和values同樣多勃教，然后存儲(chǔ)數(shù)據(jù)的時(shí)候淤击，根據(jù)hash函數(shù)算出來(lái)的值，找到對(duì)應(yīng)的index下標(biāo)故源，如果下標(biāo)已有數(shù)據(jù)污抬，開放定址法后移動(dòng)插入，如果空桶數(shù)組到達(dá)數(shù)據(jù)閥值绳军，這個(gè)時(shí)候就會(huì)把空桶數(shù)組擴(kuò)容印机，然后重新哈希插入。
這樣把一些不連續(xù)的key-value值插入到了能建立起關(guān)系的hash表中门驾，當(dāng)我們查找的時(shí)候射赛，key根據(jù)哈希>值算出來(lái)，然后根據(jù)索引奶是，直接index訪問(wèn)hash表keys和hash表values楣责，這樣查詢速度就可以和連續(xù)線性存儲(chǔ)的數(shù)據(jù)一樣接近O(1)了，只是占用空間有點(diǎn)大聂沙，性能就很強(qiáng)悍秆麸。
如果刪除的時(shí)候，也會(huì)根據(jù)_maker標(biāo)記邏輯上的刪除逐纬，除非NSDictionary（NSDictionary本體的hash值就是count）內(nèi)存被移除。
NSDictionary之所以采用這種設(shè)計(jì)削樊，
其一出于查詢性能的考慮豁生；
其二NSDictionary在使用過(guò)程中總是會(huì)很快的被釋放兔毒，不會(huì)長(zhǎng)期占用內(nèi)存;
2.11、Apple方案選擇：
解決哈希沖突的拉鏈法和開放定址線性探測(cè)法甸箱，Apple都是用了育叁。具體使用哪一種是根據(jù)存儲(chǔ)數(shù)據(jù)的生命周期和特性決定的。
@synchronized使用的是拉鏈法芍殖。拉鏈法多用于存儲(chǔ)的數(shù)據(jù)是通用類型豪嗽，能夠被反復(fù)利用，就像@synchronized存儲(chǔ)的是鎖是一種無(wú)關(guān)業(yè)務(wù)的實(shí)現(xiàn)結(jié)構(gòu)豌骏，程序運(yùn)行時(shí)多個(gè)對(duì)象使用同一個(gè)鎖的概率相當(dāng)高龟梦，有效的節(jié)省了內(nèi)存。
weak對(duì)象 associatedObject采用的是開放定址線性探測(cè)法窃躲。開放定址線性探測(cè)法用于存儲(chǔ)的數(shù)據(jù)是臨時(shí)的计贰，用完盡快釋放，就像associatedObject蒂窒，weak躁倒。
2.12、NSDictionary的存儲(chǔ)過(guò)程：
具體參考我寫的另一篇博客：iOS筆記：進(jìn)一步認(rèn)識(shí) ==洒琢、isEqual秧秉、hash
1、通過(guò)方法- (void)setObject:(id)anObject forKey:(id)aKey;可以看出key必須遵循NSCopy協(xié)議衰抑，也就是說(shuō)NSDictionary的key是copy一份新的象迎，而value是淺拷貝的（如果想深拷貝可以使用NSMapTable）。
2停士、不過(guò)這還不夠挖帘，key還必須要繼承NSObject，并且重寫-(NSUInteger)hash;和-(BOOL)isEqual:(id)object;兩個(gè)方法恋技。第一個(gè)函數(shù)用于計(jì)算hash值拇舀，第二個(gè)函數(shù)用來(lái)判斷當(dāng)哈希值相同的時(shí)候value是否相同（解決哈希沖突）。
參考博客
淺談算法和數(shù)據(jù)結(jié)構(gòu): 十一 哈希表
NSDictionary和NSMutableArray底層原理（哈希表和環(huán)形緩沖區(qū)）
iOS重做輪子蜻底，寫一個(gè)NSDictionary（一）
iOS重做輪子骄崩，寫一個(gè)NSDictionary（一）
哈希表——線性探測(cè)法、鏈地址法薄辅、查找成功要拂、查找不成功的平均長(zhǎng)度
細(xì)說(shuō)@synchronized和dispatch_once
鏈接：https://juejin.im/post/5c6abfc86fb9a049c04396a7
