最近做信息檢索的VSM實驗，字典生成這塊用的是java自帶的Hashtable數(shù)據(jù)結構，覺得效率還不錯。后來有同學提到用
詞典樹來保存字符串，可以用公共前綴來節(jié)約存儲空間，最大限度的減少無謂的比較，查詢效率要高于哈希表。(補充@2011.5.5 在數(shù)據(jù)較少的情況下，hash的查詢效率應該是最高的，基本接近O（1），字典樹的優(yōu)勢應該是在空間效率上)回頭有時間研究下詞典樹的實現(xiàn)和分析，這里先分析一下Java的hashtable實現(xiàn)。
為了使用Eclipse去查看java本身的一些基礎實現(xiàn)，我們需要先將java的源碼加到Eclipse的jre路徑中:
1.點 “window”-> "Preferences" -> "Java" -> "Installed JRES"
2.此時"Installed JRES"右邊是列表窗格，列出了系統(tǒng)中的 JRE 環(huán)境，選擇你的JRE，然后點邊上的 "Edit..."
3.選中rt.jar文件,點右邊的按鈕“Source Attachment...”, 選擇你的JDK目錄下的“src.zip”文件即可
這樣，在Eclipse中隨便寫一個Hashtable對象，然后ctrl單擊就可以看到java的Hashtable類的實現(xiàn)了。下面這張是其總體的結構：
總得來說就是每個哈希表都保存了一個Entry數(shù)組，然后每個Entry其實是存放碰撞的一個鏈，其中Entry類部分代碼實現(xiàn)是：
view plainprint?/**
* Hashtable collision list.
*/
private static class Entry<K,V> implements Map.Entry<K,V> {
int hash;
K key;
V value;
Entry<K,V> next;
protected Entry(int hash, K key, V value, Entry<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
除了hash值和鍵值對，就是指向下一個Entry的“指針”了。哈希表還有兩個主要的屬性，一個是initialCapacity表示初始的大小，如果使用默認的構造函數(shù)，系統(tǒng)就設為11，注意這里容量不是可以存放字符串的個數(shù)，而是哈希的范圍，設為11的話，所有的hash值都會映射到這11個位置上。另一個是loadFactor，表示存放元素的個數(shù)?？偟膆ash范圍的比例，默認的是設為0.75，這是在空間和時間之間的一個權衡，如果過大，則會有很多的碰撞出現(xiàn)，搜索效率不高，而如果過低，則會占用很大的空間。還有一些其他的屬性，比如總的元素個數(shù)，閾值等等，這里不再詳述。
下面看下幾個關鍵的函數(shù)實現(xiàn)，首先自然是put函數(shù)：
view plainprint?public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
V old = e.value;
e.value = value;
return old;
}
}
modCount++;
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
rehash();
tab = table;
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
Entry<K,V> e = tab[index];
tab[index] = new Entry<K,V>(hash, key, value, e);
count++;
return null;
}
這里我們可以看到，對key的hash做了一個與操作，保證其是一個正整數(shù)，然后對數(shù)組的長度求余，得到索引，然后遍歷這個索引位置的鏈表中的每一個元素，如果存在一個元素的key和插入的key相同，就修改其值。否則，就新建一個Entry放在index位置鏈表的最前面，其中用到了rehash函數(shù)，可以在當哈希表中的總個數(shù)超過當前容量乘以loadFactor（就是threshold）的時候，進行擴建和重排序：
view plainprint?protected void rehash() {
int oldCapacity = table.length;
Entry[] oldMap = table;
int newCapacity = oldCapacity * 2 + 1;
Entry[] newMap = new Entry[newCapacity];
modCount++;
threshold = (int)(newCapacity * loadFactor);
table = newMap;
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry<K,V> old = oldMap[i] ; old != null ; ) {
Entry<K,V> e = old;
old = old.next;
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
e.next = newMap[index];
newMap[index] = e;
}
}
}
容量擴大2倍加1，采用這個策略應該是有一定考慮的，我沒有細究。在拷貝完之后，進行了一個重新的hash，因為容量已經(jīng)變了，所以這個步驟是必須的。還有一些其他的函數(shù)，類似這里就不介紹了，最后我們來看下java的字符串hash是采用的什么算法：
view plainprint?public int hashCode() {
int h = hash;
if (h == 0) {
int off = offset;
char val[] = value;
int len = count;
for (int i = 0; i < len; i++) {
h = 31*h + val[off++];
}
hash = h;
}
return h;
}
這個函數(shù)在String中，看上面非常簡潔，就是對字符串中的每一個字符的ASCII碼值進行的一個加和乘運算，乘數(shù)是31。這個算法是BKDR哈希算法，來自于Brian Kernighan 和 Dennis Ritchie的The C Programming Language一書，可以說是常用的hash算法中較為簡潔的一個了，但是效率確實最好的之一，其中乘數(shù)的形式是31 131 1313 13131 131313...。關于常見的字符串hash算法，我會在以后的博客給予介紹，并用這次VSM的實驗進行一個簡單的測試。
