在編程語言中，集合是指代表一組對象的對象。Java平臺專門有一個集合框架(Collections Framework)。集合框架是指表示和操作集合的統一架構，隔離了集合的操作和實現細節。
集合框架中的集合接口主要分為兩大部分，一部分繼承自java.util.Collection，另一部分繼承自java.util.Map （其實Map本質上并不是集合，只是看起來好像可以像集合一樣操作）。一個有趣的事情是這些接口的實現不一定都需要實現這些接口中的修改方法（如add，remove等），可以給某些不想實現的修改方法拋出一個運行時異常(UnsupportedOperationException)。
List
List是Java中的一個接口，繼承了Collection接口。它是一個有序集合，又稱序列，允許存儲重復元素。其實現類常用的有ArrayList、LinkedList等。ArrayList是實現了List接口的可變長數組。它的特點是add方法操作時間復雜度為分期常量時間（amortized constant time），意思即如果添加n個元素則耗時O(n)，其它操作耗時則是線性時間。每個ArrayList都有個容量，即存放元素能力的大小。這個容量是list中元素個數。當添加新的元素時，這個容量也會自動添加，這需要消耗一定時間。如果要添加大量數據到ArrayList，可以先調用ensureCapacity操作，從而減少每次添加新元素容量自動調整的時間。
需要注意的是ArrayList并不是線程同步的。如果多個線程同時訪問一個ArrayList實例，至少一個線程修改了其結構（添加或刪除元素，或顯式的調整了其大小，僅僅設置元素值并不屬于結構修改），則會使程序進入不確定的狀態。解決方式之一就是使用一個線程同步的對象來封裝該ArrayList。或者也可以用Collections.synchronizedList來封裝。
1
|
|
實現原理就是Collections.synchronizedList返回的類的iterator做了特殊處理。如果iterator被創建后，除了自己的add和delete方法，有其他行為導致了List結構被修改，iterator將會拋出一個ConcurrentModificationException異常。當然iterate這種處理方式并不能擔保它能處理所有的異步并發修改，只能降低程序陷入不確定狀態的概率。
LikedList是一個雙重鏈表，它既實現了List接口，也實現了Deque接口。LikedList也不是線程安全的，解決方式與ArrrayList基本相同。
Set
Set也是Java中的一個接口，同樣繼承于Collection。與List不同的是，Set不允許放置重復元素,并且最多只能放置一個null元素。其實現類有HashSet、TreeSet等。
HashSet的實現其實是依托了一個HashMap的實例。HashSet并不保證元素的迭代順序每次都是一致的。HashSet的基本操作（add,remove,contains及size）耗時都是常數時間，即迭代Set的耗時與Set的大小乘以HashMap實例的乘積成正比。HashSet也不是線程安全的。
Map
Map則是另一種重要的數據結構，是一組鍵值對的集合。Map不允許有重復的key存在。 它的實現中有HashTable和HashMap。兩者非常相似，最大的不同是HashMap不是線程安全的，并且允許null值作為key或value，而HashTable則不允許。
HashMap的性能取決于兩個因素：一個是初始容量，一個是負載因數。容量是哈希表中bucket的數量。初始容量則是HashMap被創建時容量。負載因數則是當容量需要自動增加的閥值。當HashMap中的元素超過了負載因數和當前容量的乘積，HashMap則會重新進行hash計算，以便bucket數量增加到以前的近似兩倍。一般負載因子的默認值是0.75，這能達到時間和空間的一個平衡。負載因子過大，雖然會減少空間消耗，但是增加查找時間。
文章列表
留言列表
