JAVA程式设计与资料结构.ppt

《JAVA程式设计与资料结构.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、JAVA程式設計與資料結構第十六章HashTablesIntroductionHashTables結構為一個Array，稱之為Bucketarray。如果想要新增一個物件，要根據這個物件的特性將其加入HashTable內。BucketArray用A來代替，其size為N，也就是A的Capacity。每個物件需要有一個Key，用來判斷物件需要放入哪一個籃子裡。如果key是唯一的，而且忽略collision，那麼searches，insertion和removals的worst-cast執行時間為O(1)HashFunctionsan

2、dHashCodeHashFunction的用處就是將key轉換成hashcode（稱之為k的hashcode）。根據hashcode來決定物件需放在BucketArray的某位置。h(k)代表hashfunction，其中k就是key。如果h(k)的範圍剛好介於[0，N-1]之間，那便可以直接將(k,e)存入籃子A[h(k)]內，其中e為欲存入之物件。必須特別注意的是我們必須要慎選hashfunction跟key。因為我們希望的是每個籃子內裝的物件沒有collision，如果hashfunction跟key沒有設計好的話，很容易產

3、生物件集中在少數幾個籃子內的情形。CompressionMaps當HashCode的值並不是座落在BucketArray的Index範圍內時（也就是[0,N-1]），只要將HashCode除以N-1，然後求其餘數即可。在這樣的情形下，我們還得注意慎選N的值，如果N為質數的話，對於平均分佈物件會有較好的效果。例如如果我們有keys{200,205,210,215,220,…..,600}，如果N的值等於100，那麼所有的hashcode都會是5的倍數，也就是說所有的物件都會擠在5的倍數的籃子裡，這樣會造成許多的collision。可是

4、如果我們將N的值改成101的話，那麼這樣的情形便會改善許多。CompressionMaps對於一些容易有重複型態的key，例如都是某個數的倍數，我們可以用比較複雜的hashfunction來求得分佈較好的hashcode。例如：Collision-HandlingSchemes雖然我們有上述許多設計較好hashfunction的方法，還是難以避免會出現兩個物件有相同hashcode的情況(collision)，亦即，這樣我們便無法直接將新物件insert進hashtable。也會影響尋找的功能。此時我們必須有一些機制來反應這個情況。

5、以下介紹SeparateChaining＆OpenAddressing兩種機制。SeparateChaining在每一個籃子裡，我們放入一個Vector或是LinkedList來儲存相同key的物品，也就是在A[i]內，放入一個Vector或LinkedList，B。這樣我們便可以將collision的情況解決。需要注意B這個Vector(orLinkedList)的物件個數需要時時的監控，不可使之過長，否則便會增長操作的時間，而也就失去了HashTable的用意。OpenAddressingopenaddressing的方法就是只

6、使用一個hashtable的結構，不過這樣需要使用較為複雜的方式來處理collision，而且在openaddressing的方式中，loadfactor必須要小於1，也就是，而且物件便直接儲存在BucketArray之內。一般有以下幾種方式：LinearProbingQuadraticProbingDoubleHashingLoadFactorsandRehashingLoadFactor的定義為，而且我們希望的值小於1。根據經驗及一般的案例分析，如果使用openaddressing的話，的值最好小於0.5。如果是使用separa

7、techaining的話，的值最好小於0.9。保持的值在一個相當的低點變成維護hashtable所必須的一件事。當的值變大到超過一個固定的值，通常我們需要重新調整hashtable的大小，並且將所有的物件重新加入到新的hashtable內。一般來說，如果要重新調整hashtable的大小，通常會將讓新的hashtable的大小為原來的兩倍。此外，我們可能還需要重新定義hashfunction以符合新的hashtable的大小。這樣的程序我們稱之為rehashing。