集合-2（Set（HashSet、TreeSet、LinkedHashSet）、List（ArrayList、LinkedList、Vector）、Map（HashMap、TreeMap...））
1.Set接口
集合中的元素不能重復，所以存入Set的元素都必須定義equals()來確保對象的唯一性。
無序、無索引
1.1HashSet類
實現了Set接口，此實現不是同步的。
由哈希表支持。實際上是一個HashMap集合。
不能保證迭代順序和存儲順序一致。特別是它不保證該順序恒久不變。
保證元素唯一的方式：hashCode()和equals()（若為自定義類，需重寫兩個方法）。
假定哈希函數將這些元素正確地分布在桶中。對此 set 進行迭代所需的時間與 HashSet 實例的大小（元素的數量）和底層 HashMap 實例（桶的數量）的“容量”的和成比例。因此，如果迭代性能很重要，則不要將初始容量設置得太高（或將加載因子設置得太低）。
1.1.1哈希表
底層使用數組機制。
數組中存放對象
由對象的特有數據結合相應的算法（Object中為hashCode()），計算出此對象在數組中的位置。
哈希沖突
2個對象計算出的hashCode()結果一樣。
則調用此對象的equals()，判斷兩個對象是否一樣。
- 一樣，不存第二個，
- 不一樣，存
1.2TreeSet
使用元素的自然順序對元素進行排序，或者根據創建 set 時提供的 Comparator 進行排序，具體取決于使用的構造方法。
此實現為基本操作（add、remove 和 contains）提供受保證的 log(n) 時間開銷。
此實現不是同步的。
1.2.1構造方法
TreeSet(Collection<T> coll)：構造一個包含指定 collection 元素的新 TreeSet，它按照其元素的自然順序進行排序。
1.2.1方法
E ? last()：?返回此 set 中當前最后一個（最高）元素。
E? first()：返回此 set 中當前第一個（最低）元素。
1.3LinkedHashSet
HashSet的子類。
數據存儲結構：鏈表+哈希表
保證元素的存取和取出順序一致。
2.List接口
有序的 collection（也稱為序列）。
此接口的用戶可以對列表中每個元素的插入位置進行精確地控制。
用戶可以根據元素的整數索引（在列表中的位置）訪問元素，并搜索列表中的元素。
通常允許重復的元素。列表通常允許滿足 e1.equals(e2) 的元素對 e1 和 e2，并且如果列表本身允許 null 元素的話，通常它們允許多個 null 元素。
ListIterator listIterator() ：返回此列表元素的列表迭代器（按適當順序）。
2.1 ArrayList
List 接口的大小可變數組的實現.
此類大致上等同于 Vector 類，除了此類是不同步的。
每個 ArrayList 實例都有一個容量。該容量是指用來存儲列表元素的數組的大小。它總是至少等于列表的大小。隨著向 ArrayList 中不斷添加元素，其容量也自動增長。并未指定增長策略的細節。
在添加大量元素前，應用程序可以使用 ensureCapacity 操作來增加 ArrayList 實例的容量。這可以減少遞增式再分配的數量。
2.1.1構造方法
ArrayList()：構造一個初始容量為 10 的空列表。
ArrayList(Collection<E> coll)：?構造一個包含指定 collection 的元素的列表，這些元素是按照該 collection 的迭代器返回它們的順序排列的。
ArrayList(int initialCapacity)；構造一個具有指定初始容量的空列表。
2.1.2常用方法
boolean add(E e)：將指定的元素添加到此列表的尾部
void add(int index,E e)：將指定的元素插入此列表中的指定位置。原位置元素后移。
boolean add(int index,Collection<E> coll)：從指定的位置開始，將指定 collection 中的所有元素插入到此列表中。
E remove(int index)：移除此列表中指定位置上的元素。并返回被刪除的元素。
E set(int index,E e)：用指定的元素替代此列表中指定位置上的元素。返回此位置上的原元素。
- ArrayList的contains()方法源碼：
2.2LinkedList
List 接口的鏈接列表實現。
采用雙向列表實現的，對數據的索引需要從列表頭開始遍歷，隨機訪問效率低；插入元素時不需要對數據進行移動，所以插入效率高。LinkedList是非線程安全的容器。
此類實現 Deque 接口，為 add、poll 提供先進先出隊列操作，以及其他堆棧和雙端隊列操作。
此實現不是同步的。
2.2.1構造方法
LinkedList()：構造一個空的列表。
LinkedList(Collection<E> coll)：構造一個包含指定 collection 中的元素的列表，這些元素按其 collection 的迭代器返回的順序排列。
2.2.2 方法
E peek()：獲取但不移除此列表的頭（第一個元素）。
E peekFirst()：獲取但不移除此列表的第一個元素；如果此列表為空，則返回 null。
E peekLast()：獲取但不移除此列表的最后一個元素；如果此列表為空，則返回 null。
E poll()：獲取并移除此列表的頭（第一個元素）——E pollFirst()、E pollLast()
E pop()：從此列表所表示的堆棧處彈出一個元素。
void push(E e)：?將元素推入此列表所表示的堆棧。
boolean offer(E e)：?將指定元素添加到此列表的末尾（最后一個元素）?！猙oolean offerFirst()、boolean offerLast()
2.3 Vector
可以實現可增長的對象數組。Vector 是同步的
與數組一樣，它包含可以使用整數索引進行訪問的組件。但是，Vector 的大小可以根據需要增大或縮小，以適應創建 Vector 后進行添加或移除項的操作。
每個向量會試圖通過維護 capacity 和 capacityIncrement 來優化存儲管理。
- capacity 始終至少應與向量的大小相等；這個值通常比后者大些，因為隨著將組件添加到向量中，其存儲將按 capacityIncrement 的大小增加存儲塊。
- 應用程序可以在插入大量組件前增加向量的容量；這樣就減少了增加的重分配的量。
2.3.1構造方法
Vector()：構造一個空向量，使其內部數據數組的大小為 10，其標準容量增量為零。
Vector(Collection<E> coll)：構造一個包含指定 collection 中的元素的向量，這些元素按其 collection 的迭代器返回元素的順序排列。
Vector(int initialCapacity)：使用指定的初始容量和等于零的容量增量構造一個空向量。
Vector(int initialCapacity, int capacityIncrement)：使用指定的初始容量和容量增量構造一個空的向量。
2.3.2方法
void copyInto(Object[] obj)：將此向量的組件復制到指定的數組中。
void trimTosIZE()：對此向量的容量進行微調，使其等于向量的當前大小。
取出方法：枚舉Enumeration
沒有一個ArrayList的方法是同步的，而Vecotr的絕大多數方法（例如，add、insert、remove、set、equals、hashCode等）都是直接或間接同步的，所以Vector是線程安全的，ArrayList不是線程安全的。性能上ArrayList較好。
2.4總結
- 主要操作為：索引、只在集合末尾增刪元素——使用ArrayList和Vector
- 主要操作為：指定位置的插入刪除——LinkedList
- 多線程——Vector
3.Map接口
將鍵映射到值的對象。一個映射不能包含重復的鍵；每個鍵最多只能映射到一個值。
Map 接口提供三種collection 視圖，允許以鍵集、值集或鍵-值映射關系集的形式查看某個映射的內容。
某些映射實現可明確保證其順序，如 TreeMap 類；另一些映射實現則不保證順序，如 HashMap 類。
所有通用的映射實現類應該提供兩個“標準的”構造方法：
- 一個 void（無參數）構造方法，用于創建空映射；
- 一個是帶有單個 Map 類型參數的構造方法，用于創建一個與其參數具有相同鍵-值映射關系的新映射。
- 實際上，后一個構造方法允許用戶復制任意映射，生成所需類的一個等價映射。
- 盡管無法強制執行此建議（因為接口不能包含構造方法），但是 JDK 中所有通用的映射實現都遵從它。
3.1方法
boolean containsKey(Object key)：如果此映射包含指定鍵的映射關系，則返回 true。
boolean containsVlue(Object value)：?如果此映射將一個或多個鍵映射到指定值，則返回 true。
Set<Map,Entry<K,V>> enctrySet()：返回此映射中包含的映射關系的 Set 視圖。
V get(Object key)：?返回指定鍵所映射的值；如果此映射不包含該鍵的映射關系，則返回 null。
Set<K> getKey()：?返回此映射中包含的鍵的 Set 視圖。
V put(K key,V value)：??將指定的值與此映射中的指定鍵關聯（可選操作）。
Collections<V> values()：?返回此映射中包含的值的 Collection 視圖。
3.2Map集合的遍歷
3.2.1鍵找值的方式
Set<String> keySet=map.keySet();Iterator<String> it=keySet.iterator();while(it.hasNext()){String key=it.next();String value=map.get(key); }3.2.2 Entry鍵值對對象
Entry：Map的內部類
將鍵值對封裝成了對象，可以從每個鍵值對對象獲取對應的鍵和值。
步驟：
Map集合不能使用增強for進行遍歷，但轉成Set后就可使用。
3.3HashMap
基于哈希表的 Map 接口的實現。此實現不是同步的。
允許使用 null 值和 null 鍵。（除了非同步和允許使用 null 之外，HashMap 類與 Hashtable 大致相同。）
此類不保證映射的順序。
HashMap 的實例有兩個參數影響其性能：初始容量 和加載因子。
- 容量 是哈希表中桶的數量，
- 初始容量只是哈希表在創建時的容量。
- 加載因子 （默認是0.75）是哈希表在其容量自動增加之前可以達到多滿的一種尺度。
- 當哈希表中的條目數超出了加載因子與當前容量的乘積時，則要對該哈希表進行 rehash 操作（即重建內部數據結構），從而哈希表將具有大約兩倍的桶數。
3.3.1構造方法
HashMap()：構造一個具有默認初始容量 (16) 和默認加載因子 (0.75) 的空 HashMap。
?HashMap(int initialCapacity)：構造一個帶指定初始容量和默認加載因子 (0.75) 的空 HashMap。
HashMap(int intialCapacity,float loadFactor)：?構造一個帶指定初始容量和加載因子的空 HashMap。
HashMap(Map<K,V> m)：構造一個映射關系與指定 Map 相同的新 HashMap。
3.3.2?HashMap添加元素
當新增加的key的hash值已存在于HashMap中時，會產生沖突。一般而言，對于不同的Key值可能會得到相同的hash值，所以應對沖突進行處理。處理沖突的方法：
- 開放地址法；
- 再hash法；
- 鏈地址法。
3.3.3HashMap使用鏈地址法解決沖突的具體操作
3.3.4?向HashMap中添加元素時，若遇到沖突，解決方式如圖
Object類的equals()比較規則：當參數obj引用的對象與當前對象為同一個對象時，就返回true，否則返回false。
hashCode()會返回對象存儲的內存地址。
為了實現向HashMap中添加鍵值對，可以根據對對象的內容來判斷兩個對象是否相等，就需重寫hashCode()和equals()。
import java.util.*;class Person{String id;String name;public int hachCode() {return id.hashCode();}public Person(String id,String name) {this.id=id;this.name=name;}public String toString() {return "id="+id+",name="+name;}public boolean equals(Object obj) {Person p=(Person)obj;if(p.id.equals(this.id))return true;elsereturn false;} }public class Test{public static void test() {System.out.println("Use String as key:");HashMap<Person,String> hm=new HashMap<Person,String>();Person p1=new Person("111","name1");Person p2=new Person("222","name2");hm.put(p1,"address1");hm.put(p2,"address2");Iterator iter=hm.entrySet().iterator();while(iter.hasNext()) {Map.Entry entry=(Map.Entry)iter.next();Person key=(Person)entry.getKey();String val=(String)entry.getValue();System.out.println("key:"+key+",value："+val);}}public static void main(String[] args) {test();} }運行結果
Use String as key:
key:id=111,name=name1,value：address1
key:id=222,name=name2,value：address2
使用自定義類作為HahsMap的key時，需注意：
3.3.5總結
根據鍵的hashCode值存儲數據，由鍵可以很快得到它的值，訪問速度快。
存的鍵值對沒有固定順序，取出時是隨機的。
適合在Map中插入、刪除和定位元素。
采用“強引用”，只有這個key從HashMap中刪除后，才能被垃圾回收器回收。
使用最多的。
3.4TreeMap
基于紅黑樹（Red-Black tree）的 NavigableMap 實現。此實現不是同步的。
實現了SortMap接口，能夠將記錄根據鍵值對排序保存，取出來時是排好序后的鍵值對。適用于需要按自然順序或自定義順序遍歷鍵。
該映射根據其鍵的自然順序進行排序，或者根據創建映射時提供的 Comparator 進行排序，具體取決于使用的構造方法。?
此實現為 containsKey、get、put 和 remove 操作提供受保證的 log(n) 時間開銷
3.4.2構造方法
TreeMap()：使用鍵的自然順序構造一個新的、空的樹映射。
TreeMap(Comparator< K>?comparator)：構造一個新的、空的樹映射，該映射根據給定比較器進行排序。
TreeMap(Map<K,V>?m)：構造一個與給定映射具有相同映射關系的新的樹映射，該映射根據其鍵的自然順序 進行排序。
TreeMap((SortedMap<K,V>?m)：構造一個與指定有序映射具有相同映射關系和相同排序順序的新的樹映射。
3.4.3方法
Map.Entry<K,V> ceilingEntry(K key)：返回一個鍵-值映射關系，它與大于等于給定鍵的最小鍵關聯；如果不存在這樣的鍵，則返回 null。
K ceilingKey(K key)：返回大于等于給定鍵的最小鍵；如果不存在這樣的鍵，則返回 null。
Map.Entry<K,V> higherEntry(K key)：返回一個鍵-值映射關系，它與嚴格大于給定鍵的最小鍵關聯；如果不存在這樣的鍵，則返回 null。
K higherKey(K key)：返回嚴格大于給定鍵的最小鍵；如果不存在這樣的鍵，則返回 null。
lowerKey()、lowerEntry()
3.5?LinkedHashMap
HashMap的一個子類，按讀取順序排列，適用于需要輸入與輸出順序相同。
Map 接口的哈希表和鏈接列表實現，具有可預知的迭代順序。此實現不是同步的
使用它可以生成一個與原來順序相同的映射副本，而與原映射的實現無關：
void foo(Map m) {Map copy = new LinkedHashMap(m);... }提供特殊的構造方法來創建鏈接哈希映射，該哈希映射的迭代順序就是最后訪問其條目的順序，從近期訪問最少到近期訪問最多的順序（訪問順序）。這種映射很適合構建 LRU 緩存。
3.5.1構造方法
LinkedHashMap()：構造一個帶默認初始容量 (16) 和加載因子 (0.75) 的空插入順序 LinkedHashMap 實例
LinkedHashMap(int initialCapacity,int loadFactor,boolean accessOrder)：構造一個帶指定初始容量、加載因子和排序模式的空 LinkedHashMap 實例。
3.6 WeakHashaMap
與HashMap類似，key采用“弱引用”的方式，在 WeakHashMap 中，當某個鍵不再正常使用時，將自動移除其條目，被垃圾回收器回收。
- 對于一個給定的鍵，其映射的存在并不阻止垃圾回收器對該鍵的丟棄，這就使該鍵成為可終止的，被終止，然后被回收。
- 丟棄某個鍵時，其條目從映射中有效地移除。
WeakHashMap 中的值對象由普通的強引用保持
null 值和 null 鍵都被支持。
該類具有與 HashMap 類相似的性能特征，并具有相同的效能參數初始容量 和加載因子。
不同步的。
3.7Hashtable
此類實現一個哈希表，該哈希表將鍵映射到相應的值。
任何非 null 對象都可以用作鍵或值。
為了成功地在哈希表中存儲和獲取對象，用作鍵的對象必須實現 hashCode 方法和 equals 方法。
3.7.1構造方法
Hashtable()：用默認的初始容量 (11) 和加載因子 (0.75) 構造一個新的空哈希表。
3.7.2方法
?Enumeration<K> keys()：返回此哈希表中的鍵的枚舉。
3.7.3示例
它將數字的名稱用作鍵：
? Hashtable<String, Integer> numbers = new Hashtable<String, Integer>();numbers.put("one", 1);numbers.put("two", 2);numbers.put("three", 3);?要獲取一個數字，可以使用以下代碼：
Integer n = numbers.get("two"); if (n != null) {System.out.println("two = " + n); }3.8HashMap和HashTable
| HashMap | Hashtable |
| 是Hashtable的輕量級實現（非線程安全的實現） | 效率上，HashMap高于Hashtable |
| 都完成了Map接口 | 都完成了Map接口 |
| 允許空鍵值（key為null），最多只允許一條記錄的鍵為null | 不允許 |
| 去掉了Hashtable的contains方法,改成containsvalue和containsKey | ? |
| java 1.2引進的Map interface的一個實現 | 繼承自Dictionary類 |
| 不支持線程同步，所以不是線程安全的 | 線程安全的 |
| 使用Iterator | 使用Enumeration |
| hash數組默認大小是16，而且一定是2的指數 | hash默認大小是11，增加方式是old*2+1； |
| hash值的使用不同 | Hashtable使用對象的hashCode |
使用自定義類型作為HashMap或Hashtable的key需注意：
- 不能存儲重復的鍵，當有重復的鍵時，不會創建新的映射關系，而是使用先前的鍵值；
總結
以上是生活随笔為你收集整理的集合-2（Set（HashSet、TreeSet、LinkedHashSet）、List（ArrayList、LinkedList、Vector）、Map（HashMap、TreeMap...））的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 集合-1（Collection、迭代器、
- 下一篇： JVM运行时结构、Java内存管理、JV