最近做信息檢索的VSM實(shí)驗(yàn)，字典生成這塊用的是java自帶的Hashtable數(shù)據(jù)結(jié)構(gòu)，覺(jué)得效率還不錯(cuò)。后來(lái)有同學(xué)提到用
詞典樹(shù)來(lái)保存字符串，可以用公共前綴來(lái)節(jié)約存儲(chǔ)空間，最大限度的減少無(wú)謂的比較，查詢效率要高于哈希表。(補(bǔ)充@2011.5.5 在數(shù)據(jù)較少的情況下，hash的查詢效率應(yīng)該是最高的，基本接近O（1），字典樹(shù)的優(yōu)勢(shì)應(yīng)該是在空間效率上)回頭有時(shí)間研究下詞典樹(shù)的實(shí)現(xiàn)和分析，這里先分析一下Java的hashtable實(shí)現(xiàn)。
為了使用Eclipse去查看java本身的一些基礎(chǔ)實(shí)現(xiàn)，我們需要先將java的源碼加到Eclipse的jre路徑中:
1.點(diǎn) “window”-> "Preferences" -> "Java" -> "Installed JRES"
2.此時(shí)"Installed JRES"右邊是列表窗格，列出了系統(tǒng)中的 JRE 環(huán)境，選擇你的JRE，然后點(diǎn)邊上的 "Edit..."
3.選中rt.jar文件,點(diǎn)右邊的按鈕“Source Attachment...”, 選擇你的JDK目錄下的“src.zip”文件即可
這樣，在Eclipse中隨便寫(xiě)一個(gè)Hashtable對(duì)象，然后ctrl單擊就可以看到j(luò)ava的Hashtable類的實(shí)現(xiàn)了。下面這張是其總體的結(jié)構(gòu)：
總得來(lái)說(shuō)就是每個(gè)哈希表都保存了一個(gè)Entry數(shù)組，然后每個(gè)Entry其實(shí)是存放碰撞的一個(gè)鏈，其中Entry類部分代碼實(shí)現(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值和鍵值對(duì)，就是指向下一個(gè)Entry的“指針”了。哈希表還有兩個(gè)主要的屬性，一個(gè)是initialCapacity表示初始的大小，如果使用默認(rèn)的構(gòu)造函數(shù)，系統(tǒng)就設(shè)為11，注意這里容量不是可以存放字符串的個(gè)數(shù)，而是哈希的范圍，設(shè)為11的話，所有的hash值都會(huì)映射到這11個(gè)位置上。另一個(gè)是loadFactor，表示存放元素的個(gè)數(shù)?？偟膆ash范圍的比例，默認(rèn)的是設(shè)為0.75，這是在空間和時(shí)間之間的一個(gè)權(quán)衡，如果過(guò)大，則會(huì)有很多的碰撞出現(xiàn)，搜索效率不高，而如果過(guò)低，則會(huì)占用很大的空間。還有一些其他的屬性，比如總的元素個(gè)數(shù)，閾值等等，這里不再詳述。
下面看下幾個(gè)關(guā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;
}
這里我們可以看到，對(duì)key的hash做了一個(gè)與操作，保證其是一個(gè)正整數(shù)，然后對(duì)數(shù)組的長(zhǎng)度求余，得到索引，然后遍歷這個(gè)索引位置的鏈表中的每一個(gè)元素，如果存在一個(gè)元素的key和插入的key相同，就修改其值。否則，就新建一個(gè)Entry放在index位置鏈表的最前面，其中用到了rehash函數(shù)，可以在當(dāng)哈希表中的總個(gè)數(shù)超過(guò)當(dāng)前容量乘以loadFactor（就是threshold）的時(shí)候，進(jìn)行擴(kuò)建和重排序：
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;
}
}
}
容量擴(kuò)大2倍加1，采用這個(gè)策略應(yīng)該是有一定考慮的，我沒(méi)有細(xì)究。在拷貝完之后，進(jìn)行了一個(gè)重新的hash，因?yàn)槿萘恳呀?jīng)變了，所以這個(gè)步驟是必須的。還有一些其他的函數(shù)，類似這里就不介紹了，最后我們來(lái)看下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;
}
這個(gè)函數(shù)在String中，看上面非常簡(jiǎn)潔，就是對(duì)字符串中的每一個(gè)字符的ASCII碼值進(jìn)行的一個(gè)加和乘運(yùn)算，乘數(shù)是31。這個(gè)算法是BKDR哈希算法，來(lái)自于Brian Kernighan 和 Dennis Ritchie的The C Programming Language一書(shū)，可以說(shuō)是常用的hash算法中較為簡(jiǎn)潔的一個(gè)了，但是效率確實(shí)最好的之一，其中乘數(shù)的形式是31 131 1313 13131 131313...。關(guān)于常見(jiàn)的字符串hash算法，我會(huì)在以后的博客給予介紹，并用這次VSM的實(shí)驗(yàn)進(jìn)行一個(gè)簡(jiǎn)單的測(cè)試。
