Q:哈希表是啥腺律？？
A:0.哈希表的本質(zhì)是一個(gè)數(shù)組古掏，數(shù)組中每一個(gè)元素稱為一個(gè)箱子(bin)损话，箱子中存放的是鍵值對。字典 NSDictionary 底層其實(shí)是一個(gè)哈希表。
0.1 哈希表的存儲過程如下:
- 根據(jù) key 計(jì)算出它的哈希值 h丧枪。
- 假設(shè)箱子的個(gè)數(shù)為 n光涂，那么這個(gè)鍵值對應(yīng)該放在第 (h % n) 個(gè)箱子中。
- 如果該箱子中已經(jīng)有了鍵值對拧烦，就使用開放尋址法或者拉鏈法解決沖突忘闻。
1.每個(gè)箱子其實(shí)是一個(gè)鏈表，屬于同一個(gè)箱子的所有鍵值對都會排列在鏈表中恋博。
2.關(guān)于哈希表擴(kuò)容
- 負(fù)載因子 = 總鍵值對數(shù) / 箱子個(gè)數(shù)
- 負(fù)載因子可能是等于1齐佳，或者0.75時(shí)哈希表將自動(dòng)擴(kuò)容。
- 哈希表在自動(dòng)擴(kuò)容時(shí)债沮，一般會創(chuàng)建兩倍于原來個(gè)數(shù)的箱子炼吴，因此即使 key 的哈希值不變，對箱子個(gè)數(shù)取余的結(jié)果也會發(fā)生改變疫衩，因此所有鍵值對的存放位置都有可能發(fā)生改變缺厉，這個(gè)過程也稱為重哈希(rehash)。
- 哈希表的擴(kuò)容并不總是能夠有效解決負(fù)載因子過大的問題隧土。假設(shè)所有 key 的哈希值都一樣提针，那么即使擴(kuò)容以后他們的位置也不會變化。雖然負(fù)載因子會降低曹傀，但實(shí)際存儲在每個(gè)箱子中的鏈表長度并不發(fā)生改變辐脖，因此也就不能提高哈希表的查詢性能。
3.總結(jié)
- 如果哈希表中本來箱子就比較多皆愉，擴(kuò)容時(shí)需要重新哈希并移動(dòng)數(shù)據(jù)嗜价，性能影響較大。
- 如果哈希函數(shù)設(shè)計(jì)不合理幕庐，哈希表在極端情況下會變成線性表久锥，性能極低。
n_n
