6.1 散列表的概念

散列表又叫哈希（hash）表，是根據鍵（key）直接訪問在內存存儲位置的值（value）的數據結構，由數組演化而來（根據數組支持按照下標進行隨機訪問數據的特性）。

eg：有一組數據2023ZHBJ001、2023ZHBJ002、...、2023ZHBJ100。其中2023代表年份，zh代表中國，bj代表北京，001代表選手編號，此時這一串數據就代表一個選手

那么此時，我們如何將這一串數據轉換為key存進數組作為數組下標呢？此時我們介紹下面這個方法散列函數。

6.2 散列函數

概念:將key映射為數組下標的函數就叫散列函數。可以表示成hashvalue=hash（key）。

散列函數的要求：

1.散列函數計算得到的key值必須是大于等于0的正整數，因為hashvalue要作為數組下標。

2.如果key1==key2，那么經過hash后得到的hash值也必須相等：hash（key1）==hash（key2）。

3.如果key1 ！= key2，那么經過hash后得到的hash值也必須不相等：hash（key1）！=hash（key2）。

注:第三點不太好實現，因為實際情況下想找一個散列函數能夠做到對于不同key計算得到的散列值不相同是幾乎不可能的，這就是散列沖突。

6.3 散列沖突（哈希碰撞、哈希沖突）

概念：多個key值映射到同一個數組下標，這就是散列沖突。

那么如何解決這個呢，就要介紹到下面的拉鏈法。

6.4 拉鏈法

在散列表中，數組每個下標的位置我們稱之為桶（bucket）或者槽（slot），每個桶（槽）都對應一個鏈表，所有的散列值相同的元素都存進相同槽位對應的鏈表中。這樣就做到了讓多個hash值相同的元素存到同一個索引下，這就解決了hash沖突

6.5 拉鏈法時間復雜度

6.5.1 插入

通過散列函數計算出對應散列槽位，將其插入進對應散列槽位即可，時間復雜度是O（1）；

插入流程：根據key經過hash計算得到數組索引，然后將數據掛到索引上，這樣不需要遍歷，只需要計算就可完成，效率比較高，所以時間復雜度是O（1）。

6.5.2 刪除、查找

當查找、刪除時，同樣是先通過hash計算得到數組索引，然后遍歷對應槽位的鏈表進行查找刪除。

6.5.2.1 一般情況下

基于鏈表法解決沖突時查詢的時間復雜度時O（1）。因為鏈表中數據并不多

6.5.2.2 特殊情況下

當數據量夠多，產生了大量的hash沖突，就會將數據掛到同一索引下，導致某一個槽位的鏈表很長，那么此時散列表就退化成了鏈表，當再去這個索引下查找元素時，就要遍歷鏈表，所以時間復雜度為O（n）。

6.5.2.3 第三種情況下

當鏈表過長時，將鏈表法中的鏈表改造為其他高效的數據結構，比如紅黑樹，這樣遍歷時時間復雜度為O（logn）。

注：將鏈表改為紅黑樹的一個重要原因也是為了防止DDos攻擊（分布式拒絕服務攻擊）。

可以理解為，有人惡意偽造key，造成大量hash沖突，就會在數組索引中產生大量鏈表，就會導致訪問散列表的效率很低。