iOS NSDictionary(字典)~實作原理

   聯系人:石虎 QQ:1224614774  昵稱: 嗡嘛呢叭咪哄

                      QQ群:807236138  群稱: iOS 技術交流學習群

一、NSDictionary使用原理

    1.NSDictionary（字典）是使用 hash表來實作key和value之間的映射和存儲的， hash函數設計的好壞影響着資料的查找通路效率。

    - (void)setObject:(id)anObject forKey:(id <NSCopying>)aKey;

   2.Objective-C 中的字典 NSDictionary 底層其實是一個哈希表，實際上絕大多數語言中字典都通過哈希表實作，

二、哈希的原理

   哈希概念:哈希表的本質是一個數組，數組中每一個元素稱為一個箱子(bin)，箱子中存放的是鍵值對。

三、哈希表的存儲過程:

    1. 根據 key 計算出它的哈希值 h。

    2. 假設箱子的個數為 n，那麼這個鍵值對應該放在第 (h % n) 個箱子中。

    3. 如果該箱子中已經有了鍵值對，就使用開放尋址法或者拉鍊法解決沖突。

    在使用拉鍊法解決哈希沖突時，每個箱子其實是一個連結清單，屬于同一個箱子的所有鍵值對都會排列在連結清單中。

    哈希表還有一個重要的屬性: 負載因子(load factor)，它用來衡量哈希表的 空/滿 程度，一定程度上也可以展現查詢的效率，計算公式為:

    負載因子 = 總鍵值對數 / 箱子個數

    負載因子越大，意味着哈希表越滿，越容易導緻沖突，性能也就越低。是以，一般來說，當負載因子大于某個常數(可能是 1，或者 0.75 等)時，哈希表将自動擴容。

重哈希概念:    

    哈希表在自動擴容時，一般會建立兩倍于原來個數的箱子，是以即使 key 的哈希值不變，對箱子個數取餘的結果也會發生改變，是以所有鍵值對的存放位置都有可能發生改變，這個過程也稱為重哈希(rehash)。

    哈希表的擴容并不總是能夠有效解決負載因子過大的問題。假設所有 key 的哈希值都一樣，那麼即使擴容以後他們的位置也不會變化。雖然負載因子會降低，但實際存儲在每個箱子中的連結清單長度并不發生改變，是以也就不能提高哈希表的查詢性能。

四、總結，細心的讀者可能會發現哈希表的兩個問題:

   1. 如果哈希表中本來箱子就比較多，擴容時需要重新哈希并移動資料，性能影響較大。

   2. 如果哈希函數設計不合理，哈希表在極端情況下會變成線性表，性能極低。

謝謝!!!