當前位置:成語大全網 - 新華字典 - iOS 字典的實現原理

iOS 字典的實現原理

壹、NSDictionary使用原理

1.NSDictionary(字典)是使用hash表來實現key和value之間的映射和存儲的,hash函數設計的好壞影響著數據的查找訪問效率。

-(void)setObject:(id)anObject forKey:(id)aKey;

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

二、哈希的原理

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

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

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

在使用拉鏈法解決哈希沖突時,每個箱子其實是壹個鏈表,屬於同壹個箱子的所有鍵值對都會排列在鏈表中。

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

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

負載因子越大,意味著哈希表越滿,越容易導致沖突,性能也就越低。因此,壹般來說,當負載因子大於某個常數(可能是1,或者0.75等)時,哈希表將自動擴容。

哈希表在自動擴容時,壹般會創建兩倍於原來個數的箱子,因此即使key的哈希值不變,對箱子個數取余的結果也會發生改變,因此所有鍵值對的存放位置都有可能發生改變,這個過程也稱為重哈希(rehash)。

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

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

1.如果哈希表中本來箱子就比較多,擴容時需要重新哈希並移動數據,性能影響較大。

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

關於hash表

想想壹下,我們有壹個數組,數組長度是100個,現在的需求是:給出這個數組是否包含壹個對象obj?

如果這是個無序的數組,那麽我們只能用遍歷的方法來查找是否包含這個對象obj了。這是我們的時間復雜度就是O(n)。

這種查找效率是很低的,所以hash表應運而生。

hash表其實也是壹個數組,區別數組的地方是它會建立 存儲的值 到 存儲的下標 索引的壹個映射,也就是散列函數。

我們來舉壹個通俗易懂的例子:

現在我們有個hash表,表長度count = 16,現在我們依次把3,12,24,30依次存入hash表中。

首先我們來約定壹個簡單的映射關系:存儲的索引下表(index) = 存儲值(value) % hash表長度(count);

[註:實際的映射並不是簡單的存儲值,而是經過計算得到的hash值]

算下來hash表的存儲分布是這樣的:hash[3] = 3、hash[12] = 12、hash[8] = 24、hash[14] = 30

還是壹樣的需求,當我們給出24的時候,求出hash表中是否存有24?

此時,按照原先約定的映射關系:index = 24 % 16 = 8,然後我們在hash[8]查詢等於24。這樣,通過數組需要O(n)的時間復雜度,通過hash表只需要O(1);

散列碰撞

上面提到的hash表在存入3,12,24,30後,如果要面臨存入19呢?

此時index = 19 % 16 = 3,而之前hash[3] 已經存入了3這個值了!這種情況就是發送了散列碰撞。

此時,我們可以改進壹下我們的hash表,讓它存儲的是壹個鏈表。這樣發送散列碰撞的元素就可以以鏈表的形式***處在hash表的某壹個下標位置了。