java-基礎-TreeMap和HashMap

HashMap通過hashcode對其内容進行快速查找，而 TreeMap中所有的元素都保持着某種固定的順序，如果你需要得到一個有序的結果你就應該使用TreeMap（HashMap中元素的排列順序是不固定的）。

HashMap 非線程安全 TreeMap 非線程安全

線程安全

在Java裡，線程安全一般展現在兩個方面：

1、多個thread對同一個java執行個體的通路（read和modify）不會互相幹擾，它主要展現在關鍵字synchronized。如ArrayList和Vector，HashMap和Hashtable

（後者每個方法前都有synchronized關鍵字）。如果你在interator一個List對象時，其它線程remove一個element，問題就出現了。

2、每個線程都有自己的字段，而不會在多個線程之間共享。它主要展現在java.lang.ThreadLocal類，而沒有Java關鍵字支援，如像static、transient那樣。

1.AbstractMap抽象類和SortedMap接口

AbstractMap抽象類：(HashMap繼承AbstractMap)覆寫了equals()和hashCode()方法以確定兩個相等映射傳回相同的哈希碼。如果兩個映射大小相等、包含同樣的鍵且每個鍵在這兩個映射中對應的值都相同，則這兩個映射相等。映射的哈希碼是映射元素哈希碼的總和，其中每個元素是Map.Entry接口的一個實作。是以，不論映射内部順序如何，兩個相等映射會報告相同的哈希碼。

SortedMap接口：（TreeMap繼承自SortedMap）它用來保持鍵的有序順序。SortedMap接口為映像的視圖(子集)，包括兩個端點提供了通路方法。除了排序是作用于映射的鍵以外，處理SortedMap和處理SortedSet一樣。添加到SortedMap實作類的元素必須實作Comparable接口，否則您必須給它的構造函數提供一個Comparator接口的實作。TreeMap類是它的唯一一份實作。

HashMap：适用于在Map中插入、删除和定位元素。

Treemap：适用于按自然順序或自定義順序周遊鍵(key)。

HashMap通常比TreeMap快一點(樹和哈希表的資料結構使然)，建議多使用HashMap，在需要排序的Map時候才用TreeMap。

在HashMap中通過get()來擷取value，通過put()來插入value，ContainsKey()則用來檢驗對象是否已經存在。可以看出，和ArrayList的操作相比，HashMap除了通過key索引其内容之外，别的方面差異并不大。

前面介紹了，HashMap是基于HashCode的，在所有對象的超類Object中有一個HashCode()方法，但是它和equals方法一樣，并不能适用于所有的情況，這樣我們就需要重寫自己的HashCode()方法。

在這個例子中，Element用來索引對象Figureout,也即Element為key，Figureout為value。在Figureout中随機生成一個浮點數，如果它比0.5大，列印”OK!”，否則列印”Impossible!”。之後檢視Element(3)對應的Figureout結果如何。

結果卻發現，無論你運作多少次，得到的結果都是”Not found”。也就是說索引Element(3)并不在HashMap中。這怎麼可能呢？

原因得慢慢來說：Element的HashCode方法繼承自Object，而Object中的HashCode方法傳回的HashCode對應于目前的位址，也就是說對于不同的對象，即使它們的内容完全相同，用HashCode（）傳回的值也會不同。這樣實際上違背了我們的意圖。因為我們在使用 HashMap時，希望利用相同内容的對象索引得到相同的目标對象，這就需要HashCode()在此時能夠傳回相同的值。在上面的例子中，我們期望 new Element(i) (i=5)與 Elementtest=newElement(5)是相同的，而實際上這是兩個不同的對象，盡管它們的内容相同，但它們在記憶體中的位址不同。是以很自然的，上面的程式得不到我們設想的結果。

面對Element類更改如下：

在這裡Element覆寫了Object中的hashCode()和equals()方法。覆寫hashCode()使其以number的值作為 hashcode傳回，這樣對于相同内容的對象來說它們的hashcode也就相同了。而覆寫equals()是為了在HashMap判斷兩個key是否相等時使結果有意義（有關重寫equals()的内容可以參考我的另一篇文章《重新編寫Object類中的方法》）。修改後的程式運作結果如下：

h2:

Get the result for Element:

Impossible!

請記住：如果你想有效的使用HashMap，你就必須重寫在其的HashCode()。

還有兩條重寫HashCode()的原則：

[list=1]

不必對每個不同的對象都産生一個唯一的hashcode，隻要你的HashCode方法使get()能夠得到put()放進去的内容就可以了。即”不為一原則”。

生成hashcode的算法盡量使hashcode的值分散一些，不要很多hashcode都集中在一個範圍内，這樣有利于提高HashMap的性能。即”分散原則”。至于第二條原則的具體原因，有興趣者可以參考Bruce Eckel的《Thinking in Java》，在那裡有對HashMap内部實作原理的介紹，這裡就不贅述了。

掌握了這兩條原則，你就能夠用好HashMap編寫自己的程式了。不知道大家注意沒有，java.lang.Object中提供的三個方法：clone()，equals()和hashCode()雖然很典型，但在很多情況下都不能夠适用，它們隻是簡單的由對象的位址得出結果。這就需要我們在自己的程式中重寫它們，其實java類庫中也重寫了千千萬萬個這樣的方法。利用面向對象的多态性——覆寫，Java的設計者很優雅的建構了Java的結構，也更加展現了Java是一門純OOP語言的特性。