數組是Java語言內置的類型，除此之外，Java有多種保存對象引用的方式。Java類庫提供了一套相當完整的容器類，使用這些類的方法可以保存和操縱對象。下面分別進行討論，在研究Java容器類之前，先了解一下Java數組的基本功能和
特性。
1. 數組的基本特性
數組與其它種類的容器(List/Set/Map)之間的區別在于效率、確定的類型和保存基本類型
數據的能力。數組是一種高效的存儲和隨機訪問對象引用序列的方式，使用數組可以快速的訪問數組中的元素。但是當創建一個數組對象(注意和對象數組的區別)后，數組的大小也就固定了，當數組空間不足的時候就再創建一個新的數組，把舊的數組中所有的引用
復制到新的數組中。
Java中的數組和容器都需要進行邊界檢查，如果越界就會得到一個RuntimeException異常。這點和C++中有所不同，C++中vector的操作符[]不會做邊界檢查，這在速度上會有一定的提高，Java的數組和容器會因為時刻存在的邊界檢查帶來一些
性能上的開銷。
Java中通用的容器類不會以具體的類型來處理對象，容器中的對象都是以Object類型處理的，這是Java中所有類的基類。另外，數組可以保存基本類型，而容器不能，它只能保存任意的Java對象。
一般情況下，考慮到效率與類型檢查，應該盡可能考慮使用數組。如果要解決一般化的問題，數組可能會受到一些限制，這時可以使用Java提供的容器類。
2. 操作數組的實用功能
在java.util.Arrays類中，有許多static靜態方法，提供了操作數組的一些基本功能：
equals()方法----用于比較兩個數組是否相等，相等的條件是兩個數組的元素個數必須相等，并且對應位置的元素也相等。
fill()方法----用以某個值填充整個數組，這個方法有點笨。
asList()方法----接受任意的數組為
參數，將其轉變為List容器。
binarySearch()方法----用于在已經排序的數組中查找元素，需要注意的是必須是已經排序過的數組。當Arrays.binarySearch()找到了查找目標時，該方法將返回一個等于或大于0的值，否則將返回一個負值，表示在該數組目前的排序狀態下此目標元素所應該插入的位置。負值的計算公式是“-x-1”。x指的是第一個大于查找對象的元素在數組中的位置，如果數組中所有的元素都小于要查找的對象，則x = a.size()。如果數組中包含重復的元素，則無法保證找到的是哪一個元素，如果需要對沒有重復元素的數組排序，可以使用TreeSet或者LinkedHashSet。另外，如果使用Comparator排序了某個對象數組，在使用該方法時必須提供同樣的Comparator類型的參數。需要注意的是，基本類型數組無法使用Comparator進行排序。
sort()方法----對數組進行升序排序。
在Java標準類庫中，另有static方法System.arraycopy()用來復制數組，它針對所有類型做了重載。
3. 數組的排序
在Java1.0和1.1兩個版本中，類庫缺少基本的算法操作，包括排序的操作，Java2對此進行了改善。在進行排序的操作時，需要根據對象的實際類型執行比較操作，如果為每種不同的類型各自編寫一個不同的排序方法，將會使得
代碼很難被復用。一般的程序
設計目標應是“將保持不變的事物與會發改變的事物相分離”。在這里，不變的是通用的排序算法，變化的是各種對象相互比較的方式。
Java有兩種方式來實現比較的功能，一種是實現java.lang.Comparable接口，該接口只有一個compareTo()方法，并以一個Object類為參數，如果當前對象小于參數則返回負值，如果相等返回零，如果當前對象大于參數則返回正值。另一種比較方法是采用策略(strategy)設計模式，將會發生變化的代碼封裝在它自己的類(策略對象)中，再將策略對象交給保持不變的代碼中，后者使用此策略實現它的算法。因此，可以為不同的比較方式生成不同的對象，將它們用在同樣的排序程序中。在此情況下，通過定義一個實現了Comparator接口的類而創建了一個策略，這個策略類有compare()和equals()兩個方法，一般情況下實現compare()方法即可。
使用上述兩種方法即可對任意基本類型的數組進行排序，也可以對任意的對象數組進行排序。再提示一遍，基本類型數組無法使用Comparator進行排序。
Java標準類庫中的排序算法針對排序的類型進行了優化——針對基本類型設計了“快速排序”，針對對象設計的“穩定歸并排序”。一般不用擔心其性能。
Java容器分析--List和Set
容器類可以大大提高編程效率和編程能力，在Java2中，所有的容器都由SUN公司的Joshua Bloch進行了重新設計，豐富了容器類庫的功能。
Java2容器類類庫的用途是“保存對象”，它分為兩類：
Collection----一組獨立的元素，通常這些元素都服從某種規則。List必須保持元素特定的順序，而Set不能有重復元素。
Map----一組成對的“鍵值對”對象，即其元素是成對的對象，最典型的應用就是數據字典，并且還有其它廣泛的應用。另外，Map可以返回其所有鍵組成的Set和其所有值組成的Collection，或其鍵值對組成的Set，并且還可以像數組一樣擴展多維Map，只要讓Map中鍵值對的每個“值”是一個Map即可。
1.迭代器
迭代器是一種設計模式，它是一個對象，它可以遍歷并選擇序列中的對象，而開發人員不需要了解該序列的底層結構。迭代器通常被稱為“輕量級”對象，因為創建它的代價小。
Java中的Iterator功能比較簡單，并且只能單向移動：
(1) 使用方法iterator()要求容器返回一個Iterator。第一次調用Iterator的next()方法時，它返回序列的第一個元素。
(2) 使用next()獲得序列中的下一個元素。
(3) 使用hasNext()檢查序列中是否還有元素。
(4) 使用remove()將迭代器新返回的元素刪除。
Iterator是Java迭代器最簡單的實現，為List設計的ListIterator具有更多的功能，它可以從兩個方向遍歷List，也可以從List中插入和刪除元素。
2.List的功能方法
List(interface): 次序是List最重要的特點；它確保維護元素特定的順序。List為Collection添加了許多方法，使得能夠向List中間插入與移除元素(只推薦LinkedList使用)。一個List可以生成ListIterator，使用它可以從兩個方向遍歷List，也可以從List中間插入和刪除元素。
ArrayList: 由數組實現的List。它允許對元素進行快速隨機訪問，但是向List中間插入與移除元素的速度很慢。ListIterator只應該用來由后向前遍歷ArrayList，而不是用來插入和刪除元素，因為這比LinkedList開銷要大很多。
LinkedList: 對順序訪問進行了優化，向List中間插入與刪除得開銷不大，隨機訪問則相對較慢(可用ArrayList代替)。它具有方法addFirst()、addLast()、getFirst()、getLast()、removeFirst()、removeLast()，這些方法(沒有在任何接口或基類中定義過)使得LinkedList可以當作堆棧、隊列和雙向隊列使用。
3.Set的功能方法
Set(interface): 存入Set的每個元素必須是唯一的，因為Set不保存重復元素。加入Set的Object必須定義equals()方法以確保對象的唯一性。Set與Collection有完全一樣的接口。Set接口不保證維護元素的次序。
HashSet: 為快速查找而設計的Set。存入HashSet的對象必須定義hashCode()。
TreeSet: 保持次序的Set，底層為樹結構。使用它可以從Set中提取有序的序列。
LinkedHashSet: 具有HashSet的查詢速度，且內部使用鏈表維護元素的順序(插入的次序)。于是在使用迭代器遍歷Set時，結果會按元素插入的次序顯示。
HashSet采用散列函數對元素進行排序，這是專門為快速查詢而設計的；TreeSet采用紅黑樹的數據結構進行排序元素；LinkedHashSet內部使用散列以加快查詢速度，同時使用鏈表維護元素的次序，使得看起來元素是以插入的順序保存的。需要注意的是，生成自己的類時，Set需要維護元素的存儲順序，因此要實現Comparable接口并定義compareTo()方法。
Java容器分析--Map
標準的Java類庫中包含了幾種類型的Map，它們都擁有同樣的基本接口Map，但是行為特性各不相同，主要表現在效率、鍵值對的保存、元素呈現次序、對象的保存周期和判定鍵是否等價的策略等方面。
1.Map的功能方法
Map(interface): 維護label和value的關聯性，使得可以通過label查找value。
HashMap: Map基于散列表的實現，取代了Hashtable。插入和查詢label/value的開銷是固定的，并且可以通過構造器設置容量和負載因子，以調整容器的性能。
LinkedHashMap: 在HashMap的基礎上做了一些改進，在迭代遍歷它時，取得label/value的順序是其插入的次序，或者是最近最少使用(LRU)的次序，速度上比HashMap要慢一點，但在迭代訪問時速度會更快，主要原因是它使用了鏈表維護內部次序。
TreeMap: 查看label或label/value時，元素會被排序，其次序由Comparable或Comparator決定，因此查詢所得到的結果是經過排序的。另外，它是唯一帶有subMap()方法的Map具體類，即返回一個子樹。它也是SortedMap接口的唯一實現，subMap()方法也是從該接口繼承的。
WeakHashMap: Weak Key映射，允許釋放映射所指向的對象。當映射之外沒有引用指向某個label時，此label可以被垃圾收集器回收。
IdentityHashMap: 使用==代替equals()對label進行比較的散列映射。
2.hashCode()
當使用標準庫中的類Integer作為HashMap的label時，程序能夠正常運行，但是使用自己創建的類作為HashMap的label時，通常犯一個錯誤。
在HashMap中通過label查找value時，實際上是計算label對象地址的散列碼來確定value的。一般情況下，我們是使用基類Object的方法hashCode()來生成散列碼，它默認是使用對象的地址來計算的，因此由第一個對象new Apple(5)和第二個對象new Apple(5)生成的散列碼是不同的，不能完成正確的查找。通常，我們可以編寫自己的hashCode()方法來覆蓋基類的原始方法，但與此同時，我們必須同時實現equals()方法來判斷當前的label是否與表中存在的label相同。正確的equals()方法滿足五個條件：
(1) 自反性。對于任意的x，x.equals(x)一定返回true。
(2) 對稱性。對于任意的x和y，如果y.equals(x)返回true，則x.equals(y)也返回true。
(3) 傳遞性。對于任意的x、y、z，如果有x.equals(y)返回true，y.equals(z)返回true，則x.equals(z)一定返回true。
(4) 一致性。對于任意的x和y，如果對象中用于等價比較的信息沒有改變，那么無論調用x.equals(y)多少次，返回的結果應該保持一致，要么一直是true，要么一直是false。
(5) 對任何不是null的x，x.equals(null)一定返回false。
equals()比較的是對象的地址，如果要使用自己的類作為HashMap的label，必須同時重載hashCode()和equals()方法。
使用散列的目的：想要使用一個對象來查找另一個對象。使用TreeSet或TreeMap也能實現此目的。另外，還可以自己實現一個Map，此時，必須提供Map.entrySet()方法來生成Map.Entry對象的Set。
使用散列的價值：速度，散列使得查詢可以快速進行。散列將label保存載數組中方便快速查詢，因為存儲一組元素最快的數據結構是數組，用它來表示label的信息(后面有信息的描述)，而不是label本身。通過label對象計算得到一個數字，作為數組的下標，這個數字就是散列碼(即前面所述的信息)。該散列碼具體是通過定義在基類Object中，可能由程序員自定義的類覆蓋的hashCode()方法，即散列函數生成。為了解決數組容量帶來的限制，可以使不同的label生成相同的下標，保存在一個鏈表list中，每一個鏈表就是數組的一個元素。查詢label時就可以通過對list中的信息進行查找，當散列函數比較好，數組的每個位置中的list長度較短，則可以快速查找到數組元素list中的某個位置，提高了整體速度。
散列表中的slot通常稱為bucket，為了使散列分步均勻，bucket的值一般取質數。但事實證明，質數實際上并不是散列bucket的理想容量，近來Java散列實現都使用2的冪，具體如何驗證以后再續。
3.HashMap的性能因子
容量(capacity): 散列表中bucket的數量。
初始化容量(initial capacity): 創建散列表時bucket的數量。可以在構造方法中指定HashMap和HashSet的初始化容量。
尺寸(size): 散列表中記錄的數量。(數組的元素個數，非list中元素總和)
負載因子(load factor): 尺寸/容量。負載因子為0，表示空的散列表，0.5表示半滿的散列表。輕負載的散列表具有沖突少，適宜插入與查詢的特點，但是使用迭代器遍歷會比較慢。較高的負載會減少所需空間大小。當負載達到指定值時，容器會自動成倍地增加容量，并將原有的對象重新分配，存入新的bucket中，這個過程稱為“重散列”。
4.重寫hashCode()的關鍵
(1) 對同一個對象調用hashCode()都應該生成同樣的值。
(2) hashCode()方法不要依賴于對象中易變的數據，當數據發生變化時，hashCode()就會生成一個不同的散列碼，即產生了一個不同的label。
(3) hashCode()不應依賴于具有唯一性的對象信息，例如對象地址。
(4) 散列碼應該更關心速度，而不是唯一性，因為散列碼不必是唯一的。
(5) 好的hashCode()應該產生分步均勻的散列碼。在Effective Java(Addison-Wesley 2001)中，Joshua Bloch給hashCode()給出了設計指導，可以參考。
編寫正確高效的hashCode()和equals()可以參考Apache的Jakarta Commons項目中的工具。
posted on 2007-08-14 19:56
歲月如歌 閱讀(595)
評論(0) 編輯 收藏 所屬分類:
java