一、散列表的由來？

1.散列表來源于數組，它借助散列函數對數組這種數據結構進行擴展，利用的是數組支持按照下標隨機訪問元素的特性。
2.需要存儲在散列表中的數據我們稱為鍵，將鍵轉化為數組下標的方法稱為散列函數，散列函數的計算結果稱為散列值。
3.將數據存儲在散列值對應的數組下標位置。

二、如何設計散列函數？

總結3點設計散列函數的基本要求
1.散列函數計算得到的散列值是一個非負整數。
2.若key1=key2，則hash(key1)=hash(key2)
3.若key≠key2，則hash(key1)≠hash(key2)
正是由于第3點要求，所以產生了幾乎無法避免的散列沖突問題。

三、散列沖突的解放方法？

1.常用的散列沖突解決方法有2類：開放尋址法（open addressing）和鏈表法（chaining）
2.開放尋址法
①核心思想：如果出現散列沖突，就重新探測一個空閑位置，將其插入。
②線性探測法（Linear Probing）：
插入數據：當我們往散列表中插入數據時，如果某個數據經過散列函數之后，存儲的位置已經被占用了，我們就從當前位置開始，依次往后查找，看是否有空閑位置，直到找到為止。
查找數據：我們通過散列函數求出要查找元素的鍵值對應的散列值，然后比較數組中下標為散列值的元素和要查找的元素是否相等，若相等，則說明就是我們要查找的元素；否則，就順序往后依次查找。如果遍歷到數組的空閑位置還未找到，就說明要查找的元素并沒有在散列表中。
刪除數據：為了不讓查找算法失效，可以將刪除的元素特殊標記為deleted，當線性探測查找的時候，遇到標記為deleted的空間，并不是停下來，而是繼續往下探測。
結論：最壞時間復雜度為O(n)
③二次探測（Quadratic probing）：線性探測每次探測的步長為1，即在數組中一個一個探測，而二次探測的步長變為原來的平方。
④雙重散列（Double hashing）：使用一組散列函數，直到找到空閑位置為止。
⑤線性探測法的性能描述：
用“裝載因子”來表示空位多少，公式：散列表裝載因子=填入表中的個數/散列表的長度。
裝載因子越大，說明空閑位置越少，沖突越多，散列表的性能會下降。
3.鏈表法（更常用）

插入數據：當插入的時候，我們需要通過散列函數計算出對應的散列槽位，將其插入到對應的鏈表中即可，所以插入的時間復雜度為O(1)。
查找或刪除數據：當查找、刪除一個元素時，通過散列函數計算對應的槽，然后遍歷鏈表查找或刪除。對于散列比較均勻的散列函數，鏈表的節點個數k=n/m，其中n表示散列表中數據的個數，m表示散列表中槽的個數，所以是時間復雜度為O(k)。

四、如何設計散列函數？

要盡可能讓散列后的值隨機且均勻分布，這樣會盡可能減少散列沖突，即便沖突之后，分配到每個槽內的數據也比較均勻。

除此之外，散列函數的設計也不能太復雜，太復雜就會太耗時間，也會影響到散列表的性能。

常見的散列函數設計方法：直接尋址法、平方取中法、折疊法、隨機數法等。

五、如何根據裝載因子動態擴容？

1.如何設置裝載因子閾值？
①可以通過設置裝載因子的閾值來控制是擴容還是縮容，支持動態擴容的散列表，插入數據的時間復雜度使用攤還分析法。
②裝載因子的閾值設置需要權衡時間復雜度和空間復雜度。如何權衡？如果內存空間不緊張，對執行效率要求很高，可以降低裝載因子的閾值；相反，如果內存空間緊張，對執行效率要求又不高，可以增加裝載因子的閾值。
2.如何避免低效擴容？分批擴容
①分批擴容的插入操作：當有新數據要插入時，我們將數據插入新的散列表，并且從老的散列表中拿出一個數據放入新散列表。每次插入都重復上面的過程。這樣插入操作就變得很快了。
②分批擴容的查詢操作：先查新散列表，再查老散列表。
③通過分批擴容的方式，任何情況下，插入一個數據的時間復雜度都是O(1)。

六、如何選擇散列沖突解決方法？

①常見的2中方法：開放尋址法和鏈表法。
②大部分情況下，鏈表法更加普適。而且，我們還可以通過將鏈表法中的鏈表改造成其他動態查找數據結構，比如紅黑樹、跳表，來避免散列表時間復雜度退化成O(n)，抵御散列沖突攻擊。
③但是，對于小規模數據、裝載因子不高的散列表，比較適合用開放尋址法。

七、為什么散列表和鏈表經常放在一起使用？

數組占據隨機訪問的優勢，卻有需要連續內存的缺點。
鏈表具有可不連續存儲的優勢，但訪問查找是線性的。
散列表和鏈表、跳表的混合使用，是為了結合數組和鏈表的優勢，規避它們的不足。

我們可以得出數據結構和算法的重要性排行榜：連續空間 > 時間 > 碎片空間。
1.散列表的優點：支持高效的數據插入、刪除和查找操作
2.散列表的缺點：不支持快速順序遍歷散列表中的數據
3.如何按照順序快速遍歷散列表的數據？只能將數據轉移到數組，然后排序，最后再遍歷數據。
4.我們知道散列表是動態的數據結構，需要頻繁的插入和刪除數據，那么每次順序遍歷之前都需要先排序，這勢必會造成效率非常低下。
5.如何解決上面的問題呢？就是將散列表和鏈表（或跳表）結合起來使用。

八、散列表和鏈表如何組合起來使用？

1.LRU（Least Recently Used）緩存淘汰算法
1.1.LRU緩存淘汰算法主要操作有哪些？主要包含3個操作：
①往緩存中添加一個數據；
②從緩存中刪除一個數據；
③在緩存中查找一個數據；
④總結：上面3個都涉及到查找。
1.2.如何用鏈表實現LRU緩存淘汰算法？
①需要維護一個按照訪問時間從大到小的有序排列的鏈表結構。
②緩沖空間有限，當空間不足需要淘汰一個數據時直接刪除鏈表頭部的節點。
③當要緩存某個數據時，先在鏈表中查找這個數據。若未找到，則直接將數據放到鏈表的尾部。若找到，就把它移動到鏈表尾部。
④前面說了，LRU緩存的3個主要操作都涉及到查找，若單純由鏈表實現，查找的時間復雜度很高為O(n)。若將鏈表和散列表結合使用，查找的時間復雜度會降低到O(1)。
1.3.如何使用散列表和鏈表實現LRU緩存淘汰算法？
①使用雙向鏈表存儲數據，鏈表中每個節點存儲數據（data）、前驅指針（prev）、后繼指針（next）和hnext指針（解決散列沖突的鏈表指針）。

pre和next組成雙向鏈表，這個鏈表是按照緩存的時間由大到小，組成的一個緩存隊列；對于hnext作用是，在最新時間插入緩存數據時，通過哈希函數得出的沖突，用其連接。
總結：在雙向鏈表中，時間是從大到小；在hnext組成的拉鏈中，時間從左到右依次變小。

②散列表通過鏈表法解決散列沖突，所以每個節點都會在兩條鏈中。一條鏈是雙向鏈表，另一條鏈是散列表中的拉鏈。前驅和后繼指針是為了將節點串在雙向鏈表中，hnext指針是為了將節點串在散列表的拉鏈中。
③LRU緩存淘汰算法的3個主要操作如何做到時間復雜度為O(1)呢？
首先，我們明確一點就是鏈表本身插入和刪除一個節點的時間復雜度為O(1)，因為只需更改幾個指針指向即可。
接著，來分析查找操作的時間復雜度。當要查找一個數據時，通過散列表可實現在O(1)時間復雜度找到該數據，再加上前面說的插入或刪除的時間復雜度是O(1)，所以我們總操作的時間復雜度就是O(1)。
2.Redis有序集合
2.1.什么是有序集合？
①在有序集合中，每個成員對象有2個重要的屬性，即key（鍵值）和score（分值）。
②不僅會通過score來查找數據，還會通過key來查找數據。
2.2.有序集合的操作有哪些？
舉個例子，比如用戶積分排行榜有這樣一個功能：可以通過用戶ID來查找積分信息，也可以通過積分區間來查找用戶ID。這里用戶ID就是key，積分就是score。所以，有序集合的操作如下：
①添加一個對象；
②根據鍵值刪除一個對象；
③根據鍵值查找一個成員對象；
④根據分值區間查找數據，比如查找積分在[100.356]之間的成員對象；
⑤按照分值從小到大排序成員變量。
這時可以按照分值將成員對象組織成跳表結構，按照鍵值構建一個散列表。那么上面的所有操作都非常高效。
3.Java LinkedHashMap
和LRU緩存淘汰策略實現一模一樣。支持按照插入順序遍歷數據，也支持按照訪問順序遍歷數據。

N、思考

1.Word文檔中單詞拼寫檢查功能是如何實現的？
字符串占用內存大小為8字節，20萬單詞占用內存大小不超過20MB，所以用散列表存儲20萬英文詞典單詞，然后對每個編輯進文檔的單詞進行查找，若未找到，則提示拼寫錯誤。
2.假設我們有10萬條URL訪問日志，如何按照訪問次數給URL排序？

遍歷 10 萬條數據，以 URL 為 key，訪問次數為 value，存入散列表，同時記錄下訪問次數的最大值 K，時間復雜度 O(N)。

如果 K 不是很大，可以使用桶排序，時間復雜度 O(N)。如果 K 非常大（比如大于 10 萬），就使用快速排序，復雜度 O(NlogN)。

3.有兩個字符串數組，每個數組大約有10萬條字符串，如何快速找出兩個數組中相同的字符串？
分別將2個數組的字符串通過散列函數映射到散列表，散列表中的元素值為次數。注意，先存儲的數組中的相同元素值不進行次數累加。最后，統計散列表中元素值大于等于2的散列值對應的字符串就是兩個數組中相同的字符串。

4. 如何設計一個工業級的散列函數？
思路：
何為一個工業級的散列表？工業級的散列表應該具有哪些特性？結合學過的知識，我覺的應該有這樣的要求：

支持快速的查詢、插入、刪除操作；

內存占用合理，不能浪費過多空間；

性能穩定，在極端情況下，散列表的性能也不會退化到無法接受的情況。

方案：
如何設計這樣一個散列表呢？根據前面講到的知識，我會從3個方面來考慮設計思路：
1.設計一個合適的散列函數；
2.定義裝載因子閾值，并且設計動態擴容策略；
3.選擇合適的散列沖突解決方法。

6.在你熟悉的編程語言中，哪些數據類型底層是基于散列表實現的？散列函數是如何設計的？散列沖突是通過哪種方法解決的？

JDK hashMap源碼，hash表中數組位置的計算分兩步：
1.計算hash值：

int hash(Object key) {int h = key.hashCode()；return (h ^ (h >>> 16)) & (capicity -1); //capicity表示散列表的大小 }

這一步有一種說法，叫它擾動函數，為什么要右移16位再與本身異或呢？
1.1 首先hashCode()返回值int最高是32位，如果直接拿hashCode()返回值作為下標，大概40億的映射空間，只要哈希函數映射得比較均勻松散，一般是很難出現碰撞的。
問題是一個40億長度的數組，內存是放不下的。
1.2 所以，用自己的高半區和低半區做異或，混合原始哈希碼的高位和低位，關鍵是以此來加大低位的隨機性。為后續計算index截取低位，保證低位的隨機性。
1.3 這樣設計保證了對象的hashCode的32位值只要有一位發生改變，整個hash()返回值就會改變，高位的變化會反應到低位里，保證了hash值的隨機性。

2.在插入或查找的時候，計算Key被映射到桶的位置：

int index = hash(key) & (capacity - 1)

hash()擾動函數計算的值和hash表當前的容量減一，做按位與運算。
這一步，為什么要減一，又為什么要按位與運算？
因為A % B = A & (B - 1)，當B是2的指數時，等式成立。
本質上是使用了「除留余數法」，保證了index的位置分布均勻。

為什么HashMap的數組長度必須是2的整次冪？
數組長度是2的整次冪時，（數組長度-1）正好相當于一個低位掩碼，“與”操作的結果就是散列值的高位全部歸零，只保留低位值，用來做數組下標訪問。

以初始長度16為例，16-1=15。2進制表示是00000000 00000000 00001111。“與”操作的結果就是截取了最低的四位值。也就相當于取模操作。

7.今天講的幾個散列表和鏈表結合使用的例子里，我們用的都是雙向鏈表。如果把雙向鏈表改成單鏈表，還能否正常工作呢？為什么呢？
在刪除一個元素時，雖然能 O(1) 的找到目標結點，但是要刪除該結點需要拿到前一個結點的指針，遍歷到前一個結點復雜度會變為 O(N），所以用雙鏈表實現比較合適。

（但其實硬要操作的話，單鏈表也是可以實現 O(1) 時間復雜度刪除結點的）。

8.假設獵聘網有 10 萬名獵頭，每個獵頭都可以通過做任務（比如發布職位）來積累積分，然后通過積分來下載簡歷。假設你是獵聘網的一名工程師，如何在內存中存儲這 10 萬個獵頭 ID 和積分信息，讓它能夠支持這樣幾個操作：
根據獵頭的 ID 快速查找、刪除、更新這個獵頭的積分信息；
查找積分在某個區間的獵頭 ID 列表；
查找按照積分從小到大排名在第 x 位到第 y 位之間的獵頭 ID 列表。
以獵頭 ID 構建一個散列表[{ID ：積分}]；再用積分先構建一個跳表，再用積分跳表和獵頭 ID 數組構建一個復合散列表[{積分 : [ID數組]}]。
1）在散列表中可以 O(1) 時間復雜度查找、刪除、更新獵頭ID 對應的積分數據；
2）積分以跳表存儲，跳表支持按區間查詢；
3）使用快速排序法在 O(N) 時間復雜度內分別求出跳表中排名在第 x 位和第 y 位的積分大小，再通過復合散列表得到排名在第 x 位的積分到第 y 位的積分之間所有積分對應所有獵頭 ID 數組中的 ID。

總結

以上是生活随笔為你收集整理的【数据结构与算法】散列表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。