# 散列表 ## 定義 > 根據鍵（Key）直接訪問在內存存儲位置的數據結構 ## 實現原理 > 通過散列函數（也叫哈希函數）將元素的鍵映射為數組下標（轉化后的值叫做散列值或哈希值），然后在對應下標位置存儲記錄值。當我們按照鍵值查詢元素時，就是用同樣的散列函數，將鍵值轉化數組下標，從對應的數組下標的位置取數據： >  > 散列表用的是數組支持按照下標隨機訪問數據的特性，所以散列表其實就是數組的一種擴展，由數組演化而來。可以說，如果沒有數組，就沒有散列表。而 PHP 的關聯數組干脆就是基于散列表實現。 > 散列技術既是一種存儲方法，也是一種查找方法。與之前的查找方法不同的是散列技術的記錄之間不存在邏輯關系，因此主要是面向查找的數據結構。最適合求解的問題是查找給定值相等的記錄。 ## 散列函數 > 散列函數用于將鍵值經過處理后轉化為散列值。具有以下特性： > * 散列函數計算得到的散列值是非負整數 > * 如果key1 == key2，則hash(key1)==hash(key2) > * 如果key1!=key2,則hash(key1)!=hash(key2) ## 散列沖突 > 簡單來說，指的是key1 != key2的情況下，通過散列函數處理，hash(key1)==hash(key2),這個時候，我們說發生了散列沖突。設計再好的散列函數也無法避免散列沖突，原因是散列值是非負整數，總量是有限的，但是現實世界中要處理的鍵值是無限的，將無限的數據映射到有限的集合，肯定避免不了沖突。 ## 散列沖突解決 > 昨天我們分享了散列表的實現，對 PHPer 來說，應該對散列表很熟悉，因為我們每天用的數組就是基于散列表實現的。比如 $arr\['test'\] = 123 這段代碼，PHP底層會將鍵值 test 通過散列函數轉化為散列碼，然后將 123 映射到這個散列碼上。在不考慮哈希沖突的情況下，散列表查找、刪除、插入的時間復雜度都是 O(1)，非常高效。 > > > > 要減少哈希沖突，提高散列表操作效率，設計一個優秀的散列函數至關重要，我們平時經常使用的 md5 函數就是一個散列函數，但是其實還有其他很多自定義的設計實現，要根據不同場景，設計不同的散列函數來減少散列沖突，而且散列函數本身也要很簡單，否則執行散列函數本身會成為散列表的瓶頸。我們日常很少會自己去設計散列函數，但是做一些簡單的了解還是有必要的。 > 通常有以下幾種散列函數構造方法： > 1. 直接定址法：即 f(key) = a\*key + b，f表示散列函數，a、b是常量，key是鍵值 > 2. 數字分析法：即對數字做左移、右移、反轉等操作獲取散列值 > 3. 除數留余法：即 f(key) = key % p，p 表示容器數量，這種方式通常用在將數據存放到指定容器中，如何決定哪個數據放到哪個容器，比如分表后插入數據如何處理（此時p表示拆分后數據表的數量），分布式Redis如何存放數據（此時p表示幾臺Redis服務器） > 4. 隨機數法：即 f(key) = random(key)，比如負載均衡的random機制 >以上只是一些比較場景的散列函數設計思路，還有很多其他的設計方法，這里就不一一列舉了。 > 我們在上篇分享中提到，設計再好的散列函數也不能完全避免散列沖突，我們只能優化自己的實現讓散列沖突盡可能少出現罷了，如果出現了散列沖突，該如何處理呢？下面給出一些思路： > 1. 開放尋址法：該方法又可以細分為三種 —— 線性尋址、二次探測、隨機探測。線性尋址表示出現散列沖突之后，就去尋找下一個空的散列地址；線性尋址步長是1，二次探測步長是線性尋址步長的2次方，其它邏輯一樣；同理，隨機探測每次步長隨機。不管哪種探測方法，散列表中空閑位置不多的時候，散列沖突的概率就會提高，為了保證操作效率，我們會盡可能保證散列表中有一定比例的空閑槽位，我們用裝載因子來表示空位的多少，裝載因子=填入元素/散列表長度，裝載因子越大，表明空閑位置越少，沖突越多，散列表性能降低。 > 2. 再散列函數法：發生散列沖突后，換一個散列函數計算散列值 > 3. 鏈地址法：發生散列沖突后，將對應數據鏈接到該散列值映射的上一個值之后，即將散列值相同的元素放到相同槽位對應的鏈表中。鏈地址法即使在散列沖突很多的情況下，也可以保證將所有數據存儲到散列表中，但是也引入了遍歷單鏈表帶來性能損耗。 > 介紹完以上內容之后，想必你對如何打造工業級散列表已經心中有數。主要考慮因素包含以下幾個方面： > 散列函數設置合理，不能太過復雜，成為性能瓶頸； > > 設置裝載因子閾值，支持動態擴容，裝載因子閾值設置要充分權衡時間、空間復雜度； > > 如果一次性擴容耗時長，可采取分批擴容的策略，達到閾值后只申請空間，不搬移數據，以后每插入一條數據，搬移一個舊數據，最后逐步完成搬移，期間為了兼容新老散列表查詢，可以先查新表，再查老表； > > 散列沖突解決辦法：開發尋址法在數據量較小、裝載因子小的時候（小于1）選用；鏈表法可以容忍裝載因子大于1，適合存儲大對象、大數據量的散列表，且更加靈活，支持更多優化策略