文章目錄

• 前言
• • 關(guān)聯(lián)對象的底層原理
  • weak的實現(xiàn)原理
  • KVO的實現(xiàn)原理
  • iOS App簽名的原理
  • 對象引用計數(shù)存儲的位置
  • Runloop與線程的存儲關(guān)系
  • NSDictionary的原理
• 哈希表
• • 哈希表定義
  • 哈希表優(yōu)缺點
  • 哈希查找步驟
  • 哈希表的存儲過程
  • 哈希表的實現(xiàn)
  • 負載因子 = 總鍵值對數(shù)/數(shù)組的個數(shù)
  • 哈希沖突的解決方法
  • • 開散列
    • 閉散列
    • 再哈希法
    • 建立公共溢出區(qū)
    • 開閉散列二者的比較
    • • 拉鏈法的優(yōu)點：
      • 拉鏈法的缺點：
      • 線性探測法的缺點
• NSDictionary

前言

天天聽安卓的同學(xué)整Hash，猛的發(fā)現(xiàn)iOS也有很多底層原理也是Hash來實現(xiàn)的，好好學(xué)一下。

iOS中也用到了很多Hash表。

關(guān)聯(lián)對象的底層原理

[iOS開發(fā)]Category、Extension和關(guān)聯(lián)對象

關(guān)聯(lián)對象采用的是HashMap嵌套HashMap的結(jié)構(gòu)存儲數(shù)據(jù)的，簡單來說就是根據(jù)對象從第一個HashMap中取出存儲所有關(guān)聯(lián)對象的第二個HashMap，然后根據(jù)屬性名從第二個HashMap中取出屬性對應(yīng)的值和策略。

問題：為什么關(guān)聯(lián)對象沒有weak屬性？

weak的實現(xiàn)原理

weak底層原理

weak采用的是一個全局的HashMap嵌套數(shù)組的結(jié)構(gòu)存儲數(shù)據(jù)的。銷毀對象(weak指針指向的對象)的時候，根據(jù)對象從HashMap中找到存放所有指向該對象的weak指針的數(shù)組，然后將數(shù)組中的所有元素（weak指針）都置為nil

weak最大的特點就是在對象銷毀的時候，自動置nil，減少訪問野指針的風險，這也是設(shè)計weak的初衷。weak指針置nil的基本步驟：

• 對象dealloc的時候，從全局的HashMap中，根據(jù)一個唯一代碼對象的值作為key，找到存儲所有指向該對象的weak指針的數(shù)組
• 將數(shù)組中的所有元素都置nil

蘋果對于weak的實現(xiàn)其實類似于通知的實現(xiàn)，指明誰（weak指針）要監(jiān)聽誰（賦值對象）什么事件（dealloc操作）執(zhí)行什么操作（置nil）

KVO的實現(xiàn)原理

GNUstep KVC/KVO探索（二）：KVO的內(nèi)部實現(xiàn)

iOS App簽名的原理

一致性Hash算法 + 非對稱加密算法

iOS App 簽名的原理

對象引用計數(shù)存儲的位置

if 對象支持TaggedPointer {return 直接將對象的指針值作為引用計數(shù)返回 } else if 設(shè)備是64位環(huán)境 && Objective-C2.0 {return 對象isa指針的一部分空間(bits_extra_rc) } else {return hash表 }

Runloop與線程的存儲關(guān)系

線程和Runloop之間是一一對應(yīng)的關(guān)系，其關(guān)系是保存在一個全局的Dictionary里。

線程在剛創(chuàng)建是沒有RunLoop,如果我們不主動獲取，那他就一直都不會有。RunLoop的創(chuàng)建是發(fā)生在第一次獲取時，RunLoop的銷毀時發(fā)生在線程結(jié)束時。我們只能在一個線程內(nèi)部獲取其RunLoop。

NSDictionary的原理

學(xué)完Hash之后我們來學(xué)習具體的實現(xiàn)

哈希表

前面說了那么多的底層原理都與Hash表有關(guān)，我們來詳細學(xué)一下哈希表

哈希表定義

哈希表(hash tabl，也叫散列表），是根據(jù)鍵(key)直接訪問在內(nèi)存存儲位置的數(shù)據(jù)結(jié)構(gòu)。哈希表本質(zhì)是一個數(shù)組，數(shù)組中的每一個元素成為一個箱子，箱子中存放的是鍵值對。根據(jù)下標index從數(shù)組中取value。關(guān)鍵是如何獲取index，這就需要一個固定的函數(shù)（哈希函數(shù)），將key轉(zhuǎn)換成index。不論哈希函數(shù)設(shè)計的如何完美，都可能出現(xiàn)不同的key經(jīng)過hash處理后得到相同的hash值，這時候我們就需要處理哈希沖突。

哈希表優(yōu)缺點

優(yōu)點：把數(shù)據(jù)的存儲和查找消耗的時間大大降低，幾乎可以看成是常數(shù)時間；而代價僅僅是消耗比較多的內(nèi)存。然而在當前可利用內(nèi)存越來越多的情況下，用空間換時間的做法是值得的。另外，編碼比較容易也是它的特點之一。

缺點：哈希表通常是基于數(shù)組，數(shù)組創(chuàng)建后難于擴展。也沒有一種簡便的方法可以以任何一種順序來遍歷哈希表。

所以，如果不需要有序遍歷數(shù)據(jù)，并且可以提前預(yù)測數(shù)據(jù)量的大小，那么哈希表在速度和易用性方面是無與倫比的。

哈希查找步驟

使用哈希函數(shù)將被查找的鍵轉(zhuǎn)換為數(shù)組的索引，理想情況下（hash函數(shù)設(shè)計合理）不同的鍵映射的數(shù)組下標也不同，所有的查找時間復(fù)雜度為O(1)。但是實際情況下不是這樣的，所以哈希查找的第二部就是處理哈希沖突。

處理哈希沖突有很多方法，比如拉鏈法、線性探測法…

哈希表的存儲過程

使用hash函數(shù)根據(jù)key得到哈希值h

如果箱子的個數(shù)為n，那么值應(yīng)該存放在底(h%n)個箱子中。h%n的值范圍為[0,n-1]。

如果該箱子非空（已經(jīng)存放了一個值）即不同的key得到了相同的h產(chǎn)生了哈希沖突，此時需要使用拉鏈法或者開放定址線性探測法解決沖突

哈希表的實現(xiàn)

哈希表的底層實際上是基于數(shù)組來存儲的，當插入鍵值對時，并不是直接插入該數(shù)組中，而是通過對鍵進行Hash運算得到Hash值，然后和數(shù)組容量取模，得到在數(shù)組中的位置后再插入。取值時，先對指定的鍵求Hash值，再和容量取模得到底層數(shù)組中對應(yīng)的位置，如果指定的鍵值與存貯的鍵相匹配，則返回該鍵值對，如果不匹配，則表示哈希表中沒有對應(yīng)的鍵值對。這樣做的好處是在查找、插入、刪除等操作可以做到 O ( 1 ) O(1) O(1)，最壞的情況是 O ( n ) O(n) O(n)，當然這種是最極端的情況，極少遇到。

負載因子 = 總鍵值對數(shù)/數(shù)組的個數(shù)

負載因子是哈希表的一個重要屬性，用來衡量哈希表的空/滿成都，一定程度也可以體現(xiàn)查詢的效率。負載因子越大，意味著哈希表越滿，越容易導(dǎo)致沖突，性能也就越低。所以當負載因子大于某個常數(shù)（一般是0.75）時，哈希表將自動擴容。哈希表擴容是，一般會創(chuàng)建兩倍于原來的數(shù)組長度。這個過程被稱為重哈希(rehash)。

哈希表擴容在數(shù)組比較多的時候需要重新哈希并移動數(shù)據(jù)，性能影響較大。

哈希表擴容雖然能夠使負載因子降低，但并不總能有效提高哈希表的查詢性能。比如哈希函數(shù)設(shè)計的不合理，導(dǎo)致所有的key計算出的哈希值都相同，那么即使擴容他們的位置還是在同一條鏈表上，變成了線性表，性能也極低，查詢時候的時間復(fù)雜度就變成了O(n)。

哈希沖突的解決方法

大類分為四種 開散列、閉散列、再哈希法、建立公共溢出區(qū)

開散列

開散列也叫鏈地址法，也叫拉鏈法、哈希桶。

簡單來說就是 數(shù)組 + 鏈表。將鍵通過hash函數(shù)映射為大小為M的數(shù)組的下標索引，數(shù)組的每一個元素指向一個鏈表，鏈表中的每一個節(jié)點都存儲著hash出來的索引值為結(jié)點下標的鍵值對。

JAVA 8解決哈希沖突采用的就是拉鏈法。在處理哈希函數(shù)設(shè)計不合理導(dǎo)致鏈表很長時（鏈表長度超過8切換為紅黑樹，小于6重新退化為鏈表）。將鏈表切換為紅黑樹能夠保證插入和查找的效率，缺點是當哈希表比較大時，哈希表擴容會導(dǎo)致瞬時效率降低。

Redis解決哈希沖突采用的也是拉鏈法。通過增量式擴容解決了java 8中的瞬時擴容導(dǎo)致的瞬時效率降低的缺點，同時拉鏈法的實現(xiàn)方式（新插入的鍵值對放在鏈表頭部）帶來了兩個好處：
一、 頭插法可以節(jié)省插入耗時。如果插到尾部，則需要時間復(fù)雜度為O(n)的操作找到鏈表的尾部，或者需要額外的內(nèi)存地址來保存尾部鏈表的位置。
二、頭插法可以節(jié)省查找耗時。最新插入的數(shù)據(jù)往往可能頻繁的被查詢。

閉散列

閉散列也叫開放地址法、線性探測法。

當發(fā)生哈希沖突時，且哈希表未滿，可以通過探測的方法吧key存放在沖突位置的下一個位置中。

方法一：線性探測
從發(fā)生沖突的位置開始，一次向后探測，直到尋找到下一個空位置為止。當然這種方法比較簡單，也有很大的缺陷，就是容易造成數(shù)據(jù)的堆積，使得關(guān)鍵字需要多次比較，這樣以來就導(dǎo)致搜索效率低

方法二：二次探測

方法三：偽隨機探測
建立一個偽隨機數(shù)發(fā)生器（如 i = (i + p) % m），生成一個偽隨機序列，并給定一個隨機數(shù)做起點，每次加上這個偽隨機數(shù)，++就可以了。

再哈希法

再哈希法其實很簡單，就是再使用哈希函數(shù)去散列一個輸入的時候，輸出是同一個位置就再次哈希，直至不發(fā)生沖突位置

缺點：每次沖突都要重新哈希，計算時間增加。

建立公共溢出區(qū)

這種方法的基本思想是：將哈希表分為基本表和溢出表兩部分，凡是和基本表發(fā)生沖突的元素，一律填入溢出表。

開閉散列二者的比較

拉鏈法的優(yōu)點：

與線性探測法相比，拉鏈法有如下幾個優(yōu)點：

• 處理沖突簡單，且無堆積現(xiàn)象，即非同義詞絕不會發(fā)生沖突，因此平均查找長度較短；
• 由于拉鏈法中各鏈表上的結(jié)點空間是動態(tài)申請的，所以更適合于造表錢無法確定表長的情況
• 線性探測法為減少沖突，要求裝填因子較小，故當結(jié)點規(guī)模較大時會浪費很多空間。二拉鏈法中可取a>=1，且結(jié)點較大時，拉鏈法中增加的指針域可忽略不計，因此節(jié)省空間
• 在用拉鏈法構(gòu)造的散列表中，刪除結(jié)點的操作易于實現(xiàn)。只要簡單地刪去鏈表上相應(yīng)的結(jié)點即可。而對開放定址線性探測發(fā)構(gòu)造的散列表，刪除結(jié)點不能簡單地將被刪結(jié) 點的空間置為空，否則將截斷在它之后填人散列表的同義詞結(jié)點的查找路徑。這是因為各種開放定址線性探測發(fā)中，空地址單元(即開放地址)都是查找失敗的條件。因此在用開放定址線性探測發(fā)處理沖突的散列表上執(zhí)行刪除操作，只能在被刪結(jié)點上做刪除標記，而不能真正刪除結(jié)點。

拉鏈法的缺點：

指針需要額外的空間，故當結(jié)點規(guī)模較小時，開放定址線性探測法較為節(jié)省空間，而若將節(jié)省的指針空間用來擴大散列表的規(guī)模，可使裝填因子變小，這又減少了開放定址線性探測法中的沖突，從而提高平均查找速度。

線性探測法的缺點

容易產(chǎn)生堆積問題

不適于大規(guī)模的數(shù)據(jù)存儲

散列函數(shù)的設(shè)計對沖突會有很大的影響

插入時可能會出現(xiàn)多次沖突的現(xiàn)象，刪除的元素是多個沖突元素中的一個，需要對后面的元素作處理，實現(xiàn)較復(fù)雜

結(jié)點規(guī)模很大時會浪費很多空間

NSDictionary

總結(jié)

以上是生活随笔為你收集整理的[iOS开发]iOS中的Hash的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。