List 、Set、 Map有什麼區別和聯繫
- list 和set 有共同的父類 它們的用法也是一樣的 唯一的不太就是set中不能有相同的元素 list中可以list和set的用途非常廣泛 list可以完全代替數組來使用map 是獨立的合集 它使用鍵值對的方式來儲存數據 鍵不能有重複的 值可以用map不像上邊兩種集合那個用的廣泛 不過在servlet 和jsp中 map可是絕對的重中之重 頁面之間傳值全靠map
List 、Set、 Map都有哪些子類
Collection
├List
│├LinkedList
│├ArrayList
│└Vector
│ └Stack
└Set
|-HashSet
└TreeSet
Map
├Hashtable
├HashMap
└WeakHashMap
- 注意：Map沒有繼承Collection接口，Map提供key到value的映射。
List
- LinkedList類LinkedList實現了List接口，允許null元素。此外LinkedList提供額外的get，remove，insert方法在 LinkedList的首部或尾部。這些操作使LinkedList可被用作堆棧（stack），隊列（queue）或雙向隊列（deque）。注意LinkedList沒有同步方法。如果多個線程同時訪問一個List，則必須自己實現訪問同步。一種解決方法是在創建List時構造一個同步的List：
List list = Collections.synchronizedList(new LinkedList(…));
特點：尋址困難，插入和刪除容易。
- ArrayList類ArrayList實現了可變大小的數組。它允許所有元素，包括null。ArrayList沒有同步。size，isEmpty，get，set方法運行時間為常數。但是add方法開銷為分攤的常數，添加n個元素需要O(n)的時間。其他的方法運行時間為線性。每個ArrayList實例都有一個容量（Capacity），即用於存儲元素的數組的大小。這個容量可隨著不斷添加新元素而自動增加，但是增長算法並 沒有定義。當需要插入大量元素時，在插入前可以調用ensureCapacity方法來增加ArrayList的容量以提高插入效率。和LinkedList一樣，ArrayList也是非同步的（unsynchronized）。特點是：尋址容易，插入和刪除困難；
- Vector類Vector非常類似ArrayList，但是Vector是同步的。由Vector創建的Iterator，雖然和ArrayList創建的 Iterator是同一接口，但是，因為Vector是同步的，當一個Iterator被創建而且正在被使用，另一個線程改變了Vector的狀態（例 如，添加或刪除了一些元素），這時調用Iterator的方法時將拋出ConcurrentModificationException，因此必須捕獲該 異常。
- Stack 類Stack繼承自Vector，實現一個後進先出的堆棧。Stack提供5個額外的方法使得 Vector得以被當作堆棧使用。基本的push和pop 方法，還有peek方法得到棧頂的元素，empty方法測試堆棧是否為空，search方法檢測一個元素在堆棧中的位置。Stack剛創建後是空棧。
Set
- HashSet類它不允許出現重複元素；不保證集合中元素的順序允許包含值為null的元素，但最多隻能有一個null元素。HashSet的實現是不同步的。
- TreeSet類TreeSet類實現 Set 接口，該接口由 TreeMap 實例支持。此類保證排序後的 set 按照升序排列元素，根據使用的構造方法不同，可能會按照元素的自然順序 進行排序，或按照在創建 set 時所提供的比較器進行排序。TreeSet描述的是Set的一種變體——可以實現排序等功能的集合，它在將對象元素添加到集合中時會自動按照某種比較規則將其插入到有序的對象序列中.HashSet是基於Hash算法實現的,其性能通常優於TreeSet,我們通常都應該使用HashSet,在我們需要排序的功能時,我門才使用TreeSet;
Map接口
- Hashtable類Hashtable繼承Map接口，實現一個key-value映射的哈希表。任何非空（non-null）的對象都可作為key或者value。
- 添加數據使用put(key, value)，取出數據使用get(key)，這兩個基本操作的時間開銷為常數。Hashtable 通過initial capacity和load factor兩個參數調整性能。通常缺省的load factor 0.75較好地實現了時間和空間的均衡。增大load factor可以節省空間但相應的查找時間將增大，這會影響像get和put這樣的操作。作為key的對象將通過計算其散列函數來確定與之對應的value的位置，因此任何作為key的對象都必須實現hashCode和equals方法。 Hashtable是同步的。
- HashMap類HashMap和Hashtable類似，不同之處在於HashMap是非同步的，並且允許null，即null value和null key。
- 其迭代子操作時間開銷和HashMap 的容量成比例,因此，不要將HashMap的初始化容量設得過高，或者load factor過低。WeakHashMap類WeakHashMap是一種改進的HashMap，它對key實行“弱引用”，如果一個key不再被外部所引用，那麼該key可以被GC回收。
- hashmap遍歷的兩種方式HashMap的遍歷有兩種常用的方法，那就是使用keyset及entryset來進行遍歷
- 方法一：
Map map = new HashMap();
Iterator iter = map.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
Object key = entry.getKey();
Object val = entry.getValue();
}
- 效率高,以後儘量要使用此種方式！
- 方法二：
Map map = new HashMap();
Iterator iter = map.keySet().iterator();
while (iter.hasNext()) {
Object key = iter.next();
Object val = map.get(key);
}
- 效率低,以後儘量少使用！HashMap的數據結構HashMap裡面實現一個靜態內部類Entry，其重要的屬性有 key , value, next.
- 數據value的值是元素的key的哈希值對數組長度取模得到。如下面第二幅圖中，12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存儲在數組下標為12的位置。結構如圖所示：
- HashMap的存取實現
// 存儲時:
int hash = key.hashCode(); // 這個hashCode方法這裡不詳述,只要理解每個key的hash是一個固定的int值
int index = hash % Entry[].length;
Entry[index] = value;
// 取值時:
int hash = key.hashCode();
int index = hash % Entry[].length;
return Entry[index];
- 解決hash衝突的辦法開放定址法（線性探測再散列，二次探測再散列，偽隨機探測再散列）
- 再哈希法
- 鏈地址法
- 建立一個公共溢出區
- Java中hashmap的解決辦法就是採用的鏈地址法。
再散列rehash過程當哈希表的容量超過默認容量時，必須調整table的大小。當容量已經達到最大可能值時，那麼該方法就將容量調整到Integer.MAX_VALUE返回，這時，需要創建一張新表，將原表的映射到新表中。
閱讀更多 譚慶波不在家 的文章
