哈希表, 也叫散列表, 是數(shù)組的一種擴(kuò)展
把關(guān)鍵字或者鍵轉(zhuǎn)換為數(shù)組下標(biāo)的方法叫做散列函數(shù)
散列函數(shù)計(jì)算得到的值也叫做散列值或hash值

散列沖突

解決散列沖突的方法: 開放尋址法 和 鏈表法

開放尋址法

1. 線性探測
   如果數(shù)據(jù)經(jīng)過散列函數(shù)散列后, 存儲位置被占用了, 我們就從當(dāng)前位置開始, 依
   次往后查找, 看是否有空閑位置, 直到找到為止

   對于刪除操作, 不能單純地把要?jiǎng)h除的元素置位空, 因?yàn)槿绻@個(gè)空閑的位置是
   后來刪除的, 就會導(dǎo)致原來的查找算法失效, 本來存在的數(shù)據(jù), 會認(rèn)定為不存在,
   這個(gè)問題的話, 我們可以將刪除的元素特殊標(biāo)記為 deleted, 遇到標(biāo)記 deleted的
   空間, 并不是停下來, 而是繼續(xù)往下探測

   所以, 散列表插入的數(shù)據(jù)越來越多時(shí), 散列沖突發(fā)生的可能性就會越來越大, 空
   閑的位置會越來越少, 線性探測的時(shí)間會越來越久. 極端情況下, 需要探測整個(gè)
   散列表, 所以最壞情況下的時(shí)間復(fù)雜度是 O(n)

2. 二次探測
   線性探測每次探測的步長是 1, hash(key) + 0, hash(key) + 1, 二次探測的步長變?yōu)槎畏? hash(key) + 0, hash(key) + 1^2, hash(key) + 2^2

3. 雙重散列
   不僅使用一個(gè)散列函數(shù), 還要使用一組散列函數(shù) hash1(key), hash2(key), hash3(key).... 優(yōu)先使用第一個(gè)函數(shù), 如果有沖突, 就用第二個(gè)散列函數(shù)

不管哪種探測方法, 散列表中空閑位置不多的時(shí)候, 散列沖突概率會大大提高。 需要盡可能保證散列表的操作效率, 一般情況下, 保證一定比例的空閑槽位。用裝載因子來表示空位的多少

    裝載因子 = 填入表的元素個(gè)數(shù) / 散列表的長度

鏈表法

所有散列值相同的元素都放到相同槽位對應(yīng)的鏈表中, 插入的時(shí)候只需要通過散列函數(shù)計(jì)算出對應(yīng)的槽位, 將其插入到對應(yīng)的鏈表中即可， 所以插入的時(shí)間復(fù)雜度是 O(1)