哈希表HashTable

0.前言

前面的文章我們分析了符号表的集中實作方式：有序連結清單、無序數組、二叉搜尋樹(BST)、平衡搜尋樹（紅黑樹法）等，通過下圖回憶一下各種實作方法的性能對比。

【Algorithms公開課學習筆記11】符号表part4——哈希表哈希表HashTable

那麼，除此之外，是否還存在性能更好的實作方法呢？答案是肯定的，就是本文将重點介紹的哈希表（HashTable）。

1.哈希函數

哈希表就是使用一個key-indexed的表來存儲資料，其中該index是對key使用哈希函數計算的結果。（如下圖所示）

【Algorithms公開課學習筆記11】符号表part4——哈希表哈希表HashTable

哈希存在以下三個注意事項：

哈希容易運算
相等性檢測：能夠通過哈希運算檢測兩個輸入值是否相等
沖突解決：能夠解決哈希沖突的情況。哈希沖突是指當兩個不同的輸入經過哈希運算的結果相同的index時

是以，哈希函數的目标是：均勻地為每一個key産生一個index，具體展現在：

高效的運算
一個index等可能地服務于一個key（理想情況下，一個key隻産生一個index）

hashCode

在Java中，每一個類都繼承了hashCode()方法，該方法會傳回一個32bit的整型資料。

預設情況下，hashCode(x)傳回的是x在記憶體中的位址，使用者可以通過重寫hashCode()方法改變這一規則。在Java庫裡，hashCode()的實作如下：

//Integer,整型本身就可以作為index，故傳回本身
public final class Integer{
    private final int value;
    ...
    public int hashCode(){
        return value; }
}

//Boolean，布爾值隻有兩種情況，故隻需傳回兩個index
public final class Boolean{
    private final boolean value;
    ...
    public int hashCode(){
        if (value) return 1231;
        else return 1237;
    }
}

//Double
public final class Double{
    private final double value;
    ...
    //先轉成64bit的形式，然後進行位異或，最後傳回強轉整型的index值
    public int hashCode(){
        long bits = doubleToLongBits(value);
        return (int) (bits ^ (bits >>> 32));
    }
}

//String，先将字元串拆成字元數組，然後使用公式：h = s[0]·31^L–1+ … +s[L–3]·312 +s[L–2]·31^1 +s[L–1]·31^0.
public final class String{
    //為了友善，可以先将結果緩存（因為String是immutable的）
    private int hash = 0;
    private final char[] s;
    ...
    public int hashCode(){
        int h = hash;
        if (h != 0) return h;
        for (int i = 0; i < length(); i++)
            hash = s[i] + (31 * hash);
        hash = h;
        return hash;
    }
}

對于使用者自定義的類中，可以使用以下标準來重寫hashCode()方法：

對每一個有意義的域使用x=31x+y的規則
如果域是基本類型(int, float等)，則使用其包裝類的hashCode()方法
如果域是null，則傳回0
如果域是引用類型，則使用hashCode()方法
如果域是數組，則對每一個數組項使用hashCode()方法（或者使用Arrays.deepHashCode()方法）

//使用者自定義類型
public final class Transaction implements Comparable<Transaction>{
    private final String who;
    private final Date when;
    private final double amount;

    public Transaction(String who, Date when, double amount){ /* as before */ }
    ...
    public boolean equals(Object y){ /* as before */ }

    public int hashCode(){
        //非零常數
        int hash = 17;
        //引用類型
        hash = 31*hash + who.hashCode();
        hash = 31*hash + when.hashCode();
        //基本類型
        hash = 31*hash + ((Double) amount).hashCode();
        return hash;
    }
}

前文講到hashCode()傳回一個32位的整型資料，其範圍是：-2^31 ~ 2^31 -1。

由于我們哈希的目的是得出index，如果數組的長度為M，則index隻能取0 ~ M-1之間的值。這時，對hashCode()的結果對M取模即可。
由于index的值均為正整數，而hashCode()的結果存在負數，故需要将其轉化成正數。不能直接使用Math類的絕對值方法，因為有可能會使-2^31 變成2^31而越界。這時，可以讓hashCode()結果位與0x7fffffff。

//錯誤，可能會越界
private int hash(Key key){
    return Math.abs(key.hashCode()) % M;
}

//符合實際需求的哈希函數
private int hash(Key key){
    return (key.hashCode() & 0x7fffffff) % M;
}

均勻哈希假想（Uniform hashing assumption）

均勻哈希假想：每一個key值都等可能地哈希成一個0 ~ M-1的整型值。

設想一個球與桶的模型：随機地往M個桶抛球，存在以下情況：

【Algorithms公開課學習筆記11】符号表part4——哈希表哈希表HashTable

Birthday problem：經過 ~sqrt(πM /2)次投擲後，會出現兩個球進入同一個桶的情況（首次出現沖突）

Coupon collector：經過 ~MlnM 次投擲後，每一個桶至少有一個球（所有桶都有球）

Load balancing：經過 M次投擲後，大多數loaded的桶會有Θ(logM / log logM)個球

是以，如果滿足均勻哈希假想的場景，将滿足上述的三種情況。

2.哈希沖突之分鍊法（separate chaining）

上文已經涉及了哈希沖突，所謂哈希沖突是指當兩個不同的輸入key經過哈希運算後出現相同的index的情況。

【Algorithms公開課學習筆記11】符号表part4——哈希表哈希表HashTable

處理哈希沖突有兩個常用的方法：分鍊法和線性探測。本小節介紹分鍊法，線性探測法将在下一小節分析。

分鍊法

分鍊法是使用size為M的數組來存放index，且每個index将指向一條連結清單。基本操作如下：

哈希：将key映射成0 ~ M-1的整數i
插入：将該key-vaule對插入第i條連結清單，每條連結清單有數組索引
查找：根據key的映射整數i查找到第i條連結清單，然後在連結清單中使用key來比對查找value值

【Algorithms公開課學習筆記11】符号表part4——哈希表哈希表HashTable

public class SeparateChainingHashST<Key, Value>{

    private int M = 97; //數組大小，即連結清單的數量
    private Node[] st = new Node[M]; //數組
    //連結清單節點
    private static class Node{
        private Object key;
        private Object val;
        private Node next;
        ...
    }

    //哈希操作
    private int hash(Key key){
        return (key.hashCode() & 0x7fffffff) % M;
    }

    //插入操作
    public void put(Key key, Value val) {
        int i = hash(key);
        for (Node x = st[i]; x != null; x = x.next)
            if (key.equals(x.key)){
                x.val = val;
                return;
            }
        st[i] = new Node(key, val, st[i]);
    }

    //查找操作
    public Value get(Key key) {
        int i = hash(key);
        for (Node x = st[i]; x != null; x = x.next)
            if (key.equals(x.key)) 
                return (Value) x.val;
        return null;
    }
}

性能分析

在分鍊法中，會影響時間性能的就是參數M的選擇了。實驗證明，在均勻哈希假想下，連結清單的key的個數是N/M的機率接近于1，是以，連結清單大小的分布的服從二項分布的。

【Algorithms公開課學習筆記11】符号表part4——哈希表哈希表HashTable

是以，M的大小就很關鍵了。如果M過大，就會出現許多短鍊，甚至空鍊；如果M過小，就會出現長鍊。理論上，M的最佳值為M ~ N/5，即N/M = 5。

分鍊法的時間性能如下。其中平均情況是滿足均勻哈希假想下成立的

【Algorithms公開課學習筆記11】符号表part4——哈希表哈希表HashTable

3.哈希沖突之線性探測（linear probing）

本節我們繼續分析哈希沖突的另一個解決方法——線性探測法。

線性探測法

線性探測法采用的措施是：用size為M的數組來存儲N個資料時，如果産生沖突，就尋找下一個空項來存儲（M必須大于N）。基本操作如下：

哈希：将key映射成0 ~ M-1的整數i
插入：将key插入到位置i，如果沖突，就往下位置i+1, i+2……
查找：從位置i取出key-value對，如果key存在但不比對，就往下位置i+1, i+2……

public class LinearProbingHashST<Key, Value>{

    private int M = 30001; //M必須足夠大，大于N
    private Value[] vals = (Value[]) new Object[M];//數組不能泛型
    private Key[] keys = (Key[]) new Object[M];

    //哈希操作
    private int hash(Key key) {
        return (key.hashCode() & 0x7fffffff) % M;
    }

    //插入操作
    public void put(Key key, Value val){
        int i;
        for (i = hash(key); keys[i] != null; i = (i+1) % M)
            if (keys[i].equals(key))
                break;
        keys[i] = key;
        vals[i] = val;
    }

    //查找操作
    public Value get(Key key){
        for (int i = hash(key); keys[i] != null; i = (i+1) % M)
            if (key.equals(keys[i]))
                return vals[i];
        return null;
    }
}

knuth’s parking問題

問題模型：在一條單向的路上有M個停車位，每一台車都是随機尋找停車位i，如果i已經被占用，就往下尋找i+1，i+2……。問：如何計算一輛車在parking過程中的平均位移(mean displacement)。

半滿half-full：當已經停有M/2輛車時，平均位移 ~ 3/2

全滿full：當已經停有M輛車時，平均位移 ~ sqar(πM /8)

将knuth’s parking問題類比到線性探測法中同樣适用。是以，線上性探測法中，同樣要注意M值對時間性能的影響。

性能分析

在均勻哈希假想下，如果N/M = α時，查找一個key值一次命中與不命中的機率如下圖，數學證明略。

【Algorithms公開課學習筆記11】符号表part4——哈希表哈希表HashTable

當M值過大時，數組就會有許多空項，浪費空間；當M值過小時，就會有許多沖突，查找的時間就會劇增。理論證明，α值最佳為 ~1/2,根據N/M = α，可以計算出最佳M值。

線性探測法的時間性能如下。其中平均情況是滿足均勻哈希假想下成立的

【Algorithms公開課學習筆記11】符号表part4——哈希表哈希表HashTable

4.其他

單向哈希函數

由于哈希會發生沖突，惡意對手可以通過研究你的哈希函數來确定發生沖突的case，然後制造大量沖突的塊去堵塞通道（如果你采用分鍊法，就會出現某條鍊特别長），進而影響系統性能，甚至導緻系統癱瘓。這種稱為拒絕服務攻擊。

在Java1.1版本中，String型的hashCode()就存在以下已知的沖突：

【Algorithms公開課學習筆記11】符号表part4——哈希表哈希表HashTable

是以，有人就提出了單向哈希函數(one-way hash function)，單向哈希函數的特征是容易通過key哈希得到index，但是通過index反向找到應該哈希的key是很困難的。

在實際應用中，MD5, SHA-0, SHA-1, SHA-2都是安全性達到要求的哈希函數。哈希函數通常可用于數字簽名、密碼存儲、消息認證等場景。

分鍊法vs線性探測法

分鍊法

比較容易去實作delete方法，但要注意哈希表是不支援其他ordered operation的
能夠優雅地降低性能，即降低性能的同時實作起來也簡單
對聚簇的影響不敏感，更關注對哈希函數的設計

線性探測法

更節約空間
更好的緩存特性

優化的哈希函數

雙探頭哈希Two-probe hashing

雙探頭哈希是分鍊法的進化型。它會用兩個哈希函數将key哈希到兩個位置，然後選擇鍊比較短的那條進行存放。有效地将最長鍊的長度減小到理想中的log logN。

雙重哈希Double hashing

雙重哈希是線性探測法的進化型。它使用線性探測，在發生沖突時，不是一個個往下找，而是間隔若幹個往下找。這樣可以有效地消除聚簇的影響，并且能夠讓哈希表接近full的狀态。但是删除操作不容易實作。

Cuckoo hashing

Cuckoo hashing是線性探測的進化型。它會用一個哈希函數将key哈希到兩個位置，随機選擇一個存儲。如果第一個位置已被占用，就選擇另一個位置存儲之。

哈希表vs平衡搜尋樹

哈希表

容易實作，但不支援ordered operation
對于簡單的key，性能表現得更好
對于無序的key，暫無有效的替代品（不了解）
在Java中，java.util.HashMap, java.util.IdentityHashMap 都是通過哈希表實作的

平衡搜尋樹

有更強的性能保證（哈希表要在均勻哈希假想的前提下，而BSTs無需前提）
支援order operation
相比于實作equal()和hashCode()，實作compareTo()更容易
在Java中，java.util.TreeMap, java.util.TreeSet 都是通過BSTs實作的

5.對比

【Algorithms公開課學習筆記11】符号表part4——哈希表哈希表HashTable

【Algorithms公開課學習筆記11】符号表part4——哈希表哈希表HashTable

哈希表HashTable

0.前言

1.哈希函數

hashCode

均勻哈希假想（Uniform hashing assumption）

2.哈希沖突之分鍊法（separate chaining）

分鍊法

性能分析

3.哈希沖突之線性探測（linear probing）

線性探測法

knuth’s parking問題

性能分析

4.其他

單向哈希函數

分鍊法vs線性探測法

優化的哈希函數

哈希表vs平衡搜尋樹

5.對比

繼續閱讀

關于Gradle配置的小結

Java小案例——随機數猜測随機數猜測

nginx location中斜線的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method

【Algorithms公開課學習筆記11】 符号表part4——哈希表哈希表HashTable

哈希表HashTable

0.前言

1.哈希函數

hashCode

均勻哈希假想（Uniform hashing assumption）

2.哈希沖突之分鍊法（separate chaining）

分鍊法

性能分析

3.哈希沖突之線性探測（linear probing）

線性探測法

knuth’s parking問題

性能分析

4.其他

單向哈希函數

分鍊法vs線性探測法

優化的哈希函數

哈希表vs平衡搜尋樹

5.對比

繼續閱讀

【Algorithms公開課學習筆記11】符号表part4——哈希表哈希表HashTable