csusky

HASHTABLE的內部實現

public class TestHashtable {
    public static void main(String[] args){
        Hashtable ht = new Hashtable();
        ht.put("sichuan","chengdu"); //改變以下四行代碼的順序，可能會改變輸出內容的順序    
        ht.put("hunan","changsha");     
        ht.put("beijing","beijing");    
        ht.put("anhui","hefei");    
        
    Enumeration e = ht.keys();
    while(e.hasMoreElements()) {
        Object key = e.nextElement();
        Object value = ht.get(key);            
        System.out.println(key + " " + value + " " + key.hashCode() + " " + value.hashCode());
    }
        
    }
}

        從上面的結構圖可以看出，Hashtable的實質就是一個數組＋鏈表。圖中的Entry就是鏈表的實現，Entry的結構中包含了對自己的另一個實例的引用next，用以指向另外一個Entry。而圖中標有數字的部分是一個Entry數組，數字就是這個Entry數組的index。那么往Hashtable增加鍵值對的時候，index會根據鍵的hashcode、Entry數組的長度共同決定，從而決定鍵值對存放在Entry數組的哪個位置。從這種意義來說，當鍵一定，Entry數組的長度一定的情況下，所得到的index肯定是相同的，也就是說插入順序應該不會影響輸出的順序才對。然而，還有一個重要的因素沒有考慮，就是計算index出現相同值的情況。譬如代碼中 "sichuan" 和 "anhui"，所得到的index是相同的，在這個時候，Entry的鏈表功能就發揮作用了：put方法通過Entry的next屬性獲得對另外一個Entry的引用，然后將后來者放入其中。根據debug得出的結果，"sichuan", "anhui"的index同為2，"hunan"的index為6，"beijing"的index為1，在輸出的時候，會以index遞減的方式獲得鍵值對。很明顯，會改變的輸出順序只有"sichuan"和"anhui"了，也就是說輸出只有兩種可能："hunan" - "sichuan" - "anhui" - "beijing"和"hunan" - "anhui" - "sichuan" - "beijing"。以下是運行了示例代碼之后，Hashtable的結果：

    
        以上的討論基于Java展開的，在C#中的Hashtable實現會有所不同，但是我相信兩者的設計應該是差不多的。感謝葉漂和quitgame，給了我思考的機會，也讓我感到了基礎知識的匱乏，看來是要補補基礎知識了。   

        [補充]：在Hashtable的實現代碼中，有一個名為rehash的方法用于擴充Hashtable的容量。很明顯，當rehash方法被調用以后，每一個鍵值對相應的index也會改變，也就等于將鍵值對重新排序了。這也是往不同容量的Hashtable放入相同的鍵值對會輸出不同的鍵值對序列的原因。在Java中，觸發rehash方法的條件很簡單：hahtable中的鍵值對超過某一閥值。默認情況下，該閥值等于hashtable中Entry數組的長度×0.75

posted on 2008-02-19 11:07 曉宇 閱讀(1663) 評論(0)  編輯  收藏