下面列出了所有集合的類圖：
- 每個(gè)接口做的事情非常明確兵拢，比如 Serializable眨攘，只負(fù)責(zé)序列化，Cloneable 只負(fù)責(zé)拷貝讽营，Map 只負(fù)責(zé)定義 Map 的接口，整個(gè)圖看起來(lái)雖然接口眾多叁巨，但職責(zé)都很清晰；
- 復(fù)雜功能通過(guò)接口的繼承來(lái)實(shí)現(xiàn)呐籽，比如 ArrayList 通過(guò)實(shí)現(xiàn)了 Serializable锋勺、Cloneable、RandomAccess狡蝶、AbstractList庶橱、List 等接口，從而擁有了序列化贪惹、拷貝苏章、對(duì)數(shù)組各種操作定義等各種功能；
- 上述類圖只能看見繼承的關(guān)系奏瞬，組合的關(guān)系還看不出來(lái)枫绅，比如說(shuō) Set 組合封裝 Map 的底層能力等。
上述設(shè)計(jì)的最大好處是硼端，每個(gè)接口能力職責(zé)單一并淋，眾多的接口變成了接口能力的積累，假設(shè)我們想再實(shí)現(xiàn)一個(gè)數(shù)據(jù)結(jié)構(gòu)類珍昨，我們就可以從這些已有的能力接口中县耽，挑選出能滿足需求的能力接口，進(jìn)行一些簡(jiǎn)單的組裝镣典，從而加快開發(fā)速度兔毙。
這種思想在平時(shí)的工作中也經(jīng)常被使用，我們會(huì)把一些通用的代碼塊抽象出來(lái)兄春，沉淀成代碼塊池澎剥，碰到不同的場(chǎng)景的時(shí)候，我們就從代碼塊池中赶舆，把我們需要的代碼塊提取出來(lái)肴裙，進(jìn)行簡(jiǎn)單的編排和組裝，從而實(shí)現(xiàn)我們需要的場(chǎng)景功能涌乳。
1.集合迭代
在講具體迭代方式之前蜻懦，先來(lái)看一下迭代的頂層接口：Iterable。在看具體源碼前先明白兩個(gè)問題：
- Iterable有什么用呢夕晓？實(shí)現(xiàn)了Itrable接口就能進(jìn)行迭代（遍歷）操作宛乃。
- 為什么我在ArrayList中沒有看見它實(shí)現(xiàn)Iterable呢？從上面的類圖中可以看到，集合的頂級(jí)接口Collection實(shí)現(xiàn)了Iterable征炼，但這里注意一點(diǎn)析既，Map并沒有實(shí)現(xiàn)Iterable（map的迭代第二部分再講解）。
public interface Iterable<T> {
Iterator<T> iterator()
default void forEach(Consumer<? super T> action) {
Objects.requireNonNull(action);
for (T t : this) {
action.accept(t);
}
}
default Spliterator<T> spliterator() {
return Spliterators.spliteratorUnknownSize(iterator(), 0);
}
}
從接口中我們看到遍歷的手段有兩種：
- 迭代器Iterator谆奥，可以實(shí)現(xiàn)多個(gè)Iterator進(jìn)行多種方法的迭代（前序眼坏，后序...)
- forEach方法，一般由具體子類重寫該方法
這里注意一點(diǎn)酸些，Iterator 和 forEach 都需要要進(jìn)行迭代的類自行實(shí)現(xiàn)宰译。
1.1 方式一：迭代器Iterator
常由內(nèi)部類實(shí)現(xiàn)，iterator方法返回魄懂，一般用于要對(duì)集合進(jìn)行刪除的情景
- 迭代器是一種設(shè)計(jì)模式沿侈，封裝了對(duì)集合的遍歷，使得不用了解集合的內(nèi)部細(xì)節(jié)市栗，就可以用同樣的方式遍歷不同的集合
- 迭代器不允許使用集合方法進(jìn)行集合增刪缀拭，但是可以對(duì)集合的元素操作（如set()），還可以使用迭代器的remove()
- 不能使用集合的 put 和 remove 方法
- 可用于集合元素屬性的修改：set方法
- remove操作：是Iterator的remove方法
這里特別注意一點(diǎn)填帽，一定要在next()后使用蛛淋，比如刪除第一個(gè)元素，要先next然后才能remove
public interface Iterator<E> {
// 每次next之前篡腌，先調(diào)用此方法探測(cè)是否迭代到終點(diǎn)
boolean hasNext();
// 返回當(dāng)前迭代元素 铣鹏，同時(shí)，迭代游標(biāo)后移
E next();
/*刪除最近一次已近迭代出出去的那個(gè)元素哀蘑。
只有當(dāng)next執(zhí)行完后诚卸，才能調(diào)用remove函數(shù)。
比如你要?jiǎng)h除第一個(gè)元素绘迁，不能直接調(diào)用 remove() 而要先next一下( );
在沒有先調(diào)用next 就調(diào)用remove方法是會(huì)拋出異常的合溺。
這個(gè)和MySQL中的ResultSet很類似
*/
void remove()
{
throw new UnsupportedOperationException("remove");
}
}
- 迭代器使用示例：
// iterator是集合的自己Iterator構(gòu)造方法
Iterator it = list.iterator();
while(it.hasNext) {
it.next();
}
1.2 方式二：forEach方法
本質(zhì)是對(duì)for循環(huán)的封裝，配合lamada使用缀台，一般用于修改集合對(duì)象屬性的情景
// ArrayList.forEach()
@Override
public void forEach(Consumer<? super E> action) {
// 判斷非空
Objects.requireNonNull(action);
// modCount的原始值被拷貝
final int expectedModCount = modCount;
final E[] elementData = (E[]) this.elementData;
final int size = this.size;
// 每次循環(huán)都會(huì)判斷數(shù)組有沒有被修改棠赛，一旦被修改，停止循環(huán)
for (int i=0; modCount == expectedModCount && i < size; i++) {
// 執(zhí)行循環(huán)內(nèi)容膛腐，action 代表我們要干的事情
action.accept(elementData[i]);
}
// 數(shù)組如果被修改了睛约，拋異常
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
- 因?yàn)樵贗terable接口中default修飾，所以必須自身實(shí)現(xiàn)而子類不一定要重寫哲身，在jdk8時(shí)所有集合都實(shí)現(xiàn)了forEach方法
- forEach：
- 修改對(duì)象屬性：通過(guò)set方法
- 不能進(jìn)行增刪操作：modCount
- 使用示例：
list.forEach(l -> {
l.setName("zs");
l.setAge(18);
})
1.3 方式三：增強(qiáng)for循環(huán)
本質(zhì)是對(duì)Iterator的簡(jiǎn)化與封裝辩涝，一般用于只遍歷集合的情況
- 增強(qiáng)for循環(huán)：
- 可以用于集合中元素屬性值的修改：set方法
- 但不能對(duì)集合新增或者刪除：modCount控制
- 使用示例：
public static void main(String[] args) {
ArrayList<Person> people = new ArrayList<>();
people.add(new Person("zs"));
people.add(new Person("lisi"));
// 調(diào)用增強(qiáng)for循環(huán)
for(Person p: people) {
// 通過(guò)set修改對(duì)象屬性值，成功
p.setName("abc");
}
System.out.println(people); // abc,abc
}
2.Map迭代
從文章首部的類圖中可以看到勘天，map并未實(shí)現(xiàn)Itrable接口怔揩，那map該如何進(jìn)行迭代呢捉邢？
通過(guò)set的Iterator進(jìn)行迭代
最高層Map接口定義了forEach方法
2.1 方式一：Set.iterator
Map 對(duì) key、value 和 entity（節(jié)點(diǎn)） 都提供了以 Set 為基礎(chǔ)的迭代器商膊。這些迭代器可以通過(guò)map.~Set().iterator()進(jìn)行獲取
- 迭代key：HashMap --keySet()--> KeySet --iterator()--> KeyIterator
- 迭代value：HashMap --values()--> Values--iterator()--> ValueIterator
- 迭代key：HashMap --entrySet()--> EntrySet--iterator()--> EntryIterator
雖然是不同的迭代器伏伐，但是它們本質(zhì)上卻沒有區(qū)別，主要體現(xiàn)在以下兩點(diǎn)：
- 都繼承了HashIterator晕拆，即擁有HashIterator的所有方法
abstract class HashIterator {
Node<K,V> next; // next entry to return
Node<K,V> current; // current entry
int expectedModCount; // for fast-fail
int index; // current slot
HashIterator() {
expectedModCount = modCount;
Node<K,V>[] t = table;
current = next = null;
index = 0;
if (t != null && size > 0) { // advance to first entry
do {} while (index < t.length && (next = t[index++]) == null);
}
}
......
}
- 都只有一個(gè)方法：next()藐翎，而且里面調(diào)用的都是 HashIterator.nextNode()，只不過(guò)最后在node中取值不同
final class KeyIterator extends HashIterator
implements Iterator<K> {
public final K next() { return nextNode().key; } // 調(diào)用父類的nextNode方法实幕，返回node的key
}
final class ValueIterator extends HashIterator
implements Iterator<V> {
public final V next() { return nextNode().value; } // 調(diào)用父類的nextNode方法吝镣，返回node的value
}
final class EntryIterator extends HashIterator
implements Iterator<Map.Entry<K,V>> {
public final Map.Entry<K,V> next() { return nextNode(); } // 調(diào)用父類的nextNode方法，返回node
}
使用示例：
Iterator<Map.Entry<String,String>> it = map.entrySet().iterator
while (it.hasNext()) {
Map.Entry<String,String> me = it.next();
// 獲取key
me.getkey();
// 獲取value
me.getValue();
}
2.2 方式二：Map.forEach
Map中定義的forEach茬缩，default修飾赤惊，實(shí)際上也是調(diào)用entrySet
default void forEach(BiConsumer<? super K, ? super V> action) {
Objects.requireNonNull(action);
for (Map.Entry<K, V> entry : entrySet()) {
K k;
V v;
try {
k = entry.getKey();
v = entry.getValue();
} catch(IllegalStateException ise) {
// this usually means the entry is no longer in the map.
throw new ConcurrentModificationException(ise);
}
action.accept(k, v);
}
}
HashMap的forEach方法源碼：
@Override
public void forEach(BiConsumer<? super K, ? super V> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e.key, e.value);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
3.批量操作
3.1 批量新增
下面列出 ArrayList.addAll 方法的源碼：
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
// 確保容量充足吼旧，整個(gè)過(guò)程只會(huì)擴(kuò)容一次
ensureCapacityInternal(size + numNew);
// 進(jìn)行數(shù)組的拷貝
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
我們可以看到凰锡，整個(gè)批量新增的過(guò)程中，只擴(kuò)容了一次圈暗，HashMap 的 putAll 方法也是如此掂为，整個(gè)新增過(guò)程只會(huì)擴(kuò)容一次，大大縮短了批量新增的時(shí)間员串，提高了性能勇哗。
所以當(dāng)碰到集合批量拷貝，批量新增場(chǎng)景寸齐，要提高新增性能的時(shí)候 欲诺，就可以從目標(biāo)集合初始化方面入手。
這里也提醒了我們渺鹦，在容器初始化的時(shí)候扰法，最好能給容器賦上初始值，這樣可以防止在 put 的過(guò)程中不斷的擴(kuò)容毅厚，從而縮短時(shí)間塞颁，上章 HashSet 的源碼演示了給 HashMap 賦初始值的公式為：取括號(hào)內(nèi)兩者的最大值（期望的值/0.75+1，默認(rèn)值 16）吸耿。
使用示例：
在 List 和 Map 大量數(shù)據(jù)新增的時(shí)候祠锣，我們不要使用 for 循環(huán) + add/put 方法新增，這樣子會(huì)有很大的擴(kuò)容成本咽安，我們應(yīng)該盡量使用 addAll 和 putAll 方法進(jìn)行新增伴网，下面以 ArrayList 為例寫了一個(gè) demo 如下，演示了兩種方案的性能對(duì)比：
@Test
public void testBatchInsert(){
// 準(zhǔn)備拷貝數(shù)據(jù)
ArrayList<Integer> list = new ArrayList<>();
for(int i=0;i<3000000;i++){
list.add(i);
}
// for 循環(huán) + add
ArrayList<Integer> list2 = new ArrayList<>();
long start1 = System.currentTimeMillis();
for(int i=0;i<list.size();i++){
list2.add(list.get(i));
}
log.info("單個(gè) for 循環(huán)新增 300 w 個(gè)妆棒，耗時(shí){}",System.currentTimeMillis()-start1);
// 批量新增
ArrayList<Integer> list3 = new ArrayList<>();
long start2 = System.currentTimeMillis();
list3.addAll(list);
log.info("批量新增 300 w 個(gè)是偷，耗時(shí){}",System.currentTimeMillis()-start2);
}
最后打印出來(lái)的日志為：
16:52:59.865 [main] INFO demo.one.ArrayListDemo - 單個(gè) for 循環(huán)新增 300 w 個(gè)拳氢，耗時(shí)1518
16:52:59.880 [main] INFO demo.one.ArrayListDemo - 批量新增 300 w 個(gè)，耗時(shí)8
可以看到蛋铆，批量新增方法性能是單個(gè)新增方法性能的 189 倍馋评，主要原因在于批量新增，只會(huì)擴(kuò)容一次刺啦，大大縮短了運(yùn)行時(shí)間留特，而單個(gè)新增，每次到達(dá)擴(kuò)容閥值時(shí)玛瘸，都會(huì)進(jìn)行擴(kuò)容蜕青，在整個(gè)過(guò)程中就會(huì)不斷的擴(kuò)容，浪費(fèi)了很多時(shí)間
3.2 批量刪除
批量刪除 ArrayList 提供了 removeAll 的方法糊渊，HashMap 沒有提供批量刪除的方法右核，我們一起來(lái)看下 removeAll 的源碼實(shí)現(xiàn)，是如何提高性能的：
// 批量刪除渺绒，removeAll 方法底層調(diào)用的是 batchRemove 方法
// complement 參數(shù)默認(rèn)是 false,false 的意思是數(shù)組中不包含 c 中數(shù)據(jù)的節(jié)點(diǎn)往頭移動(dòng)
// true 意思是數(shù)組中包含 c 中數(shù)據(jù)的節(jié)點(diǎn)往頭移動(dòng)贺喝，這個(gè)是根據(jù)你要?jiǎng)h除數(shù)據(jù)和原數(shù)組大小的比例來(lái)決定的
// 如果你要?jiǎng)h除的數(shù)據(jù)很多，選擇 false 性能更好宗兼，當(dāng)然 removeAll 方法默認(rèn)就是 false躏鱼。
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
// r 表示當(dāng)前循環(huán)的位置、w 位置之前都是不需要被刪除的數(shù)據(jù)殷绍，w 位置之后都是需要被刪除的數(shù)據(jù)
int r = 0, w = 0;
boolean modified = false;
try {
// 從 0 位置開始判斷染苛，當(dāng)前數(shù)組中元素是不是要被刪除的元素，不是的話移到數(shù)組頭
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// r 和 size 不等主到，說(shuō)明在 try 過(guò)程中發(fā)生了異常茶行，在 r 處斷開
// 把 r 位置之后的數(shù)組移動(dòng)到 w 位置之后(r 位置之后的數(shù)組數(shù)據(jù)都是沒有判斷過(guò)的數(shù)據(jù)，這樣不會(huì)影響沒有判斷
// 的數(shù)據(jù)登钥，判斷過(guò)的數(shù)據(jù)可以被刪除)
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
// w != size 說(shuō)明數(shù)組中是有數(shù)據(jù)需要被刪除的
// 如果 w畔师、size 相等，說(shuō)明沒有數(shù)據(jù)需要被刪除
if (w != size) {
// w 之后都是需要?jiǎng)h除的數(shù)據(jù)怔鳖，賦值為空茉唉，幫助 gc。
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
我們看到 ArrayList 在批量刪除時(shí)结执，如果程序執(zhí)行正常度陆，只有一次 for 循環(huán)，如果程序執(zhí)行異常献幔，才會(huì)加一次拷貝懂傀，而單個(gè) remove 方法，每次執(zhí)行的時(shí)候都會(huì)進(jìn)行數(shù)組的拷貝（當(dāng)刪除的元素正好是數(shù)組最后一個(gè)元素時(shí)除外）蜡感，當(dāng)數(shù)組越大蹬蚁，需要?jiǎng)h除的數(shù)據(jù)越多時(shí)恃泪，批量刪除的性能會(huì)越差，所以在 ArrayList 批量刪除時(shí)犀斋，強(qiáng)烈建議使用 removeAll 方法進(jìn)行刪除贝乎。
4.線程安全問題
我們說(shuō)集合都是非線程安全的，這里說(shuō)的非線程安全指的是集合類作為共享變量叽粹，被多線程讀寫的時(shí)候览效，才是不安全的，如果要實(shí)現(xiàn)線程安全的集合虫几，在類注釋中锤灿，JDK 統(tǒng)一推薦我們使用 Collections.synchronized* 類， Collections 幫我們實(shí)現(xiàn)了 List辆脸、Set但校、Map 對(duì)應(yīng)的線程安全的方法， 如下圖：
圖中實(shí)現(xiàn)了各種集合類型的線程安全的方法啡氢，我們以 synchronizedList 為例状囱，從源碼上來(lái)看下，Collections 是如何實(shí)現(xiàn)線程安全的：
// mutex 就是我們需要鎖住的對(duì)象
final Object mutex;
// 這些synchronized~~都是Collections的靜態(tài)內(nèi)部類
static class SynchronizedList<E> extends SynchronizedCollection<E> implements List<E> {
private static final long serialVersionUID = -7754090372962971524L;
// 通過(guò)組合的方式空执，傳入需要保證線程安全的類（List）
// Collection.synchronizedList（list）
final List<E> list;
SynchronizedList(List<E> list, Object mutex) {
super(list, mutex);
this.list = list;
}
// 我們可以看到浪箭，List 的所有操作都使用了 synchronized 關(guān)鍵字穗椅，來(lái)進(jìn)行加鎖
// synchronized 是一種悲觀鎖辨绊，能夠保證同一時(shí)刻，只能有一個(gè)線程能夠獲得鎖
public E get(int index) {
synchronized (mutex) {return list.get(index);}
}
public E set(int index, E element) {
synchronized (mutex) {return list.set(index, element);}
}
public void add(int index, E element) {
synchronized (mutex) {list.add(index, element);}
}
…………
}
從源碼中我們可以看到 Collections 是通過(guò) synchronized 關(guān)鍵字給 List 操作數(shù)組的方法加上鎖匹表，來(lái)實(shí)現(xiàn)線程安全的门坷。
5.兩點(diǎn)注意
在文章的最后，再提出使用集合時(shí)的兩點(diǎn)注意：
重寫equals & hashcode
當(dāng)集合的元素是自定義類時(shí)袍镀，自定義類強(qiáng)制實(shí)現(xiàn) equals 和 hashCode 方法默蚌，并且兩個(gè)都要實(shí)現(xiàn)。因?yàn)樵诩现形郏?TreeMap 和 TreeSet 是通過(guò)比較器比較元素大小外绸吸，其余的集合類在判斷索引位置和相等時(shí)，都會(huì)使用到 equals 和 hashCode 方法设江，這個(gè)在之前的源碼解析中锦茁，我們有說(shuō)到，所以當(dāng)集合的元素是自定義類時(shí)叉存，我們強(qiáng)烈建議覆寫 equals 和 hashCode 方法码俩，我們可以直接使用 IDEA 工具覆寫這兩個(gè)方法，非常方便迭代刪除
所有集合類歼捏，在 for 循環(huán)進(jìn)行刪除時(shí)稿存，如果直接使用集合類的 remove 方法進(jìn)行刪除笨篷，都會(huì)快速失敗，報(bào) ConcurrentModificationException 的錯(cuò)誤瓣履，所以在任意循環(huán)刪除的場(chǎng)景下率翅，都建議使用迭代器進(jìn)行刪除；
