這章節要介紹另一種資料結構，Hash Table。

先前提到了很多關於Binary Search Tree的各種概念，但他們其實有個限制條件，就是元素要能夠compare。

但可能有些元素就是沒辦法compare，而我們又希望能很快速的搜尋到這些放在collection中的元素，該怎麼辦呢?

這時就可以利用hash table的概念，Java中的HashSet, HashMap就是利用了這個概念實作的。

要使用hash table有三個動作：

1. 創建出一個hash function，將元素轉換為一個hash code
2. 創建M個數量的bucket，其index為 0 至 M-1
3. 將hashCode % M，看餘數是多少，就歸到哪個index的bucket

以下範例為總共有6個元素(N = 6)並且M = 4的歸類：

這樣會衍生出另一個問題，如果當要放進的元素數量N越來越大時，每個bucket累積的元素數量也會越來越多，當要搜尋的時候又會變慢了。所以這時我們會去觀察load factor，也就是N / M的數值，並規定如果load factor大於某個數值時，讓bucket的數量M增倍。上面的範例是將load factor設為1.5，所以當load factor大於等於1.5時，M增倍，並且將所有元素重新歸類bucket：

如此一來就可以保證hash table的效率了，會是趨近於Θ(1)(真正Θ(1)是每個bucket都只有1個元素，但實際上不可能)；只是有時候需要擴展bucket數量，會變成Θ(N)，因為N個元素都要重新歸類至新的bucket。

仔細思考的話，會發現hash function滿重要的，因為hash table要達到Θ(1)的效率關鍵就在於讓元素平均分配到各個bucket；若讓元素都被分配到同個bucket就變成跟一般的list一樣了。

目前所知最好的hash function是以一個小的質數為基底。以下是Java在String類別中實作的hashCode function：

@Override
public int hashCode(){
	int h = cachedHashValue;
	if(h == 0 && this.length() > 0){
		for(int i == 0; i < this.length(); i++){
			h = 31 * h + this.charAt(i);
		}
		cachedHashValue = h;
	}
	return h;
}

Slides are from Josh Hug CS61B

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License