壹、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表的某壹個下標位置了。