2011年4月10日 星期日

Java HashMap之一問


hash function:
h(name)=int (1st char of name)*31+int (2nd char of name)
hash table size:11 index: h(name) mod 11
int("C")=67,int("S")=83,int("L")=36,int("W")=87
以上有向圖,
用HashMap < Name, LinkedList < NameDistancePair > >的Java data structure畫出此directed weighted graph(15分)

反正看得懂的人應該看得懂在幹嘛@@
這一題看到有些傻眼,因為這題至少有SCJP實力的人才知道在幹嘛,就算有SCJP實力的人可能也沒辦法把它跟題目上面給的一團hash function做結合,因為他還自訂hash code咧~

以下是詳解:

1.首先來了解一下Java的HashMap這個結構:
要解題前,總先要知道一下這詭異的一串:
HashMap < Name, LinkedList < NameDistancePair > >
到底是什麼意思,老實說,這題已是相當深的Java語法,因為使用到泛型的觀念,又使用到算是比較困難的HashMap容器,卻是是相當難以了解,不過我還是來嘗試用簡單的語句讓你快速認識HashMap在Java中到底是什麼碗糕:
(1)HashMap在Java的doc中原本是長這樣的一個結構:
HashMap < key, value >
他是一個儲存東西的容器
每一筆資料,你可以指定他的key再存進去,
這樣以後要取出這個資料,或是查詢這個資料時,
Java就會根據你給定的key,把資料取出來
ex:
HashMap< String, String> test=new HashMap();//宣告一個HashMap叫做test


test.put("001", "John,taipei, sales");   //放一筆資料進HashMap中,其key為"001" (請注意: key是字串的型態)
test.put("002","Tom, kuoashong, teacher"); //放另一筆資料進HashMap中,其key為"002"

System.out.println(test.get("001")); //把有key="001"的資料取出來並印出,會得到  "John,taipei, sales"

如果你感覺到上例有點像資料庫,不用懷疑,那一定是我故意設計的,因為其實我個人覺得對一個不太了解的人,最快速的學習方式是從你知道的觀念學起,那個key有點像資料庫中table的PK, 後面的value就是tuple(值組)了~你可以根據PK,快速找到你要的資料

(2)此外,HashMap的key跟value都是泛型(generic):
有點類似c++的templete(如果你比較熟c++的話)
簡單的來說,實際應用上,你怎麼會知道你的key跟value一定要是什麼資料型態,
如果在設計時就給你訂死,例如說寫成 HashMap(Integer, String)這樣你就只能在key放integer
value放string, 當然就超級不方便, java要是這樣設計一個class一定被罵到吐血
所以就出現了所謂的泛型的東西
也就是說,你想要key是甚麼型態,都可以指定, value是甚麼型態,也可以指定,下面舉一些例子給你看:
Ex1:
Hash< Integer, String > //key是 Integer class, value是String class
當然也可以是你自己訂的型態:
Ex2:
Hash< MyKey, MyValue> //key是MyKey class, value是 MyValue class, 當然這兩個class是你另外寫的
所以我們的題目就會出現了:
HashMap < Name, LinkedList < NameDistancePair > >
這坨東西, 表示他的key的型態是自訂型態 Name
value的型態是 LinkedList < NameDistancePair > ,也就是一個由NameDistancePair自訂型態組成的LinkedList
我知道有人在這個value又被打敗了,所以再深入解釋一下:
(3)關於LinkedList < NameDistancePair >
假設你了解LinkedList是個甚麼樣的資料型態(呃...不了解的話,你還會看到這邊文章嗎?趕快去翻書吧),就是你想像的那個 Linked List
那 LinkedList < NameDistancePair >是甚麼東西呢?
我們知道 linked list的node,可以是各種你設計的結構,
所以Java當然在設計這個LinkedList的時候,會以泛型處理,所以講白話點,你如果用了
LinkedList < NameDistancePair >產了一個LinkedList的話,他大意上會長這個樣子:

head-->nameDistancePair1-->nameDistancePair2-->nameDistancePair3-->null

這樣有了解了嗎?
眼尖的人應該有發現,通常在Java中,出現 < >的東西的時候,多半是泛型出現的時機 (當然有時候他可能是interface<--這句話初學者可讓過,是寫給不小心逛到這裡的某些Java專家的)

當然~我們的HashMap是絕對可以接受你value那邊放LinkedList的(事實上,你如果key要放這個,也沒人會有意見...)
所以你可能會看到類似下面這種東西:
HashMap< LinkedList , HashMap< Integer, String>>
表示其key型態為 一個由String型態當node的LinkedList, 其value為另外一個HashMap
這樣也是合法的,看你的應用了

所以讓我們來複習一下,題目中的:
HashMap < Name, LinkedList < NameDistancePair > >
表示一個HashMap容器結構,
他的key的型態是自訂型態 Name
value的型態是 LinkedList < NameDistancePair > ,也就是一個由NameDistancePair自訂型態組成的LinkedList

希望你到這裡還沒被打敗才好,好戲才要開始咧
2.推測本題指定HashMap < Name, LinkedList < NameDistancePair > >各class應該是甚麼:
了解了一下HashMap之後,我們就來設計一下本題的Name跟 NameDistancePair應該放甚麼東西,
我們再複習一下整個directed graph:

所以Name的部分應該指的就是CS,LS,CL,WW這些vertex
那後面那個NameDistancePair根據他的命名推測他應該是想要表示一個path,如:A-->B,weight為3
那可能就會存(A,B,3)之類的東西
所以HashMap < Name, LinkedList < NameDistancePair > >
key的Name部分我存的是"起始點",也就是CS,LS,CL,WW這些vertex後面的LinkedList是存以key為起始點到下一個終點的path,因為已經有起點了,所以NameDistancePair只需要存終點weight就可以


EX:以CS來說
HashMap < Name, LinkedList < NameDistancePair > >

                    "CS",   ( (LS,7) , (CL,20) )
這樣就可以用來表示圖中7和20那條,其他就類推:
                    "LS"  ,   ( (WW,21), (CL,33) )
                    "CL" ,   ( (WW,6) )
                    "WW",  (  )
所以我的Name class長這樣:


其實要不是因為題目搞一個自訂hash function,也不用另外弄一個Name class,用String型態就可以了(我們在第三點解釋為什麼Name有一些很難懂的code)

NameDistancePair class:



而我們呼叫來試試看的程式碼:


趕快放進去Java玩看看吧~
絕對不是我小氣不放code,是因為這個地方貼上去就壞掉~不給我貼 我也沒辦法

3.題目給的hash function與HashMap間的關係:
接下來,可能有很多使用HashMap的人也不懂的是,題目幹嘛給一個hash function, java的HashMap跟hash function有甚麼關係?
其實HashMap就是一個hash table, 也就是他用來儲存資料的方式本質上是一個hash table
(不然他幹嘛class名字要有Hash..)
只是平常你在用這個結構的時候,java會自己幫你安排hash function跟hash table的事情,你儘管把資料放進去使用就好,完全不用去想甚麼hash function設計, collision發生,效能方面的事情,因為java都會幫你處理好
但是這個題目他給了你一堆hash function,擺明就是要你擺脫java幫你最佳化的hash function及hash table設計,要自訂hash function
這當然也是可以的~
(1)我們先來看java預設的HashMap機制怎麼做的:
使用下列程式碼來產生一個HashMap觀察:
HashMap ex1=new HashMap();使用debug模式,觀察 ex1的內容:
ex1.put("GG", "test");

 
 
 
我們可以看到此物件被儲存在table[15]的地方,其key為2175,由Java自行計算
那如果我自己要自訂這個key的算法呢?
因為hashMap會拿key class的hashCode(繼承自Object class)這個方法來計算hash的值,
所以我們要覆寫hashCode這個方法.
但在介紹程式碼之前,我們先來計算一下題目給定的4個name的hash值:
CS:題目有給範例 =4
LS:(76*31+83) mod 11=2
WW: (87*31+83) mod 11=2
CL: (67*31+76) mod 11=9
好樣的...按照題目給的hash function,竟然有collision....擺明就是要給你很難看,相信很多java使用者會用HashMap,可能根本不知道裡面實作結構是怎樣....題外話
所以我們開始override Name的 hashCode方法:


為求查詢方便,我用了一個HashMap來存CS=4, LS=2, WW=2, CL=9這個對照表,基本上跟題目沒甚麼關係,如果相關的寫法,你看不懂,那因為不在題目內容,所以我也不打算在這裡解釋XD

接下來終於要收工了,那讓我們來看看,Java跑出來之後會長怎麼樣子呢?
以debug看此HashMap test的結構:


我們可以看到,他真的照我們的指示放在2,4,9這些地方
再往下看一下那有兩個2的LS與WW會放在哪?照理來說他會有collision阿??


我們可以很清楚的看到,他先存WW然後再用next指向下一個LS那一串
難道HashMap是用chainnig?
其實答案是因為,此結構用的hash table的bucket不是1,我們可以看到由Java doc的解釋:
An instance of HashMap has two parameters that affect its performance: initial capacity and load factor. The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created. The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the capacity is roughly doubled by calling the rehash method.
在HashMap的constructor中有一個叫做capacity的變數,這個就是用來控制bucket數的,所以doc中說他的設定是非常重要的

4.最後總結一下,這一題畫起來應該是長這樣:


整個好累@@
沒想到弄這個好久喔~blogger真的不好做