欢迎来到天天文库
浏览记录
ID:50587515
大小:87.00 KB
页数:9页
时间:2020-03-12
《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。
此文档下载收益归作者所有