3.NSDictionary底層實(shí)現(xiàn)原理
筆者自語：當(dāng)有一個面試官問我NSDictionary底層實(shí)現(xiàn)原理钱磅，我平時開發(fā)的時候只是會用而已，哪里知道它的內(nèi)部實(shí)現(xiàn)原理呀检眯，一臉懵逼的樣子骑晶，感覺跟那個面試的人相差甚遠(yuǎn)匾浪，現(xiàn)在有空來系統(tǒng)整理一下我自己對NSDictionary內(nèi)部實(shí)現(xiàn)原理的理解，真的理解了對你只有好處沒有壞處匈睁，永遠(yuǎn)不要說我會用就完了监透，那只是初級開發(fā)工程師的要求不是嗎？廢話不多說航唆，希望各位引起重視胀蛮。
一言以蔽之：在OC中NSDictionary是使用hash表來實(shí)現(xiàn)key和value的映射和存儲的。
那么問題來了什么是hash表呢糯钙？
哈希表（hash表）：又叫做散列表醇滥，是根據(jù)關(guān)鍵碼值（key value）而直接訪問的數(shù)據(jù)結(jié)構(gòu)。也就是說它通過關(guān)鍵碼值映射到表中一個位置來訪問記錄超营，以加快查找的速度鸳玩。這個映射叫做函數(shù)，存放記錄的數(shù)組叫做哈希表演闭。
讀到此處我們得到一個關(guān)鍵信息：所謂哈希表就是一個數(shù)組不跟，數(shù)組中每一個元素稱為一個箱子（bin），箱子中存放的是鍵值對米碰∥迅铮看一個示意圖就一目了然了：
hash表存儲過程簡單介紹：
- 根據(jù)key值計算出它的hash值h；
- 假設(shè)箱子的個數(shù)是n吕座，那么鍵值對應(yīng)該放在第（h%n）個箱子中虐译。
- 如果該箱子中已經(jīng)有了鍵值對，就是用開放尋址法或者拉鏈法解決沖突吴趴。使用拉鏈法解決哈希沖突時漆诽，每個箱子其實(shí)是一個鏈表，屬于同一個箱子的所有鍵值對都會排列在鏈表中锣枝。
依此我們得出結(jié)論：OC中的字典其實(shí)是一個數(shù)組厢拭，數(shù)組中每一個元素同樣為一個鏈表實(shí)現(xiàn)的數(shù)組，也就是數(shù)組中套數(shù)組撇叁。
那么對應(yīng)在oc中字典是如何進(jìn)行存儲的呢供鸠？
在oc中每一個對象創(chuàng)建時，都默認(rèn)生成一個hashCode,也就是經(jīng)過hash算法生成的一串?dāng)?shù)字陨闹，當(dāng)利用key去取字典中的value時楞捂，若是使用遍歷或者二分查找等方法薄坏，效率相對較低，于是出現(xiàn)了根據(jù)每一個key生成的hashCode將鍵值對放到hasCode對應(yīng)的數(shù)組中的指定位置寨闹，這樣當(dāng)用key去取值時胶坠，便不必遍歷去獲取，既可以根據(jù)hashCode直接取出鼻忠。因為hashCode的值過大涵但，或許經(jīng)過取余獲取一個較小的數(shù)字杈绸，假如是對999進(jìn)行取余運(yùn)算帖蔓，那么得到的結(jié)果始終處于0-999之間。但是瞳脓，這樣做的弊端在于取余所得到的值塑娇，可能是相同的，這樣可能導(dǎo)致完全不相干的鍵值對被新的鍵值對（取余后值key相等）所覆蓋劫侧，于是出現(xiàn)了數(shù)組中套鏈表實(shí)現(xiàn)的數(shù)組埋酬。這樣，key值取余得到值相等的鍵值對烧栋，都將保存在同一個鏈表數(shù)組中写妥，當(dāng)查找key對應(yīng)的值時，首先獲取到該鏈表數(shù)組审姓，然后遍歷數(shù)組珍特，取正確的key所對應(yīng)的值即可。
至此NSDictionary的底層原理算是基本上講透徹了魔吐，希望對看到者有一定的啟示作用扎筒，那么筆者就心滿意足了。
