十一、集合

1. 為什么要使用集合

(1) 數組存在的弊端

1) 數組在初始化之后，長度就不能改變，不方便擴展。

2) 數組中提供的屬性和方法比較少，不便于進行添加、刪除、修改等操作，并且效率不高，同時無法直接存儲元素的個數。

3) 數組中存儲的元素是可以重復的。

(2) Java 集合類可以用于存儲數量不等的多個對象，還可以保存具有映射關鍵的鍵值對。

(3) Java 中的集合可分為 Collection 和 Map 兩種體系

1) Collection 接口：單列數據，定義了存取一組對象的方法的集合，包含兩個子接口：

a. List 接口：元素有序，元素可重復的集合

b. Set 接口：元素無序，元素不可重復的集合

2) Map 接口：雙列數據，保存具有映射關系“key-value”對的集合

(4) Collection 接口常用的方法：

① 添加

add(Object obj)

addAll(Collection obj)

② 獲取有效元素的個數

int size()

③清空集合

void clear()

④ 判斷是否是空集合

boolean isEmpty()

⑤ 是否包含某個元素

boolean contains(Object obj)：是通過元素的equals方法來判斷是否是同一個對象

boolean containsAll(Collection c)

⑥ 刪除

boolean remove(Object obj)：也是通過equals方法來判斷

boolean removeAll(Collection c)

⑦ 求兩個集合的交集

boolean retainAll(Collection c)

⑧ 判斷兩個集合是否相等

boolean equals(Object obj)

⑨ 轉換成對象數組

Object[] toArray()

⑩ 獲取哈希碼

hashCode()

? 遍歷

iterator()：返回迭代對象

從上面的方法可以看出：集合只能接收引用數據類型（對象）

示例：Collection 接口的子接口 List 有一個實現類 ArrayList，表示數組類型的集合

package com.edu.coll;

import java.util.ArrayList;
import java.util.Collection;

public class CollectionDemo1 {

?? ?public static void main(String[] args) {
// TODO Auto-generated method stub
Collection c = new ArrayList();//向上轉型，多態
for (int i = 1; i <= 10; i++) {
c.add(new Person("姓名" + i, 20 + i));//多態性，實際上調用的是 ArrayList 的 add() 方法
}
System.out.println("集合的大小為：" + c.size());
Object[] array = c.toArray();//轉換為對象數組
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
}

}

class Person {
private String name;
private int age;

public Person() {
// TODO Auto-generated constructor stub
}

?? ?public Person(String name, int age) {
super();
this.name = name;
this.age = age;
}

?? ?public String getName() {
return name;
}

?? ?public void setName(String name) {
this.name = name;
}

?? ?public int getAge() {
return age;
}

?? ?public void setAge(int age) {
this.age = age;
}

?? ?@Override
public String toString() {
return "Person [name=" + name + ", age=" + age + "]";
}
}

課堂練習：創建一個集合，往里面放10個 Person 對象，然后刪除一個元素，再查看所有元素

package com.edu.coll;

package com.edu.coll;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Objects;

public class CollectionDemo1 {

?? ?public static void main(String[] args) {
// TODO Auto-generated method stub
Collection c = new ArrayList();//向上轉型，多態
for (int i = 1; i <= 10; i++) {
c.add(new Person("姓名" + i, 20 + i));//多態性，實際上調用的是 ArrayList 的 add() 方法
}
c.remove(new Person("姓名5", 25));//要這樣刪除就必須重寫 equals 方法，然后比較內容是否相等
System.out.println("集合的大小為：" + c.size());
Object[] array = c.toArray();//轉換為對象數組
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
}

}

class Person {
private String name;
private int age;

public Person() {
// TODO Auto-generated constructor stub
}

?? ?public Person(String name, int age) {
super();
this.name = name;
this.age = age;
}

?? ?public String getName() {
return name;
}

?? ?public void setName(String name) {
this.name = name;
}

?? ?public int getAge() {
return age;
}

?? ?public void setAge(int age) {
this.age = age;
}

?? ?@Override
public String toString() {
return "Person [name=" + name + ", age=" + age + "]";
}

/**
* 為什么重寫 equals 方法的同時一定要重寫 hashCode()？
* 原因就是相等的對象必須具有相同的哈希值(hash 值)
* equals() 沒有重寫的時候比較的是兩個對象地址值是否相等，這個時候如果兩個對象相等，那么它們沒有重寫的 hashCode?
* 也是相等的，然后 equals 方法重寫之后是比較對象的屬性內容是否相等，要保證這兩個對象的 hashCode 相等，那么也必須
* 要重寫 hashCode() 方法，從而使用對象的屬性來生成 hashCode。
*/
@Override
public int hashCode() {
return Objects.hash(age, name);
}

?? ?@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Person other = (Person) obj;
return age == other.age && Objects.equals(name, other.name);
}


}

(5) Iterator 迭代器：用于循環遍歷集合元素

1) Collection 接口繼承了 java.lang.Iterator 接口，該接口中有一個方法 iterator() 方法，所有實現 Collection 接口的集合類都有一個 iterator() 方法，可以返回 Iterator 對象

2) Iterator 對象包含三個方法，用于遍歷集合，但是需要注意：Iterator 本身并不提供承載對象的能力，如果需要創建 Iterator 對象，則必須有一個被迭代的集合，它包含的三個方法：

a. boolean hasNext()：判斷是否有下一個元素

b. Object next()：返回下一個元素

c. void remove()：刪除指定的元素

示例：

(6) foreach 循環(增強 for 循環)：

foreach 循環可用于遍歷集合和數組，它的底層也是通過 Iterator 完成

語法：

其中：

類型：待遍歷的元素的類型

變量：遍歷后自定義元素的名稱

集合/數組：待遍歷的集合或數組

(7) Collection 接口的子接口 --- List 接口

1) List 集合中元素有序，且元素可以重復，集合中的每個元素都有對應的索引。

2) List 接口常用的實現類：ArrayList、Vector、LinkedList

3) List 集合除了繼承了 Collection 接口的常用方法之外，還添加了一些根據索引來操作集合的方法，這些額外的方法有：

示例：

package com.edu.coll;

import java.util.ArrayList;
import java.util.List;

public class ListDemo1 {

?? ?public static void main(String[] args) {
// TODO Auto-generated method stub
List list = new ArrayList();//向上轉型，多態
for (int i = 0; i < 10; i++) {
list.add("集合元素" + i);//添加元素，多態性
}
//獲取第二個元素
String s2 = (String)list.get(1);//向下轉型，強轉
System.out.println(s2);

/**
* 找到"集合元素2"的索引位置：ArrayList 的 indexOf() 方法是通過 equals() 方法來比較元素的
* 因為 String 已經重寫 equals() 方法，是比較內容是否相等
*/
int i = list.indexOf(new String("集合元素2"));
System.out.println(i);

//設置索引位置3的元素值：
list.set(3, "修改后的元素值");
//取出區間[2,5)的子集合
List subList = list.subList(2, 5);
System.out.println(subList);

System.out.println();

//打印所有元素
for (Object s : list) {
System.out.println(s);
}
}

}

(8) List 的實現類（集合的難點就是在下面的源碼分析，用集合不難，但是面試會問這些底層！）

1) List 接口的實現類之一：ArrayList，其底層就是一個變長的對象數組，ArrayList 的源碼分析：

//ArrayList 實現了 List 接口
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;
//默認容量/初始容量為10
private static final int DEFAULT_CAPACITY = 10;
//一個空的 Object 類型的數組，給內部的 elementData 對象數組賦值
private static final Object[] EMPTY_ELEMENTDATA = {};
//一個空的 Object 類型的數組，給內部的 elementData 對象數組賦值
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//ArrayList 存放對象的對象數組
transient Object[] elementData; // non-private to simplify nested class access
//ArrayList 目前存放了多少個元素
private int size;

?? ?//如果 initialCapacity > 0，就是用 initialCapacity 來初始化對象數組 elementData
//否則如果 initialCapacity == 0，就是用一個空的數組來初始還 elementData
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}

//無參構造器中使用一個空的數組來初始化 elementData
//所以從這里我們可以看出：默認情況下，我們調用 ArrayList 的默認構造函數產生對象時，它此時的容量為 0，是一個空的數組
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

//用一個集合 c 來初始化 ArrayList 內部對象數組 elementData,使用 Arrays.copyOf() 將集合 c 轉換成對象數組之后拷貝到 ArrayList 內部的對象數組 elementData 中，如果此時size為0(證明傳進來的c為空)，就直接給 elementData 賦予一個空的數組
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
//將新的數據(c)以及大小 size 復制到elementData中
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}

......

//增加元素的方法
public boolean add(E e) {
//將當前元素的個數size+1之后傳入方法，如果此時容量不夠了，則需要對 elementData 進行擴容
ensureCapacityInternal(size + 1); ?// Increments modCount!!
//將元素 e 添加到 elementData 對應的下標位置，同時元素個數 size 自增
elementData[size++] = e;
return true;//返回 true
}
//然后上面的擴容方法
private void ensureCapacityInternal(int minCapacity) {
//判斷數據是否為空(調用 ArrayList 默認構造方法時就是空的)
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//將能允許的最小容量 minCapacity 取值為默認容量 10 和 允許的最小容量 minCapacity 取個最大值
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
//擴容
ensureExplicitCapacity(minCapacity);
}
//繼續看上面的擴容方法
private void ensureExplicitCapacity(int minCapacity) {
modCount++;//修改計數自增

? ? ? ? // overflow-conscious code
//如果能允許的最小容量 minCapacity 減去當前數組 elementData 的長度大于 0，證明數組當前已經不能容納更多的元素了，需要擴容
if (minCapacity - elementData.length > 0)
grow(minCapacity);//擴容
}
//然后看grow()擴容：
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;//取出數組當前的長度作為老的容量
//擴充的新的容量為老的容量的 1.5 倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果算出來的新容量比能允許的最小容量 minCapacity 都還要小，那么直接將新的容量賦值為能允許的最小容量 minCapacity
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//如果算出來的新容量比 MAX_ARRAY_SIZE 還要大，那么就調用 hugeCapacity() 來擴容
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
//然后調用 Arrays.copyOf() 將數組當前內容以及新的容量拷貝到 elementData 中
elementData = Arrays.copyOf(elementData, newCapacity);
}
//然后就是 hugeCapacity()：
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}

從上面代碼分析可知：我們通過 ArrayList 的默認構造器創建對象的時候，它此時內部的對象數組的大小為 0，是一個空的數組，然后第一次調用 add() 方法添加元素的時候，才去進行擴容，此時擴容的大小是默認的容量 10。

然后繼續分析源碼：

?? ?//返回數組的大小：數組中包含的元素的個數
public int size() {
return size;
}

//判斷 ArrayList 是否為空
public boolean isEmpty() {
return size == 0;
}

//判斷是否存在某個元素
public boolean contains(Object o) {
return indexOf(o) >= 0;
}

//遍歷數組，找到參數 o 的下標返回，找不到返回 -1
//注意，這里使用的是 equals() 方法來比較對象的，要注意此時的 equals() 方法有沒有重寫，是比較地址還是比較內容，同時也看出 ArrayList 中可以放置 null 元素
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}

//從后面往前面找，找到對應元素返回下標，注意也是用 equals() 來比較
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}

//獲取指定索引位置的數組元素
public E get(int index) {
rangeCheck(index);//檢查索引的范圍

? ? ? ? return elementData(index);
}
//通過數組下標 index 返回 elementData 對應的元素
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}

//設置對應索引位置的元素值
public E set(int index, E element) {
rangeCheck(index);//檢查索引范圍
//取出對應索引位置的舊值
E oldValue = elementData(index);
elementData[index] = element;//將新值賦予對應索引位置的元素
return oldValue;//返回舊值
}

然后是通過索引位置刪除，索引位置后面的元素要依次往前面移動一個位置：

繼續看源碼：

//通過索引刪除
public E remove(int index) {
rangeCheck(index);//索引范圍檢查

? ? ? ? modCount++;//修改計數自增
E oldValue = elementData(index);//取出對應索引位置的舊值

? ? ? ? int numMoved = size - index - 1;//總共要移動的元素的個數
if (numMoved > 0)
//通過 System.arraycopy() 方法將 index+1 到最后的元素拷貝到 index 這個位置(注意底層還是一個一個的移動的)，總共移動了 numMoved 個元素
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//元素移動后，最后一個元素會空出，通過 --size 找到最后一個元素，將其置為 null，等待垃圾回收
elementData[--size] = null; // clear to let GC do its work

? ? ? ? return oldValue;//將舊值返回
}

從上面的源碼分析可知：ArrayList 的讀取效率比較高，因為只需要一個索引 index 就可以定位到要讀取的元素，但是刪除的效率比較低，因為后面的元素要一個一個的往前移動，所以 ArrayList 讀操作效率高，修改操作效率低。

繼續看源碼：

然后是往指定的索引位置插入元素，在插入的位置以及后面的元素要依次往后面移動一個位置：

看源碼：

2) List 接口的實現類之二：Vector

Vector源碼分析：Vector 的底層實現和 ArrayList 類似，Vector 的很多方法和 ArrayList 一樣，只是多加了一個 synchronized 鎖來保證線程安全(效率沒有 ArrayList 高)。我們這里只把 Vector 和 ArrayList 不一樣的地方提一下：

Vector 比 ArrayList 多了一個屬性：

從以上的代碼分析可知，Vector 在默認情況下會創建容量為 10 的內部對象數組，這點和 ArrayList 不一樣，ArrayList 默認情況下，內部的對象數組容量為 0，是一個空的數組，在第一次 add() 的時候才擴容為 10.

然后我們來看 Vector 的擴容方法：

總結：

1. ArrayList 默認創建的時候大小為 0，當加入第一個元素的時候，進行第一次擴容，擴充的容量為默認的 10。

2. ArrayList 每次擴容都是以當前數組大小的 1.5 倍去擴容。

3. Vector 創建時的默認容量為 10。

4. Vector 每次擴容默認是數組大小 2 倍去擴容，當指定了 capacityIncrement 之后，每次擴容僅在原來的基礎上加上 capacityIncrement 個單位空間。

5. ArrayList 是非線程安全，Vector 是線程安全。

3) List 接口的另一個實現：LinkedList

a. 對于頻繁插入或刪除的元素的操作，建議使用 LinkedList，效率會比較高，原因是 LinkedList 內部是一個雙向鏈表結構。

b. LinkedList 除了繼承了 List 接口的方法之外，還新增了如下方法：

示例1：

示例2：

package com.edu.list;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;

public class LinkedListDemo2 {

?? ?public static void main(String[] args) {
// TODO Auto-generated method stub
List list = new LinkedList();
for (int i = 1; i <= 10; i++) {
list.add(new Person("姓名" + i, 20 + i));
}
list.remove(new Person("姓名5", 25));//注意：通過對象刪除時，也是通過 equals() 來比較的
Iterator iter = list.iterator();
while(iter.hasNext()) {
Person p = (Person)iter.next();
System.out.println(p);
}
}

}
class Person {
private String name;
private int age;

public Person() {
// TODO Auto-generated constructor stub
}

?? ?public Person(String name, int age) {
super();
this.name = name;
this.age = age;
}

?? ?public String getName() {
return name;
}

?? ?public void setName(String name) {
this.name = name;
}

?? ?public int getAge() {
return age;
}

?? ?public void setAge(int age) {
this.age = age;
}

?? ?@Override
public String toString() {
return "Person [name=" + name + ", age=" + age + "]";
}

?? ?@Override
public int hashCode() {
return Objects.hash(age, name);
}

?? ?@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Person other = (Person) obj;
return age == other.age && Objects.equals(name, other.name);
}
}

c. LinkedList 源碼分析：

????LinkedList 是一個雙向鏈表：

雙向鏈表每個節點除了數據域之外，還有一個前指針(prev)和后指針(next)，分別指向前驅節點和后繼節點（如果有前驅/后繼的話），另外，雙向鏈表還有一個first指針，指向頭節點，和last指針，指向尾節點。

b) 我們先來看一下 LinkedList 中的屬性：

c) 然后就是 LinkedList 的每個節點，節點是 Node 的結構：

每個節點是一個 Node 類型的類，Node 是 LinkedList 內部的一個靜態內部類，它表示鏈表的每一個節點，包含一個數據域 item，一個前指針 prev(指向前驅節點)，一個后指針 next(指向后繼節點)：

d) 添加元素

I. 在表頭添加元素的過程：

當向表頭插入一個節點時，很顯然當前節點的前驅(prev)一定是null，后繼節點(next)是 first 指針指向的原來的這個節點，當然還要修改 first 指針指向新的頭結點，除此之外，原來的頭結點變成了第二個節點，所以還要修改原來的頭結點的前驅指針，使它指向新的頭結點。

源碼實現：

III. 在指定的節點之前插入，如圖：

當向指定節點之前插入一個節點時，當前節點（新節點）的后繼為指定節點，而前驅為指定節點的前驅節點，此外，還要修改指定節點的前驅節點的后繼為新節點，以及指定節點前驅為新節點，源碼如下：

e) 刪除元素(刪除節點)

刪除操作與添加操作大同小異，例如刪除指定節點的過程是，需要把指定節點的前驅節點的后繼修改為指定節點的后繼，以及指定節點的后繼節點前驅修改為指定節點的前驅，同時將指定節點的next，item，prev置null，等待垃圾回收器回收

I. 刪除表頭節點

II. 刪除尾節點：

III. 刪除指定節點：

f) 獲取元素

I. 獲取表頭元素

public E getFirst() {

final Node<E> f = first;//獲取頭指針，頭指針指向的就是頭元素

if (f == null)

throw new NoSuchElementException();

return f.item;//返回頭元素的數據域

}

II. 獲取尾元素

III. 獲取指定索引的元素

h) 其他常用的方法

I. 獲取鏈表大小

II. 設置指定索引位置的值

III. 在指定索引位置前面插入節點

IV. 刪除指定索引位置的節點

V. 獲取表頭節點的值，表頭為空返回 null

VI. 獲取表頭節點的值，表頭為空拋出異常

VII. 獲取表頭節點的值，并刪除表頭節點，表頭為空則返回 null

VIII. 添加元素到表頭：

VV. 彈出表頭元素，彈出=返回+刪除

從上面兩個方法可以看出，LinkedList 可以作為一個棧(后進先出)來使用，也可以當成一個隊列來使用。

總結：

1. LinkedList的底層是一個帶頭/尾指針的雙向鏈表，可以快速對頭/尾節點進行操作。

2. 相比ArrayList，LinkedList 的特點就是在指定位置插入和刪除元素的效率比較高（只需改變前驅和后繼指針的指向即可），但是查找效率就不如 ArrayList 那么高了（因為需要去遍歷鏈表才能找到對應的節點）

示例：隊列(Queue)是一個典型的先進先出(FIFO)的容器，LinkedList 實現了 Queue 接口，并提供了方法來支持隊列的行為：