2015年11月16日 星期一

[Java] Hashtable 的概觀、細節與實作

Hash Table

在撰寫程式時,我們經常會用到類似「表格」的資料結構來儲存資料。要完成這件事情,一個最基本的想法就是將表格的鍵值 (key,通常會是一個字串),經過某個函數轉換為整數後,將這個整數作為索引值把該筆資料存到一個夠大的陣列中。

利用 hashing 方式儲存與取得資料的操作都必須有兩個階段:第一步,先透過某個 hash function 把鍵值轉為用作索引值的整數,我們稱為 hash value,這個 hash value 會對應到這個「陣列」中的某個位置,我們稱為 bucket;第二,用這個計算出的 hash value 把要儲存的資料存入或取出 bucket。理想上來說,我們希望每筆資料都能在陣列中找到一個屬於自己的位置,但事實上當然不可能這麼理想,假設現在我們的陣列長度只有 100,但有 200 個元素要存入這個資料結構中,那絕對會發生資料 collision 的狀況。 所以上述的第二步驟的主要工作就是在於如何處理資料的 collision。

所以,組成一份 hash table 的主要元件有三:hash function、hash value 與 bucket。其中最為重要,也影響 hash table 效能最大的,就是 hash function 了。

Hash Function

為了盡量讓我們的資料都能平均的散佈在 hash table 的各個 bucket 中,我們希望 hash function 所計算出的 hash value 能盡量的平均散佈 (uniformly distributed)。而且因為計算 hash value 只是進行資料儲存取出整個過程的一小部分,所以我們也希望這個值的計算能盡量簡單。一般來說,常用的 hash function 有:
郵遞區號、身分證ID 等對資料內容有直觀意義的數字。
取餘數:假設 hash table 中有 k 個 bucket,我們可以取 m % k 作為 hash value。
字串:我們可以根據字串中的字元將整個字串計算成一個巨大的數字,然後再取 k 的餘數: 
int hash = 0;
for (int i = 0; i < s.length(); i++) 
    hash = (R * hash + s.charAt(i)) % M;

Bucket

在 hash table 的定義中,bucket 是用來存放多個具有相同 hash value 的鍵值對資料的地方。假設現在我們有一個含有 1000 個 bucket 的 hash table,同時我們也有一個非常完美的 hash function,理想上來說,如果現在我們將這 1000 筆鍵值對資料存入這個 hash table 後,每個 bucket 會正好只有一筆鍵值對資料存在其中,如此一來存取任何一筆資料的時間複雜度為 O(1)。

但是,事實上當然不可能有那麼完美的事。如果有兩筆鍵值對資料要存入 hash table,而兩筆資料的鍵值所算出來的 hash value 相同時,那這筆資料就會以鏈結串列的方式記錄在對應的 hash value 的欄位上。所以,如果現在我們有 n 筆資料要存入 hash table 中,而我們的 hash function 又非常的爛,假設是一個只會吐出常數的函數好了,那我們的 n 筆資料所算出的 hash value 總是同一個值,總是要被放在同一個 bucket 中,最終這個 hash table 裡會只有一個bucket,而這個 bucket 中卻有一個長度為 n 的鏈結串列。當我們要尋找某筆資料時,必須窮舉這個串列的每一筆資料,造成取出時間複雜度為 O(n) 的 worst case。

Java 的 hash tables

Java 中是如何實作 hash table 的呢?在 Java standard library 中可做為 hash table 的類別共有三個,分別是 HashtableHashMap 以及 ConcurrentHashMap

事實上,Java 的 HashMap 並不信任使用者類別中定義的 hashCode() 的 hash value 有多好,所以它會在實際計算 hash value 時,利用 hashCode() 所回傳的整數雜湊值作為輸入,再放入另一個名為 hash() 的靜態方法中來計算出實際用於存取資料的雜湊值。

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        // put the <key, value> to the table
    }
}

static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor.)
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

static int indexFor(int h, int length) {
    return h & (length-1);
}

我們可以看到要實際放入一筆資料進入 HashMap 時,會先透過物件的 hashCode() 與 HashMap 的 hash() 方法計算出 hash value,hash() 中的運算非常簡單,卻能夠有效降低 collision 的機率。

接著,由於 HashMap 中用來儲存資料的物件是個每個元素實際上都是一個 Entry 型態串列的陣列,所以我們要再透過 indexFor() 方法來算出現在要存取的鍵值對資料該放入哪個串列中。

HashMap 的 hash function

HashMap 的 get(Key k) 方法首先會呼叫鍵值物件的 hashCode(),然後將這個方法所計算出的 hash value 作為 input,再送給其所自行定義的靜態方法 hash() 中計算出要存取的 bucket 位置。不過,像是 Hashtable 與 ConcurrentHashMap 並沒有 null key 的問題,HashMap 如果遇到 null key,則總是會計算出 hash 0,也就是位置為 0 的 bucket。

現在有個有趣的問題了:明明我們就已經有了一個 hashCode(),為什麼還要再用它自己的 hash() 算一次呢?答案很簡單,因為 HashMap 並不相信自定義物件的 hash function 的品質。

Thread-Safety

Hashtable 雖然是 thread-safe 的類別,但其 thread-safe 的性質卻來自於各個被標為 synchronized 的成員方法。也就是說,Hashtable 在實際應用在多執行緒環境時,其效能會非常的低落。所以當我們必須在多執行緒環境中使用 hash table 時,我們會選擇使用 ConcurrentHashMapConcurrentHashMap 也是 thread-safe 的,但與 Hashtable 不同的是,ConcurrentHashMap 在處理可能發生 race condition 的操作時,其採用的策略是鎖定部分欄位 (lock the portion) 的方式。我們如果去看 ConcurrenctHashMap 的原始碼,會發現 put()get() 等方法並沒有像 Hashtable 那樣被直接標為 synchronzied,而是在明確知道該處理哪個 bucket 之後,不得不進行資料的寫入讀出時,才進行同步化的工作。

Fail-Fast 與 Fail-Safe