Java 集合框架
目錄
集合結構圖
Java 中集合又叫做容器，主要分為兩大陣營：Collection、Map；前者用來存放單一元素，後者用來存放鍵值對；
- Collection 主要包含兩個集合類(1. List，List 集合的特點是，元素是有序的，可重複的) (2. Set 元素是無序的，不可重複的集合)
- Map（映射）雙列數據，保存映射關係的集合 也就是傳說中的 key-value 鍵值對兒
Collection 的主要實現介面有 List、Set、Queue；
List、Set、Map、Queue四者的區別
- List 存儲元素是有序的，可重複的！可以存放多個空值！
- Set 存儲的元素是無序的，不可重複的。可以存放一個 null 值，TreeSet 涉及到排序所以不可以存放 null；
- Queue 按照特定的排隊規則進行排序，存儲的元素是有序的、可重複的；
- Map 是用來存儲鍵值對的，只能存放一個 null 值（因為其他的會被覆蓋掉）；HashTable、TreeMap 依然不可以存放空值；
Collection 與數組的區別
數組的特點
- 數組一旦初始化就無法進行擴充，無法改變其數組長度和數據類型；
- 數組提供給我們的處理方法也是很少的，對於插入刪除等操作還是非常的麻煩的；
- 數組中存儲數據的特點是：有序性、可重複；
Collection 集合介面中常用的方法
@Test
public void test1() {
// 1. add(Object obj); 添加一個元素 注意 在Collection介面的實現類對象中
// 添加obj時,要求obj所在的類必須重寫equals()方法
java.util.Collection coll = new ArrayList();
coll.add(132);
System.out.println(coll); // [132]
// 2. addAll(Collection coll); 添加一個Collection的集合的全部元素到現有的集合中
java.util.Collection coll1 = new ArrayList();
coll1.add(555);
coll1.addAll(coll);
System.out.println(coll1); // [555, 132]
// 3. int size(); 返回集合中元素的個數
System.out.println(coll.size()); // 1
System.out.println(coll1.size()); // 2
// 4. void clear(); 清空集合
coll1.clear();
System.out.println(coll1.size()); // 0
// 5. boolean isEmpty(); 判斷是否為空集合
System.out.println(coll.isEmpty()); //false
System.out.println(coll1.isEmpty()); //true
// 6. boolean contains(Object obj); 底層是通過元素調用equals()方法,
// 判斷是否為同一個對象
// 注意,在用contains()方法查看集合中是否有該對象時,
// 會直接調用該對象所在類的equals()方法
// 此處用String時因為String類中對equals()類進行了重寫
coll.add(new String("hello"));
boolean hello = coll.contains(new String("hello"));
System.out.println(hello); //true
// 7. boolean containsAll(Collection coll);
// 底層是通過調用equals()方法,對集合里的元素挨個比較
// 判斷形參coll中的所有元素是否都在當前集合中
coll1.add(555);
coll.add(555);
coll1.add(new String("hello"));
boolean b = coll.containsAll(coll1);
System.out.println(coll); // [132, hello, 555]
System.out.println(coll1); // [555, hello]
System.out.println(b); // true
// 7. boolean remove(Object obj); 通過元素的equals()方法判斷
// 是否是要刪除的那個元素,只會刪除找到的第一個元素
coll.remove(555);
System.out.println(coll); // [132, hello]
// 8. boolean removeAll(Collection coll);取當前集合與形參里集合的差集
coll.removeAll(coll1);
System.out.println(coll); // [132]
// 9. retainAll(Collection coll);獲取當前集合對象和形參里集合的交集,
// 並返回給調用者
java.util.Collection coll2 = Arrays.asList(132, 563);
coll.retainAll(coll2);
System.out.println(coll); // [132]
// 10. equals(Object obj); 比較兩個集合里的元素是否一樣
// 這裡要注意區分 集合是否有序
// 11. hashcode(); 返回當前對象的哈希值
// 12. toArray(); 集合-->數組
Object[] objects = coll2.toArray();
System.out.println(Arrays.toString(objects));
// 13. 數組-->集合 Arrays.asList();
List list = Arrays.asList(45, 66, 48, "hello world");
System.out.println(list); //[45, 66, 48, hello world]
System.out.println("長度為:" + list.size());//長度為:4
List<String> list1 = Arrays.asList(new String[]{"hello java","你好"});
System.out.println(list1); //[hello java, 你好]
System.out.println("長度為:" + list1.size()); //長度為:2
List list3 = Arrays.asList(new int[]{1, 3, 5});
System.out.println("長度為:" + list3.size()); //長度為:1
List list4 = Arrays.asList(new Integer[]{154, 15, 33, 46});
System.out.println(list4); //[154, 15, 33, 46]
System.out.println("長度為:" + list4.size()); //長度為:4
}
遍歷集合
Iterator 遍歷集合，用於遍歷 Collection 集合
注意：集合對象每次調用 iterator() 都會得到一個全新的迭代器；
方式一
通過for循環遍歷 不推薦使用
for (int i = 0; i < list4.size(); i++) {
System.out.println("第"+ (i+1) +"個元素"+ iterator.next());
}
方式二
通過配合迭代器的 hasNext() 方法使用 while 循環進行遍歷
hasNext() 判斷下一個位置是否有元素
while (iterator.hasNext()) {
// next(),將指針下移,並輸返回下移後位置上的元素
System.out.println(iterator.next());
}
Collection 的子介面 List
List 正如我們上面提到的，元素是有序的，可重複的，底層是數組。但是也是需要重寫 equals( ) 方法的，因為判斷元素是否存在的時候是需要的；
List介面主要有三個實現類
概述
- ArrayList 作為一個 List 介面的主要實現類而存在，也是我們平時用的比較多的一個集合類；
- LinkedList 雙向鏈表(1.6包括之前為循環鏈表)，具體的 LinkedList 我們下面會做具體分析；
- Vector 是作為 List 介面的一個古老的實現類而存在的；
差異
相同點：都實現了 List 介面，切都遵循 List 的特點，元素有序，且可重複；
不同點：
- ArrayList 作為 List 介面的主要實現類，是執行緒不安全的，但是效率極高（底層使用Object {} elementData 存儲數據）；
- LinkedList 對於頻繁的插入刪除操作來說，比 ArrayList 的效率高得多，因為其底層實現是雙向鏈表；
- Vector 作為一個古老的實現類而存在，執行緒安全，但效率底下，底層視同 Object {} elementData 存儲數據；
對於 ArrayList 的源碼簡略分析
基於 jdk1.7 ArrayList list = new ArrayList(); 底層創建了長度為 10 的 Object [ ] 數組 ElementData，然後直接對創建好的數組進行賦值,如果不夠則進行擴容（默認情況下擴容為原來的 1.5 倍），同時將原來的數組複製到新的數組當中；
基於 jdk1.8 ArrayList list = new ArrayList(); 底層數組進行了初始化，Object [ ] elementData 初始化為{ } ，並沒有創建長度，當第一次調用 add()；添加元素時，底層才進行了創建長度為 10 的數組,並將數據添加到數組當中.後面的操作則與 jdk1.7 無異
jdk1.7 中的 ArrayList 的對象的創建類似於單例的餓漢式，而 jdk1.8 中的 ArrayList 的對象的創建類似於單例模式的懶漢式,延遲了數組的創建,節省記憶體；
結論：建議使用帶有參數的構造器：ArrayList list = new ArrayList(int capacity);直接初始化容量；
對 LinkedList 的源碼分析
LinkedList list = new LinkedList(); 內部聲明了 Node 類型的 first 和 last 屬性,默認值為 null，list.add(); 將對象封裝到 Node 中,創建了 Node 對象
Node 的定義體現了 LinkedList 的雙向鏈表的說法
private static class Node<E> {
E item; // 數據
Node<E> next; // 下一個值
Node<E> prev; // 上一個值
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
List 介面特有的常用方法
總結:常用方法
// 增
add(Object obj);
// 刪
remove(int index);
remove(Object obj));
// 改
set(int index,Object ele);
// 查
get(int index)
// 插
add(int index,Object ele)
// 長度
size()
// 遍歷
Iterator // 迭代器
增加元素
@Test
public void test() {
ArrayList list = new ArrayList();
list.add(123);
list.add(556);
list.add("hello");
list.add(new person("小紅", 23, "女"));
System.out.println(list);
//[123, 556, hello, person{name='小紅', age=23, sex='女'}]
}
在指定索引位置插入 ele 元素 add(int index,ele)；
@Test
public void test1() {
ArrayList list = new ArrayList();
list.add(123);
list.add(556);
list.add("hello");
list.add(new person("小紅", 23, "女"));
System.out.println(list);// [123, 556, hello, person{name='小紅', age=23, sex='女'}]
list.add(2, new person("小黃", 22, "男"));
System.out.println(list);
// [123, 556, person{name='小黃', age=22, sex='男'}, hello, person{name='小紅', age=23, sex='女'}]
}
從指定索引位置開始將 eles 中的所有元素都添加進來
@Test
public void test2() {
ArrayList list = new ArrayList();
ArrayList list1 = new ArrayList();
list.add(123);
list.add(556);
list.add("hello");
list.add(new person("小紅", 23, "女"));
list1.add(45);
list1.add(36);
list1.add(86);
System.out.println(list1); // [45, 36, 86]
list1.addAll(2, list);
System.out.println(list1);// [45, 36, 123, 556, hello, person{name='小紅', age=23, sex='女'}, 86]
}
取指定索引位置的元素 get(int index)
@Test
public void test3() {
ArrayList list = new ArrayList();
list.add(123);
list.add(556);
list.add("hello");
list.add(new person("小紅", 23, "女"));
System.out.println(list);// [123, 556, hello, person{name='小紅', age=23, sex='女'}]
System.out.println(list.get(3)); // person{name='小紅', age=23, sex='女'}
}
返回 obj 在集合中首次出現的位置 int indexOf(Object obj); 返回 obj 在當前集合首次出現的位置
@Test
public void test4() {
ArrayList list = new ArrayList();
list.add(123);
list.add(556);
list.add("hello");
System.out.println(list.indexOf(556)); // 1
}
返回 obj 在集合中最後一次出現的位置
@Test
public void test5() {
ArrayList list = new ArrayList();
list.add(123);
list.add(123);
list.add(556);
list.add(556);
list.add(123);
list.add("hello");
System.out.println(list.lastIndexOf(123)); // 4
}
移除指定索引位置的元素,並返回該元素 Object remove(int index);
@Test
public void test6() {
ArrayList list = new ArrayList();
list.add(123);
list.add(123);
list.add(556);
System.out.println("移除前:" + list); // 移除前:[123, 123, 556]
Object remove = list.remove(2);
System.out.println("移除的值為:" + remove); // 移除的值為:556
System.out.println("移除後:" + list); // 移除後:[123, 123]
}
指定索引位置的元素設置為 ele
@Test
public void test7() {
ArrayList list = new ArrayList();
list.add(123);
list.add(123);
list.add(556);
System.out.println("設置前:" + list); // 設置前:[123, 123, 556]
list.set(0, new person("小明", 23, "男"));
System.out.println("設置後:" + list); // 設置後:[person{name='小明', age=23, sex='男'}, 123, 556]
}
返回指定區間的集合的子集合 List subList(int fromIndex,int toIndex);
@Test
public void test8() {
ArrayList list = new ArrayList();
list.add(123);
list.add(556);
list.add("hello");
list.add(new person("小紅", 23, "女"));
List list1 = list.subList(1, 3);
System.out.println(list); //[123, 556, hello, person{name='小紅', age=23, sex='女'}]
System.out.println(list1); //[556, hello]
}
Set介面
Set 介面是 Collection 的子介面，Set 介面沒有提供額外的方法，Set 存儲無序的、不可重複的數據
- Set 介面中不允許包含相同的元素(無序且唯一)，若強行添加會使得添加操作失敗
- Set 判斷兩個對象是否相同只能調用equals();
所以，Set是嚴格的
要求：
- 在 Set 中添加的數據一定要重寫 equals()、hashCode();
- 重寫的 equals( )、hashCode( )，保證相同的對象的哈希值是相同的，即 equals( ) 與 hashCode( ) 返回值都是true
無序性以及不可重複性的理解：
底層數據的存儲依然是以數組的形式進行存儲，但是無序不等於隨機，當我們添加數組的時候，並不是按照數組的索引進行添加，而是根據哈希值進行添加。
存數據的過程
- 如果計算的哈希值不同，則表明數據不一樣，直接添加成功，
- 如果計算的哈希值相同，那麼就會調用其equals();進行比較，如果經過equals();比較後返回的值不是true那麼證明不一樣，添加成功。
- 如果哈希值相同，equals返回為false，那麼就會在對應的哈希值的位置以鏈表的方式添加數據。以鏈表的方式添加數據的
針對上述的第三種情況又有：
規則,新的 hash 值相同的元素放在同一個位置的數組裡，其順序在jdk7.0/8.0中有些許不同
- 基於JDK7.0：新的元素放到數組中，並指向原來的舊元素
- 基於JDK8.0：原來的元素在數組中，指向新的元素
總結：七上八下(指的是 新元素的存放位置，七、新的元素放在原來的數組的位置(上邊)，舊的元素向下移動，在鏈表中，新的元素指向舊的元素； 八、新的元素放在鏈表中，在鏈表中，舊的指向新的)
Set介面有三個實現類:
- HashSet 基於 HashMap（底層是 數組 + 鏈表） 實現的，底層使用 HashMap 來保存元素，作為 Set 介面的主要實現類，執行緒不安全；
- LinkedHashSet 作為 HashSet 的子類，遍歷其中的元素，可以按照添加順序來遍歷，對於頻繁的遍歷操作，效率高於 HashSet，是因為在 HashSet 的基礎上在數組給每個元素都加上了指針，使數據變成雙向鏈表。
- TreeSet 可以按照對象的指定屬性進行排序，要求添加的數據是相同類的對象
Set的實現類 HashSet 的實現以及練習
@Test
public void test1() {
Set set = new HashSet();
set.add("hello");
set.add(123);
set.add("abc");
set.add(123);
set.add(new person("小紅", 29, "男"));
set.add(new person("小紅", 29, "男"));
Iterator iterator = set.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
}
輸出結果
abc
person{name='小紅', age=29, sex='男'}
hello
123
LinkedHashSet 是 HashSet 的子類，根據添加元素的順序來遍歷集合
@Test
public void test2() {
Set set = new LinkedHashSet();
set.add("hello");
set.add(123);
set.add("abc");
set.add(123);
set.add(new person("小紅", 29, "男"));
set.add(new person("小紅", 29, "男"));
Iterator iterator = set.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
}
輸出結果
hello
123
abc
person{name='小紅', age=29, sex='男'}
TreeSet，向 TreeSet 中添加數據，要求是相同類的對象，兩種排序方式：自然排序、訂製排序
自然排序中，比較兩個對象是否相同的標準為：compareTo() 返回 0 ，而不再是 equals() 方法
訂製排序中，比較兩個對象是否相同的標準是 compare() 但是規則是一樣的
@Test
public void test3() {
//編寫比較規則
Comparator comparator = new Comparator() {
@Override
public int compare(Object o1, Object o2) {
if (o1 instanceof person && o2 instanceof person) {
person p1 = (person) o1;
person p2 = (person) o2;
return p1.getName().compareTo(p2.getName());
} else {
throw new RuntimeException("數據異常！");
}
}
};
//應用比價規則
TreeSet treeSet = new TreeSet(comparator); //在有參數的情況下，會根據參數對象中所定義的排序方式進行排序，
// 若沒有，將會按照添加的對象中實現的comparable介面後重寫的compareTo();的規則進行排序
treeSet.add(new person("孔乙己", 33, "女"));
treeSet.add(new person("祥林嫂", 22, "男"));
treeSet.add(new person("魯迅", 18, "女"));
Iterator iterator = treeSet.iterator();//通過age進行自然排序
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
}
輸出結果：
person{name='孔乙己', age=33, sex='女'}
person{name='祥林嫂', age=22, sex='男'}
person{name='魯迅', age=18, sex='女'}
Map
Map，並列於 Collection 介面，用於存儲雙列數據（鍵值對 key – value）
- HashMap 作為 Map 的主要實現類存在，與 ArrayList 的存在地位相似，執行緒不安全、但是效率高，可以存儲一個 null 的 key – value，key 所在的類要重寫equals( ) 和 hashCode( )；
- LinkedHashMap，HashMap 的子類、Map 的實現類，在 HashMap 的底層基礎上，添加了指針，構成鏈表，對於頻繁的遍歷操作，執行效率高於 HashMap
- TreeMap 按照添加的 key-value 對進行排序，實現排序遍歷，底層的實現是紅黑樹；
- Hashtable 作為古老的實現類，執行緒安全、效率低下，不能夠存儲空的 key-value；
- Properties，常用來處理配置文件，key-value 都是 String 類型；
HashMap 的底層:
數組+鏈表（jdk7及以前）
數組+鏈表+紅黑樹（jdk8+）
對於 Map 結構的理解：
- Map 中的 key：無序的、不可重複的、使用 Set 存儲所有的 key ；
- Map 中的 value：無序的、可重複的，使用 Collection 存儲所有的 value，value 所在的類要重寫 equals( )；
- 一個鍵值對：key-value 構成一個 Entry 對象；
- Map 中的 entry：無序的、不可重複的，使用 Set 存儲所有的 entry；
對 Map 底層原理的理解
JDK7為例說明：
HashMap map = new HashMap(); 在實例化之後，底層創建了一個長度為 16 的一維數組 Entry [ ] table。
當我們往 HashMap 中添加數據的時候 map.put(ket1,value1);
- 首先調用 key1 所在類的 hashCode() 計算哈希值，若哈希值所對應的 Entry 數組的位置上的數據為空，那麼此時的(key1,value)添加成功；
- 如果哈希值對應的 Entry 數組對應的位置上不為空(意味著此位置上存在一個或多個數據—以鏈表的形式存在)，繼續通過equals()與其他已經存在的值進行比較，如果返回 false，那麼添加成功，如果返回值為 true，那麼會用新的的 value 替換舊的；
- 以上哈希值相同的情況均以鏈表的方式進行存儲（遵循七上八下）
- 在不斷地添加過程中會涉及擴容問題，當 size 超出臨界值且要存放的位置非空，擴容為原來的兩倍，並將原來的數據複製過來；
JDK8 在底層與JDK7的不同之處：
new HashMap();底層沒有創建一個長度為16的數組- JDK8 底層的數組是 Node [ ]，而非 Entry[ ]；
- 首次使用 put()，的時候，底層創建長度為 16 的數組
- jdk7 底層結構只有：數組+鏈表。而 JDK8 底層結構為 數組+鏈表+紅黑樹。
- 當數組的某一個索引位置上的元素以鏈表的形式存在的數據個數 > 8，且當前數組的長度>64時，此時此索引位置上的所有數據改為紅黑樹存儲
底層主要關鍵字
- DEFAULT_INITIAL_CAPACITY (初始默認容量)：HashMap的默認容量：16
- DEFAULT_LOAD_FACTOR(HashMap的默認載入因子)：0.75
- threshold(擴容的臨界值):容量*擴容因子：16 X 0.75 = 12
- TREEIFY_THRESHOLD_THRESHOLD:Bucket中鏈表長度大於該默認值，就轉化為紅黑樹：8
- MIN_TREEIFY_CAPACITY： 桶中的Node被樹化時最小的hash表容量：64
