什么是哈希表?
哈希表也叫散列表，是一個(gè)根據(jù)鍵(key)直接訪問在內(nèi)存存儲(chǔ)位置的數(shù)據(jù)結(jié)構(gòu)
通過計(jì)算一個(gè)關(guān)于鍵值的函數(shù)，將所需查詢的數(shù)據(jù)映射到表中一個(gè)位置來訪問記錄，這種方式加快了查找速度。而這個(gè)映射函數(shù)稱作散列函數(shù)，存放記錄的數(shù)組稱作散列表
本質(zhì)上來說是個(gè)數(shù)組，實(shí)現(xiàn)哈希表的兩種方式：
- 數(shù)組+鏈表
- 數(shù)組+二叉樹
一般數(shù)組里存放的是單一的數(shù)據(jù)，而哈希表中存放的是鍵值對(duì)
數(shù)據(jù)經(jīng)過散列函數(shù)計(jì)算之后，放到特定的位置
entry就是鍵值對(duì)，只是不同的叫法
哈希沖突
數(shù)據(jù)經(jīng)過散列函數(shù)計(jì)算之后，指定在同一個(gè)位置上，就是哈希沖突
處理哈希沖突
1.開放尋址法
當(dāng)計(jì)算出來的位置已經(jīng)有數(shù)據(jù)了，就順著位置往后找沒有數(shù)據(jù)的位置放數(shù)據(jù)
2.拉鏈法
在原來的entry中額外保存一個(gè)next指針，指向數(shù)組的另外一個(gè)位置放置新數(shù)據(jù)
哈希表的擴(kuò)容
當(dāng)哈希表被占用的位置比較多的時(shí)候，出險(xiǎn)沖突的概率也就變高了，就會(huì)進(jìn)行擴(kuò)容
哈希表的擴(kuò)容不是簡單的擴(kuò)大，而是新創(chuàng)建一個(gè)數(shù)組是原來的2倍，然后把原來數(shù)組的所有entry都重新經(jīng)過新的哈希函數(shù)計(jì)算一邊再存放到新的位置上
哈希表如何讀取數(shù)據(jù)
- 通過key利用哈希函數(shù)得出位置，然后去對(duì)應(yīng)位置拿出數(shù)據(jù)，比較key，如果不對(duì)則根據(jù)next對(duì)比下一個(gè)位置的key
- 開放尋址法則是按順序去下一個(gè)位置對(duì)比
