資料結構 - 散串列

簡介

散串列也被稱為哈希表，其具體實作就是使用到了散列技術，

散列技術是在記錄的存盤位置和它的關鍵字之間建立一個確定的對應關系，使得每個關鍵字對應一個存盤位置，

關鍵字

散串列一般都是用在查找的時候，所以，需要存盤的原始資料被稱作是查找的關鍵字，

哈希演算法

散列技術的關鍵在于將關鍵字與存盤位置建立對應關系，這種建立映射關系的規則被稱作哈希演算法，

一般的哈希演算法都是將任意長度的二進制值串映射為固定長度的二進制值串，而這個固定長度的二進制值串可以匹配上存盤位置，

哈希值

通過原始資料映射之后得到的二進制值串就是哈希值，

裝載因子

哈希沖突是非常常見的，因此，在此基礎上增加了一個裝載因子的概念，用來表示散串列中空位的多少，其計算公式為：

散串列的裝載因子 = 填入表中的元素個數 / 散串列的長度

裝載因子越大，說明空閑位置越少，沖突越多，散串列的性能會下降，

構造方法

散串列利用了陣列支持使用下標快速隨機訪問資料的特性，散串列是由陣列演化而來，可以理解為散串列其實就是陣列的一種擴展，可以說，如果沒有陣列，就沒有散串列，

散串列通常是基于陣列實作的，而相比陣列，它還存在創建、洗掉、查找都非常快的優勢，無論資料量多大，這些操作都接近于 \(O(1)\) 的時間復雜度；但相對也存在一些劣勢，散串列中的資料沒有順序，而且不能在同一存盤地址存盤重復的哈希值，

不管是什么編程語言，實作一個散串列資料結構的程序都可以分為三個步驟：

1. 實作一個哈希演算法；
2. 合理解決哈希沖突；
3. 實作其他操作方法，

哈希演算法

一個好的哈希演算法對于散串列是非常重要的，是散串列具有比較優的時間復雜度和空間復雜度的根本，而好的哈希演算法需要具備兩個原則：快速計算和均勻分布，

特點

具體來說，實作一個好的哈希演算法會有以下特點：

• 哈希演算法的方向是單向的，從哈希值不能反向推匯出原始資料
• 哈希演算法的轉換是敏感的，原始資料任何一點變動，得到的哈希值都會大不相同
• 哈希沖突的概率要極小的，不同的原始資料，經過哈希演算法得到的哈希值相同的概率很小
• 哈希演算法的執行效率是高效的，即使是很長的文本也能快速計算出哈希值

直接定址法

直接定址法就是取關鍵字的某個線性函式值作為哈希值，或者使用這個線性函式值經過特定的演算法計算出哈希值，

例如，存盤中國每一年的人數時，可以將年份作為計算哈希值的線性函式值，可以想象得到，年份是連續的，并且沒有沖突，非常適合用來計算哈希值，

直接定址法的優點就是簡單、分布均勻、不會出現沖突，其缺點也很明顯，就是要求選定的線性函式值分布均勻、不會出現沖突，

換一種角度看，直接定址法是有限制的，這個哈希演算法并不常用，

數字分析法

數字分析法的核心就是從原始資料中選取一個辨識度較大的資料作為計算哈希演算法的關鍵字，比較常見的就是用于處理關鍵字位數比較大的數字，

數字分析法有個比較常見的場景，國內的手機號都是 11 位的數字，而且也常見到將中間 4 位數字隱藏的做法，這個其實就是數字分析法的一種用法，因為 11 位手機號的前 3 位是運營商接入號，中間 4 位是歸屬地識別號，后 4 位是用戶號，當手機號碼都在同一個地區時，只需要使用前 3 位和后 4 位就可以作為哈希演算法的關鍵字，

數字分析法也是一種相對簡單的哈希演算法，但一般針對較大數字，如果這些較大數字分布均勻的話，可以選用這個方法，

平方取中法

平方取中法的規則如其名，假設關鍵字是 1234，計算得到它的平方就是 1522756，再抽取中間三位 227 可以作為哈希值；假設關鍵字是 4321，計算得到它的平方就是 18671041，抽取中間三位 671 或 710 作為哈希值即可，

平方取中法比較適合不知道關鍵字的分布、而位數又不是很大的情況，

折疊法

折疊法主要是將關鍵字從左到右分割成位數相等的幾部分，然后將這幾部分疊加求和，并根據散串列的長度，取后幾位作為哈希值，

比如，對 9876543210 使用折疊法，假設散串列表長為三位，將 9876543210 分成 987|654|321|0 這樣四組，然后對這四組使用 987+654+321+0 疊加求和計算得到 1962，再取 1962 的后三位作為哈希值，

折疊法的應用場景可以和平方取中法互補，適合用在不知道關鍵字的分布，而位數較多的情況，

除留取余法

除留取余法是最常用的哈希演算法之一，實際就是對關鍵字求模取余數，這個余數就是哈希值，但是這種方法得到的哈希值非常容易沖突，這個方法的關鍵就是要選擇合適的除數，

根據前輩們的經驗，通常這個除數選取小于等于散串列表長的最大質數或不包含小于 20 質因子的合數，

合數是指在大于 1 的整數中除了能被 1 和本身整除外，還能被其他數（0 除外）整除的數，與之相對的是質數，而 1 既不屬于質數也不屬于合數，最小的合數是 4，

哈希沖突

設計得再好的哈希演算法也很難完全避免沖突，從散串列出現到現在，也出現了很多解決哈希沖突的常規方法，

開放定址法

所謂開放定址法就是，一旦發生了沖突，就去尋找下一個空的存盤地址，只要散串列足夠大，空的存盤地址總能被找到，并將資料存入，

像是這種尋找下一個空的存盤地址的常用方法就是線性探測法，即一個一個去尋找，直至找到下一個空的存盤地址，但是這種方法在哈希沖突比較多的時候，散串列的時間復雜度會慢慢下降到 \(O(n)\)，

除了線性探測法，還有二次探測、雙重哈希的方法，

二次探測就是將線性探測為 1 的步長改成平方的步長，例如，在線性探測中是 hash(key) + 0, hash(key) + 1, hash(key) + 2，二次探測就是 hash(key) + 0, hash(key) + \(1^2\)、hash(key) + \(2^2\)，

雙重哈希指的是使用多個哈希演算法，如果第一個哈希演算法出現沖突，就使用第二個哈希演算法，以此類推，直至找到空閑的存盤位置，

當資料量和裝載因子都比較小的時候，適合采用開放尋址法，這也是 Java 中 ThreadLocalMap 使用開放尋址法解決散列沖突的原因，

鏈地址法

鏈地址法是另一種更加常用的哈希沖突解決辦法，

開放定址法是在原散串列上再次找到存盤位置，而鏈地址法是在出現哈希沖突之后，將這些出現沖突的關鍵字存盤到鏈表中，具體的存盤結構如下圖所示：

這個方法相對于開放地址法來說多了鏈表這種資料結構，對于會出現很多沖突的哈希演算法來說，提供了絕不會出現找不到地址的保障，

雖然這個方法在插入時沒有明顯提升性能損耗，但是帶來了查找、洗掉時需要遍歷單向鏈表的性能損耗，

鏈地址法在查找時耗費的時間取決于鏈表的長度，可以將時間復雜度理解成 \(O(k)\)(k 為鏈表長度)，

針對于這樣的劣勢，一般是使用紅黑樹代替鏈表，Java 中的 HashMap 便是如此，

公共溢位區法

公共溢位區法可以理解為鏈地址法的集中方式，

公共溢位區法也是需要使用到另外的存盤區域，但不像鏈地址法中會將這個存盤區域鏈到鏈表上，而是使用一個單獨的存盤區域存盤所有沖突的關鍵字，

這個公共的溢位區可以是另外一個散串列，對沖突的關鍵字再次哈希進行存盤，

應用場景

這里的應用場景可以分為散串列的應用場景和哈希演算法的應用場景，

對于散串列，使用它主要是為了提升時間復雜度；對于哈希演算法，使用它是為了應用它的特點，

安全加密

常見的加密演算法使用的都是哈希演算法，如 MD5、SHA 等，因為哈希演算法不可逆和轉換敏感的特點，使用哈希演算法的安全性非常好，

唯一標識

比如 URL 欄位或者圖片欄位要求不能重復，這個時候就可以通過對相應欄位值做 MD5 處理，將資料統一為 32 位長度，對資料庫索引構建和查詢提升非常明顯，

此外，還可以對檔案之類的二進制資料做 MD5 處理，作為唯一標識，這樣判定重復檔案的時候更快捷，

資料校驗

比如從網上下載的很多檔案（尤其是 P2P 站點資源），都會包含一個 MD5 值，用于校驗下載資料的完整性，避免資料在中途被劫持篡改，

負載均衡

利用散串列代替映射表，可以實作一個會話粘滯的負載均衡策略，

對客戶端 IP 地址或者會話 ID 計算哈希值，將取得的哈希值與服務器串列的大小進行取模運算，最終得到的值就是應該被路由到的服務器編號，

資料分片

通過散串列對處理的海量資料進行分片，多機分布式處理，可以突破單機資源的限制，

經典案例

MD5

MD5 訊息摘要演算法是一種被廣泛使用的散列函式，可以產生出一個 128 位（16 位元組）的散列值，用于確保資訊傳輸完整一致，

MD5 是輸入不定長度資訊，輸出固定長度 128 位的演算法，無論是多長的資訊，經程序式流程，都會生成四個 32 位資料，最后聯合起來成為一個 128 位散列值，

但是在 2009 年，中國科學院的謝濤和馮登國僅用了 \(22^{0.96}\) 的碰撞演算法復雜度，破解了 MD5 的碰撞抵抗，該攻擊在普通計算機上運行只需要數秒鐘，2011 年，RFC 6151 禁止將 MD5 用作密鑰散列訊息認證碼，

SHA

安全散列演算法 SHA 是一個密碼散列函式家族，是 FIPS 所認證的安全散列演算法，這是能計算出一個數字訊息所對應到的、長度固定的字串（又稱訊息摘要）的演算法，且若輸入的訊息不同，它們對應到不同字串的幾率很高，

SHA 家族演算法包含了 SHA-0、SHA-1、SHA-2、SHA-3，對 SHA-0 和 SHA-1 都已經出現理論上破解的方法，現在比較常見的還是 SHA-2，雖然至今尚未出現對 SHA-2 有效的攻擊，但它的演算法跟 SHA-1 基本上相似，

SHA-3 是在 2015 年正式發布的，由于對 MD5 出現成功的破解，NIST 感覺需要一個與之前演算法不同的、可替換的加密散列演算法，也就是現在的 SHA-3，

CRC

回圈冗余校驗 CRC 是一種根據網路資料包或計算機檔案等資料產生簡短固定位數校驗碼的一種信道編碼技術，主要用來檢測或校驗資料傳輸或者保存后可能出現的錯誤，它是利用除法及余數的原理來作錯誤偵測的，

由于 CRC 演算法檢驗的檢錯能力極強，且檢測成本較低，因此在對于編碼器和電路的檢測中使用較為廣泛，從檢錯的正確率與速度、成本等方面，都比奇偶校驗等校驗方式具有優勢，因而 CRC 成為計算機資訊通信領域最為普遍的校驗方式，

工業級散串列實作

Java 中的 HashMap 是一個非常經典的工業級散串列實作，理解它的實作可以加深對散串列的印象，有興趣可以看一下 HashMap 的原始碼，

初始大小

HashMap 默認的初始大小是 16，當然這個默認值是可以設定的，如果事先知道大概的資料量有多大，可以通過修改默認初始大小，減少動態擴容的次數，這樣能大大提高 HashMap 的性能，

散串列的容量要取 2 的整次冪，因為這樣正好相當于一個低位掩碼，在 hash() 方法內可以做到高位歸零，

裝載因子和動態擴容

HashMap 默認的最大裝載因子是 0.75，當 HashMap 中元素個數超過 0.75 * capacity(capacity 表示散串列的容量)的時候，就會啟動擴容，每次擴容都會擴容為原來的兩倍大小，

散列函式

散列函式的設計并不復雜，追求的是簡單高效、分布均勻，HashMap 散列函式的原始碼如下：

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

在 Java 中，hashCode 方法通過將物件的物理地址轉換為一個整數，再將整數通過哈希演算法計算得到哈希碼，這個哈希碼是一個 32 位的帶符號整數值，正常情況下很難發生碰撞，

為了讓這個哈希碼與 HashMap 的底層陣列做映射，Java 還會將這個哈希碼再次做哈希操作，采用的方法是：

1. 將哈希碼右移 16 位，正好是 32bit 的一半；
2. 將哈希碼的高半區和低半區做異或，可以混合哈希碼的高位和低位，以此加大低位的隨機性；
3. 將計算結果做高位歸零，只保留低位值，

散列沖突解決方法

HashMap 底層采用鏈地址法來解決沖突，即使負載因子和散列函式設計得再合理，也免不了會出現拉鏈過長的情況，一旦出現拉鏈過長，則會嚴重影響 HashMap 的性能，

于是，在 JDK1.8 版本中，為了對 HashMap 做進一步優化引入了紅黑樹，

當鏈表長度太長（默認超過 8）時，鏈表就轉換為紅黑樹，這是利用了紅黑樹快速增刪改查的特點，提高 HashMap 的性能，

當紅黑樹結點個數少于 8 個的時候，又會將紅黑樹轉化為鏈表，這是因為在資料量較小的情況下，紅黑樹要維護平衡，比起鏈表來，性能上的優勢并不明顯，

標籤：其他

上一篇：【Java】動態規劃系列【一】【背包問題】

下一篇：Unity ScrollView 顯示大量資料