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 的類別共有三個，分別是 Hashtable、HashMap 以及 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 的品質。
