csusky

HASHTABLE的內(nèi)部實(shí)現(xiàn)

 

 為了講述Hashtable鍵排序的問(wèn)題，我們先來(lái)看Hashtable的結(jié)構(gòu)圖：

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

    
        以上的討論基于Java展開的，在C#中的Hashtable實(shí)現(xiàn)會(huì)有所不同，但是我相信兩者的設(shè)計(jì)應(yīng)該是差不多的。感謝葉漂和quitgame，給了我思考的機(jī)會(huì)，也讓我感到了基礎(chǔ)知識(shí)的匱乏，看來(lái)是要補(bǔ)補(bǔ)基礎(chǔ)知識(shí)了。   

        [補(bǔ)充]：在Hashtable的實(shí)現(xiàn)代碼中，有一個(gè)名為rehash的方法用于擴(kuò)充Hashtable的容量。很明顯，當(dāng)rehash方法被調(diào)用以后，每一個(gè)鍵值對(duì)相應(yīng)的index也會(huì)改變，也就等于將鍵值對(duì)重新排序了。這也是往不同容量的Hashtable放入相同的鍵值對(duì)會(huì)輸出不同的鍵值對(duì)序列的原因。在Java中，觸發(fā)rehash方法的條件很簡(jiǎn)單：hahtable中的鍵值對(duì)超過(guò)某一閥值。默認(rèn)情況下，該閥值等于hashtable中Entry數(shù)組的長(zhǎng)度×0.75

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