當前位置:成語大全網 - 漢語詞典 - iOS詞典的實現原理

iOS詞典的實現原理

壹、NSDictionary的使用原則

1.NSDictionary使用哈希表實現鍵和值的映射和存儲,哈希函數的設計影響數據的查找和訪問效率。

-(void)set object:(id)an object forKey:(id)aKey;

2.Objective-C中的字典NSDictionary實際上是壹個哈希表。事實上,大多數語言的詞典都是通過哈希表來實現的。

二、哈希原理

1.根據密鑰計算其哈希值H。

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

3.如果盒子裏已經有壹個鍵-值對,使用開放尋址方法或者zipper方法解決沖突。

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

哈希表還有壹個重要的屬性:負載因子,用來衡量哈希表的空/滿程度,也能在壹定程度上反映查詢的效率。計算公式為:

負載系數=總鍵值對數/盒子數量

負載因子越大,哈希表越滿,越容易引起沖突,性能越低。因此,壹般來說,當負載系數大於某個常數(可能是1,也可能是0.75等)時。),哈希表會自動展開。

哈希表自動擴展時,壹般會創建兩倍於原來數量的盒,所以即使鍵的哈希值不變,取剩余數量的盒的結果也會發生變化,所以所有鍵-值對的存儲位置都可能發生變化,這個過程也叫重散列。

哈希表的擴展並不總能有效解決加載因子過大的問題。假設所有鍵的哈希值都是相同的,那麽即使在擴展之後,它們的位置也不會改變。雖然裝載因子會降低,但是每個盒子實際存儲的鏈表長度不會改變,所以哈希表的查詢性能無法提升。

第四,綜上所述,細心的讀者可能會發現哈希表的兩個問題:

1.如果哈希表中有很多盒子,擴展時需要重新哈希和移動數據,對性能影響很大。

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

在哈希表上

想想看,我們有壹個長度為100的數組。現在的需求是:這個數組包含對象obj嗎?

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

這種搜索效率很低,於是哈希表應運而生。

哈希表實際上是壹個數組,數組的區別在於它會建立存儲值和存儲下標索引之間的映射,也就是哈希函數。

我們舉個簡單易懂的例子:

現在我們有了壹個散列表,表長度為count = 16。現在我們將3,12,24,30依次存儲在哈希表中。

先約定壹個簡單的映射關系:存儲索引表(index) =存儲值(value)%哈希表長度(count);

[註意:實際的映射不是簡單的存儲值,而是計算出的哈希值]

哈希表的存儲分布如下:hash[3] = 3,hash[12] = 12,hash[8] = 24,hash[14] = 30。

還是那個要求,當我們給24的時候,我們有沒有發現哈希表裏有沒有24?

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

哈希沖突

如果上面說的哈希表存儲在3,12,24,30之後的19會怎麽樣?

此時index = 19% 16 = 3,hash[3]已經存儲了3的值!在這種情況下,會發送哈希沖突。

此時,我們可以改進我們的哈希表,使其存儲壹個鏈表。這樣,發送哈希沖突的元素可以在鏈表形式的哈希表的下標位置。