1. 前言
集合是用來存儲多個資料的，除了基本類型之外，集合應該是java中最最常用的類型了。java中的集合類型一般都集中在java.util包和java.util.concurrent包中。
其中util包中的集合類是基礎的集合類，而concurrent包中的集合類是為并發特别準備的集合類。
集合類的父類有兩個，一個是java.util.Collection, 一個是java.util.Map。
先看下Collection的定義：
public interface Collection<E> extends Iterable<E> {
} Collection繼承自Iterable接口，表示所有的Collection都是可周遊的。并且Collection中可以儲存一種資料類型。
再看下Map的定義：
public interface Map<K, V> {
} 可以看到Map是一個頂級的接口，裡面可以保持兩種資料類型，分别是key和value。
其中Collection是List,Set和Queue的父類，這樣就組成了集合的四大類型：List，Queue，Set和Map，接下來我們将會一一的進行講解。
2. List
先看下List的定義：
public interface List<E> extends Collection<E> {
} List是一個接口，繼承自Collection，表示的是一個有序的連結清單，常用的list有ArrayList,LinkedList等等。
2.1 fail-safe fail-fast知多少
我們在使用集合類的時候，通常會需要去周遊集合中的元素，并在周遊中對其中的元素進行處理。這時候我們就要用到Iterator,經常寫程式的朋友應該都知道，在Iterator周遊的過程中，是不能夠修改集合資料的，否則就會抛出ConcurrentModificationException。
因為ConcurrentModificationException的存在，就把Iterator分成了兩類，Fail-fast和Fail-safe。
2.1.1 Fail-fast Iterator
Fail-fast看名字就知道它的意思是失敗的非常快。就是說如果在周遊的過程中修改了集合的結構，則就會立刻報錯。
Fail-fast通常在下面兩種情況下抛出ConcurrentModificationException：
- 單線程的環境中
如果在單線程的環境中，iterator建立之後，如果不是通過iterator自身的remove方法，而是通過調用其他的方法修改了集合的結構，則會報錯。
- 多線程的環境中
如果一個線程中建立了iterator,而在另外一個線程中修改了集合的結構，則會報錯。
我們先看一個Fail-fast的例子：
Map<Integer,String> users = new HashMap<>();
users.put(1, "jack");
users.put(2, "alice");
users.put(3, "jone");
Iterator iterator1 = users.keySet().iterator();
//not modify key, so no exception
while (iterator1.hasNext())
{
log.info("{}",users.get(iterator1.next()));
users.put(2, "mark");
} 上面的例子中，我們建構了一個Map，然後周遊該map的key，在周遊過程中，我們修改了map的value。
運作發現，程式完美執行，并沒有報任何異常。
這是因為我們周遊的是map的key，隻要map的key沒有被手動修改，就沒有問題。
再看一個例子：
Map<Integer,String> users = new HashMap<>();
users.put(1, "jack");
users.put(2, "alice");
users.put(3, "jone");
Iterator iterator1 = users.keySet().iterator();
Iterator iterator2 = users.keySet().iterator();
//modify key,get exception
while (iterator2.hasNext())
{
log.info("{}",users.get(iterator2.next()));
users.put(4, "mark");
} 上面的例子中，我們在周遊map的key的同時，對key進行了修改。這種情況下就會報錯。
2.1.2 Fail-fast 的原理
為什麼修改了集合的結構就會報異常呢？
我們以ArrayList為例，來講解下Fail-fast 的原理。
在AbstractList中，定義了一個modCount變量：
protected transient int modCount = 0; 在周遊的過程中都會去調用checkForComodification()方法來對modCount進行檢測：
public E next() {
checkForComodification();
try {
int i = cursor;
E next = get(i);
lastRet = i;
cursor = i + 1;
return next;
} catch (IndexOutOfBoundsException e) {
checkForComodification();
throw new NoSuchElementException();
}
} 如果檢測的結果不是所預期的，就會報錯：
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
} 在建立Iterator的時候會複制目前的modCount進行比較，而這個modCount在每次集合修改的時候都會進行變動，最終導緻Iterator中的modCount和現有的modCount是不一緻的。
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
AbstractList.this.set(lastRet, e);
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
} 注意，Fail-fast并不保證所有的修改都會報錯，我們不能夠依賴ConcurrentModificationException來判斷周遊中集合是否被修改。
2.1.3 Fail-safe Iterator
我們再來講一下Fail-safe，Fail-safe的意思是在周遊的過程中，如果對集合進行修改是不會報錯的。
Concurrent包下面的類型都是Fail-safe的。看一個ConcurrentHashMap的例子：
Map<Integer,String> users = new ConcurrentHashMap<>();
users.put(1, "jack");
users.put(2, "alice");
users.put(3, "jone");
Iterator iterator1 = users.keySet().iterator();
//not modify key, so no exception
while (iterator1.hasNext())
{
log.info("{}",users.get(iterator1.next()));
users.put(2, "mark");
}
Iterator iterator2 = users.keySet().iterator();
//modify key,get exception
while (iterator2.hasNext())
{
log.info("{}",users.get(iterator2.next()));
users.put(4, "mark");
} 上面的例子完美執行，不會報錯。
2.2 Iterator to list的三種方法
集合的變量少不了使用Iterator，從集合Iterator非常簡單，直接調用Iterator方法就可以了。
那麼如何從Iterator反過來生成List呢？今天教大家三個方法。
2.2.1 使用while
最簡單最基本的邏輯就是使用while來周遊這個Iterator，在周遊的過程中将Iterator中的元素添加到建立的List中去。
如下面的代碼所示：
@Test
public void useWhile(){
List<String> stringList= new ArrayList<>();
Iterator<String> stringIterator= Arrays.asList("a","b","c").iterator();
while(stringIterator.hasNext()){
stringList.add(stringIterator.next());
}
log.info("{}",stringList);
} 2.2.2 使用ForEachRemaining
Iterator接口有個default方法：
default void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (hasNext())
action.accept(next());
} 實際上這方法的底層就是封裝了while循環，那麼我們可以直接使用這個ForEachRemaining的方法：
@Test
public void useForEachRemaining(){
List<String> stringList= new ArrayList<>();
Iterator<String> stringIterator= Arrays.asList("a","b","c").iterator();
stringIterator.forEachRemaining(stringList::add);
log.info("{}",stringList);
} 2.2.3 使用stream
我們知道建構Stream的時候，可以調用StreamSupport的stream方法：
public static <T> Stream<T> stream(Spliterator<T> spliterator, boolean parallel) 該方法傳入一個spliterator參數。而Iterable接口正好有一個spliterator()的方法：
default Spliterator<T> spliterator() {
return Spliterators.spliteratorUnknownSize(iterator(), 0);
} 那麼我們可以将Iterator轉換為Iterable，然後傳入stream。
仔細研究Iterable接口可以發現，Iterable是一個FunctionalInterface，隻需要實作下面的接口就行了：
Iterator<T> iterator(); 利用lambda表達式，我們可以友善的将Iterator轉換為Iterable：
Iterator<String> stringIterator= Arrays.asList("a","b","c").iterator();
Iterable<String> stringIterable = () -> stringIterator; 最後将其換行成為List：
List<String> stringList= StreamSupport.stream(stringIterable.spliterator(),false).collect(Collectors.toList());
log.info("{}",stringList); 2.3 asList和ArrayList不得不說的故事
提到集合類，ArrayList應該是用到的非常多的類了。這裡的ArrayList是java.util.ArrayList，通常我們怎麼建立ArrayList呢？
2.3.1 建立ArrayList
看下下面的例子：
List<String> names = new ArrayList<>(); 上面的方法建立了一個ArrayList，如果我們需要向其中添加元素的話，需要再調用add方法。
通常我們會使用一種更加簡潔的辦法來建立List：
@Test
public void testAsList(){
List<String> names = Arrays.asList("alice", "bob", "jack");
names.add("mark");
} 看下asList方法的定義：
public static <T> List<T> asList(T... a) {
return new ArrayList<>(a);
} 很好，使用Arrays.asList，我們可以友善的建立ArrayList。
運作下上面的例子，奇怪的事情發生了，上面的例子居然抛出了UnsupportedOperationException異常。
java.lang.UnsupportedOperationException
at java.util.AbstractList.add(AbstractList.java:148)
at java.util.AbstractList.add(AbstractList.java:108)
at com.flydean.AsListUsage.testAsList(AsListUsage.java:18) 2.3.2 UnsupportedOperationException
先講一下這個異常，UnsupportedOperationException是一個運作時異常，通常用在某些類中并沒有實作接口的某些方法。
為什麼上面的ArrayList調用add方法會抛異常呢？
2.3.3 asList
我們再來詳細的看一下Arrays.asList方法中傳回的ArrayList：
private static class ArrayList<E> extends AbstractList<E>
implements RandomAccess, java.io.Serializable 可以看到，Arrays.asList傳回的ArrayList是Arrays類中的一個内部類，并不是java.util.ArrayList。
這個類繼承自AbstractList，在AbstractList中add方法是這樣定義的：
public void add(int index, E element) {
throw new UnsupportedOperationException();
} 好了，我們的問題得到了解決。
2.3.4 轉換
我們使用Arrays.asList得到ArrayList之後，能不能将其轉換成為java.util.ArrayList呢？答案是肯定的。
我們看下下面的例子：
@Test
public void testList(){
List<String> names = new ArrayList<>(Arrays.asList("alice", "bob", "jack"));
names.add("mark");
} 上面的例子可以正常執行。
在java中有很多同樣名字的類，我們需要弄清楚他們到底是什麼，不要混淆了。
2.4 Copy ArrayList的四種方式
ArrayList是我們經常會用到的集合類，有時候我們需要拷貝一個ArrayList，今天向大家介紹拷貝ArrayList常用的四種方式。
2.4.1 使用構造函數
ArrayList有個構造函數，可以傳入一個集合：
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)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
} 上面的代碼我們可以看出，底層實際上調用了Arrays.copyOf方法來對數組進行拷貝。這個拷貝調用了系統的native arraycopy方法，注意這裡的拷貝是引用拷貝，而不是值的拷貝。這就意味着這如果拷貝之後對象的值發送了變化，源對象也會發生改變。
舉個例子：
@Test
public void withConstructor(){
List<String> stringList=new ArrayList<>(Arrays.asList("a","b","c"));
List<String> copyList = new ArrayList<>(stringList);
copyList.set(0,"e");
log.info("{}",stringList);
log.info("{}",copyList);
List<CustBook> objectList=new ArrayList<>(Arrays.asList(new CustBook("a"),new CustBook("b"),new CustBook("c")));
List<CustBook> copyobjectList = new ArrayList<>(objectList);
copyobjectList.get(0).setName("e");
log.info("{}",objectList);
log.info("{}",copyobjectList);
} 運作結果：
22:58:39.001 [main] INFO com.flydean.CopyList - [a, b, c]
22:58:39.008 [main] INFO com.flydean.CopyList - [e, b, c]
22:58:39.009 [main] INFO com.flydean.CopyList - [CustBook(name=e), CustBook(name=b), CustBook(name=c)]
22:58:39.009 [main] INFO com.flydean.CopyList - [CustBook(name=e), CustBook(name=b), CustBook(name=c)] 我們看到對象的改變實際上改變了拷貝的源。而copyList.set(0,"e")實際上建立了一個新的String對象，并把它指派到copyList的0位置。
2.4.2 使用addAll方法
List有一個addAll方法，我們可以使用這個方法來進行拷貝：
@Test
public void withAddAll(){
List<CustBook> objectList=new ArrayList<>(Arrays.asList(new CustBook("a"),new CustBook("b"),new CustBook("c")));
List<CustBook> copyobjectList = new ArrayList<>();
copyobjectList.addAll(objectList);
copyobjectList.get(0).setName("e");
log.info("{}",objectList);
log.info("{}",copyobjectList);
} 同樣的拷貝的是對象的引用。
2.4.3 使用Collections.copy
同樣的，使用Collections.copy也可以得到相同的效果，看下代碼：
@Test
public void withCopy(){
List<CustBook> objectList=new ArrayList<>(Arrays.asList(new CustBook("a"),new CustBook("b"),new CustBook("c")));
List<CustBook> copyobjectList = new ArrayList<>(Arrays.asList(new CustBook("d"),new CustBook("e"),new CustBook("f")));
Collections.copy(copyobjectList, objectList);
copyobjectList.get(0).setName("e");
log.info("{}",objectList);
log.info("{}",copyobjectList);
} 2.4.4 使用stream
我們也可以使用java 8引入的stream來實作：
@Test
public void withStream(){
List<CustBook> objectList=new ArrayList<>(Arrays.asList(new CustBook("a"),new CustBook("b"),new CustBook("c")));
List<CustBook> copyobjectList=objectList.stream().collect(Collectors.toList());
copyobjectList.get(0).setName("e");
log.info("{}",objectList);
log.info("{}",copyobjectList);
} 好了，四種方法講完了，大家要注意四種方法都是引用拷貝，在使用的時候要小心。
3. Map
先看下Map的定義：
public interface Map<K, V> {
} Map是一個key-value對的集合，其中key不能夠重複，但是value可以重複。常用的Map有TreeMap和hashMap。
3.1 深入了解HashMap和TreeMap的差別
HashMap和TreeMap是Map家族中非常常用的兩個類，兩個類在使用上和本質上有什麼差別呢？本文将從這兩個方面進行深入的探讨，希望能揭露其本質。
3.1.1 HashMap和TreeMap本質差別
先看HashMap的定義：
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable 再看TreeMap的定義：
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable 從類的定義來看，HashMap和TreeMap都繼承自AbstractMap，不同的是HashMap實作的是Map接口，而TreeMap實作的是NavigableMap接口。NavigableMap是SortedMap的一種，實作了對Map中key的排序。
這樣兩者的第一個差別就出來了，TreeMap是排序的而HashMap不是。
再看看HashMap和TreeMap的構造函數的差別。
public HashMap(int initialCapacity, float loadFactor) HashMap除了預設的無參構造函數之外，還可以接受兩個參數initialCapacity和loadFactor。
HashMap的底層結構是Node的數組：
transient Node<K,V>[] table initialCapacity就是這個table的初始容量。如果大家不傳initialCapacity，HashMap提供了一個預設的值：
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 當HashMap中存儲的資料過多的時候，table數組就會被裝滿，這時候就需要擴容，HashMap的擴容是以2的倍數來進行的。而loadFactor就指定了什麼時候需要進行擴容操作。預設的loadFactor是0.75。
static final float DEFAULT_LOAD_FACTOR = 0.75f; 再來看幾個非常有趣的變量：
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64; 上面的三個變量有什麼用呢？在java 8之前，HashMap解決hashcode沖突的方法是采用連結清單的形式，為了提升效率，java 8将其轉成了TreeNode。什麼時候會發送這個轉換呢？
這時候就要看這兩個變量TREEIFY_THRESHOLD和UNTREEIFY_THRESHOLD。
有的同學可能發現了，TREEIFY_THRESHOLD為什麼比UNTREEIFY_THRESHOLD大2呢？其實這個問題我也不知道，但是你看源代碼的話，用到UNTREEIFY_THRESHOLD時候，都用的是<=,而用到TREEIFY_THRESHOLD的時候，都用的是>= TREEIFY_THRESHOLD - 1，是以這兩個變量在本質上是一樣的。
MIN_TREEIFY_CAPACITY表示的是如果table轉換TreeNode的最小容量，隻有capacity >= MIN_TREEIFY_CAPACITY的時候才允許TreeNode的轉換。
TreeMap和HashMap不同的是，TreeMap的底層是一個Entry：
private transient Entry<K,V> root 他的實作是一個紅黑樹，友善用來周遊和搜尋。
TreeMap的構造函數可以傳入一個Comparator，實作自定義的比較方法。
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
} 如果不提供自定義的比較方法，則使用的是key的natural order。
3.1.2 排序差別
我們講完兩者的本質之後，現在舉例說明，先看下兩者對排序的差別：
@Test
public void withOrder(){
Map<String, String> books = new HashMap<>();
books.put("bob", "books");
books.put("c", "concurrent");
books.put("a", "a lock");
log.info("{}",books);
} @Test
public void withOrder(){
Map<String, String> books = new TreeMap<>();
books.put("bob", "books");
books.put("c", "concurrent");
books.put("a", "a lock");
log.info("{}",books);
} 同樣的代碼，一個使用了HashMap，一個使用了TreeMap，我們會發現TreeMap輸出的結果是排好序的，而HashMap的輸出結果是不定的。
3.1.3 Null值的差別
HashMap可以允許一個null key和多個null value。而TreeMap不允許null key，但是可以允許多個null value。
@Test
public void withNull() {
Map<String, String> hashmap = new HashMap<>();
hashmap.put(null, null);
log.info("{}",hashmap);
} @Test
public void withNull() {
Map<String, String> hashmap = new TreeMap<>();
hashmap.put(null, null);
log.info("{}",hashmap);
} HashMap會報出： NullPointerException。
3.1.4 性能差別
HashMap的底層是Array，是以HashMap在添加，查找，删除等方法上面速度會非常快。而TreeMap的底層是一個Tree結構，是以速度會比較慢。
另外HashMap因為要儲存一個Array，是以會造成空間的浪費，而TreeMap隻儲存要保持的節點，是以占用的空間比較小。
HashMap如果出現hash沖突的話，效率會變差，不過在java 8進行TreeNode轉換之後，效率有很大的提升。
TreeMap在添加和删除節點的時候會進行重排序，會對性能有所影響。
3.1.5 共同點
兩者都不允許duplicate key,兩者都不是線程安全的。
3.2 深入了解HashMap和LinkedHashMap的差別
我們知道HashMap的變量順序是不可預測的，這意味着便利的輸出順序并不一定和HashMap的插入順序是一緻的。這個特性通常會對我們的工作造成一定的困擾。為了實作這個功能，我們可以使用LinkedHashMap。
3.2.1 LinkedHashMap詳解
先看下LinkedHashMap的定義：
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V> LinkedHashMap繼承自HashMap，是以HashMap的所有功能在LinkedHashMap都可以用。
LinkedHashMap和HashMap的差別就是新建立了一個Entry:
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
} 這個Entry繼承自HashMap.Node，多了一個before，after來實作Node之間的連接配接。
通過這個新建立的Entry，就可以保證周遊的順序和插入的順序一緻。
3.2.2 插入
下面看一個LinkedHashMap插入的例子：
@Test
public void insertOrder(){
LinkedHashMap<String, String> map = new LinkedHashMap<>();
map.put("ddd","desk");
map.put("aaa","ask");
map.put("ccc","check");
map.keySet().forEach(System.out::println);
} 輸出結果：
ddd
aaa
ccc 可以看到輸出結果和插入結果是一緻的。
3.2.3 通路
除了周遊的順序，LinkedHashMap還有一個非常有特色的通路順序。
我們再看一個LinkedHashMap的構造函數：
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
} 前面的兩個參數initialCapacity，loadFactor我們之前已經講過了，現在看最後一個參數accessOrder。
當accessOrder設定成為true的時候，就開啟了 access-order。
access order的意思是，将對象安裝最老通路到最新通路的順序排序。我們看個例子：
@Test
public void accessOrder(){
LinkedHashMap<String, String> map = new LinkedHashMap<>(16, .75f, true);
map.put("ddd","desk");
map.put("aaa","ask");
map.put("ccc","check");
map.keySet().forEach(System.out::println);
map.get("aaa");
map.keySet().forEach(System.out::println);
} ddd
aaa
ccc
ddd
ccc
aaa 我們看到，因為通路了一次“aaa“，進而導緻周遊的時候排到了最後。
3.2.4 removeEldestEntry
最後我們看一下LinkedHashMap的一個特别的功能removeEldestEntry。這個方法是幹什麼的呢？
通過重新removeEldestEntry方法，可以讓LinkedHashMap儲存特定數目的Entry,通常用在LinkedHashMap用作緩存的情況。
removeEldestEntry将會删除最老的Entry，保留最新的。
ublic class CustLinkedHashMap<K, V> extends LinkedHashMap<K, V> {
private static final int MAX_ENTRIES = 10;
public CustLinkedHashMap(
int initialCapacity, float loadFactor, boolean accessOrder) {
super(initialCapacity, loadFactor, accessOrder);
}
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > MAX_ENTRIES;
}
} 看上面的一個自定義的例子，上面的例子我們建立了一個保留10個Entry節點的LinkedHashMap。
3.2.5 總結
LinkedHashMap繼承自HashMap，同時提供了兩個非常有用的功能。
3.3 EnumMap和EnumSet
一般來說我們會選擇使用HashMap來存儲key-value格式的資料，考慮這樣的特殊情況，一個HashMap的key都來自于一個Enum類，這樣的情況則可以考慮使用本文要講的EnumMap。
3.3.1 EnumMap
先看一下EnumMap的定義和HashMap定義的比較：
public class EnumMap<K extends Enum<K>, V> extends AbstractMap<K, V>
implements java.io.Serializable, Cloneable public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable 我們可以看到EnumMap幾乎和HashMap是一樣的，差別在于EnumMap的key是一個Enum。
下面看一個簡單的使用的例子：
先定義一個Enum：
public enum Types {
RED, GREEN, BLACK, YELLO
} 再看下怎麼使用EnumMap：
@Test
public void useEnumMap(){
EnumMap<Types, String> activityMap = new EnumMap<>(Types.class);
activityMap.put(Types.BLACK,"black");
activityMap.put(Types.GREEN,"green");
activityMap.put(Types.RED,"red");
} 其他的操作其實和hashMap是類似的，我們這裡就不多講了。
3.3.2 什麼時候使用EnumMap
因為在EnumMap中，所有的key的可能值在建立的時候已經知道了，是以使用EnumMap和hashMap相比，可以提升效率。
同時，因為key比較簡單，是以EnumMap在實作中，也不需要像HashMap那樣考慮一些複雜的情況。
3.3.3 EnumSet
跟EnumMap很類似，EnumSet是一個set，然後set中的元素都是某個Enum類型。
EnumSet是一個抽象類，要建立EnumSet類可以使用EnumSet提供的兩個靜态方法，noneOf和allOf。
先看一個noneOf：
public static <E extends Enum<E>> EnumSet<E> noneOf(Class<E> elementType) {
Enum<?>[] universe = getUniverse(elementType);
if (universe == null)
throw new ClassCastException(elementType + " not an enum");
if (universe.length <= 64)
return new RegularEnumSet<>(elementType, universe);
else
return new JumboEnumSet<>(elementType, universe);
} noneOf傳入一個Enum類，傳回一個空的Enum類型的EnumSet。
從上面的代碼我們可以看到EnumSet有兩個實作，長度大于64的時候使用JumboEnumSet，小有64的時候使用RegularEnumSet。
注意，JumboEnumSet和RegularEnumSet不建議直接使用，他是内部使用的類。
再看一下allOf：
public static <E extends Enum<E>> EnumSet<E> allOf(Class<E> elementType) {
EnumSet<E> result = noneOf(elementType);
result.addAll();
return result;
} allOf很簡單，先調用noneOf建立空的set，然後調用addAll方法将所有的元素添加進去。
3.3.4 總結
EnumMap和EnumSet對特定的Enum對象做了優化，可以在合适的情況下使用。
3.4 SkipList和ConcurrentSkipListMap的實作
一開始聽說SkipList我是一臉懵逼的，啥？還有SkipList？這個是什麼玩意。
後面經過我的不斷搜尋和學習，終于明白了SkipList原來是一種資料結構，而java中的ConcurrentSkipListMap和ConcurrentSkipListSet就是這種結構的實作。
接下來就讓我們一步一步的揭開SkipList和ConcurrentSkipListMap的面紗吧。
3.4.1 SkipList
先看下維基百科中SkipList的定義：
SkipList是一種層級結構。最底層的是排序過的最原始的linked list。
往上是一層一層的層級結構，每個底層節點按照一定的機率出現在上一層list中。這個機率叫做p，通常p取1/2或者1/4。
先設定一個函數f，可以随機産生0和1這兩個數，并且這兩個數出現的幾率是一樣的，那麼這時候的p就是1/2。
對每個節點，我們這樣操作：
我們運作一次f，當f=1時，我們将該節點插入到上層layer的list中去。當f=0時，不插入。
舉個例子，上圖中的list中有10個排序過的節點，第一個節點預設每層都有。對于第二個節點，運作f=0，不插入。對于第三個節點，運作f=1,将第三個節點插入layer 1，以此類推，最後得到的layer 1 list中的節點有：1，3，4，6，9。
然後我們再繼續往上建構layer。 最終得到上圖的SkipList。
通過使用SkipList，我們建構了多個List，包含不同的排序過的節點，進而提升List的查找效率。
我們通過下圖能有一個更清晰的認識：
每次的查找都是從最頂層開始，因為最頂層的節點數最少，如果要查找的節點在list中的兩個節點中間，則向下移一層繼續查找，最終找到最底層要插入的位置，插入節點，然後再次調用機率函數f，決定是否向上複制節點。
其本質上相當于二分法查找，其查找的時間複雜度是O(logn)。
3.4.2 ConcurrentSkipListMap
ConcurrentSkipListMap是一個并發的SkipList，那麼它具有兩個特點，SkipList和concurrent。我們分别來講解。
- SkipList的實作
上面講解了SkipList的資料結構，接下來看下ConcurrentSkipListMap是怎麼實作這個skipList的：
ConcurrentSkipListMap中有三種結構，base nodes,Head nodes和index nodes。
base nodes組成了有序的連結清單結構，是ConcurrentSkipListMap的最底層實作。
static final class Node<K,V> {
final K key;
volatile Object value;
volatile Node<K,V> next;
/**
* Creates a new regular node.
*/
Node(K key, Object value, Node<K,V> next) {
this.key = key;
this.value = value;
this.next = next;
}
} 上面可以看到每個Node都是一個k，v的entry，并且其有一個next指向下一個節點。
index nodes是建構SkipList上層結構的基本節點：
static class Index<K,V> {
final Node<K,V> node;
final Index<K,V> down;
volatile Index<K,V> right;
/**
* Creates index node with given values.
*/
Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) {
this.node = node;
this.down = down;
this.right = right;
}
} 從上面的構造我們可以看到，Index節點包含了Node節點，除此之外，Index還有兩個指針，一個指向同一個layer的下一個節點，一個指向下一層layer的節點。
這樣的結構可以友善周遊的實作。
最後看一下HeadIndex，HeadIndex代表的是Head節點：
static final class HeadIndex<K,V> extends Index<K,V> {
final int level;
HeadIndex(Node<K,V> node, Index<K,V> down, Index<K,V> right, int level) {
super(node, down, right);
this.level = level;
}
} HeadIndex和Index很類似，隻不過多了一個level字段，表示所在的層級。
在ConcurrentSkipListMap初始化的時候，會初始化HeadIndex：
head = new HeadIndex<K,V>(new Node<K,V>(null, BASE_HEADER, null),null, null, 1); 我們可以看到HeadIndex中的Node是key=null，value=BASE_HEADER的虛拟節點。初始的level=1。
- concurrent的實作
接下來，我們再看一下并發是怎麼實作的：
基本上并發類都是通過UNSAFE.compareAndSwapObject來實作的，ConcurrentSkipListMap也不例外。
假如我們有三個節點，b-n-f。現在需要删除節點n。
第一步，使用CAS将n的valu的值從non-null設定為null。這個時候，任何外部的操作都會認為這個節點是不存在的。但是那些内部的插入或者删除操作還是會繼續修改n的next指針。
第二步，使用CAS将n的next指針指向一個新的marker節點，從這個時候開始，n的next指針将不會指向任何其他的節點。
我們看下marker節點的定義：
Node(Node<K,V> next) {
this.key = null;
this.value = this;
this.next = next;
} 我們可以看到marker節點實際上是一個key為null，value是自己的節點。
第三步，使用CAS将b的next指針指向f。從這一步起，n節點不會再被其他的程式通路，這意味着n可以被垃圾回收了。
我們思考一下為什麼要插入一個marker節點，這是因為我們在删除的時候，需要告訴所有的線程，節點n準備被删除了，因為n本來就指向f節點，這個時候需要一個中間節點來表示這個準備删除的狀态。
4. Queue
先看下Queue的定義：
public interface Queue<E> extends Collection<E> {
} Queue表示的是隊列，其特點就是先進先出。常用的Queue有DelayQueue，BlockingQueue等等。
4.1 java中的Queue家族
java中Collection集合有三大家族List，Set和Queue。當然Map也算是一種集合類，但Map并不繼承Collection接口。
List，Set在我們的工作中會經常使用，通常用來存儲結果資料，而Queue由于它的特殊性，通常用在生産者消費者模式中。
現在很火的消息中間件比如：Rabbit MQ等都是Queue這種資料結構的展開。
今天這篇文章将帶大家進入Queue家族。
4.1.1 Queue接口
先看下Queue的繼承關系和其中定義的方法：
Queue繼承自Collection，Collection繼承自Iterable。
Queue有三類主要的方法，我們用個表格來看一下他們的差別：
| 方法類型 | 方法名稱 | 差別 | |
|---|---|---|---|
| Insert | add | offer | 兩個方法都表示向Queue中添加某個元素，不同之處在于添加失敗的情況，add隻會傳回true，如果添加失敗，會抛出異常。offer在添加失敗的時候會傳回false。是以對那些有固定長度的Queue，優先使用offer方法。 |
| Remove | remove | poll | 如果Queue是空的情況下，remove會抛出異常，而poll會傳回null。 |
| Examine | element | peek | 擷取Queue頭部的元素，但不從Queue中删除。兩者的差別還是在于Queue為空的情況下，element會抛出異常，而peek傳回null。 |
注意，因為對poll和peek來說null是有特殊含義的，是以一般來說Queue中禁止插入null，但是在實作中還是有一些類允許插入null比如LinkedList。
盡管如此，我們在使用中還是要避免插入null元素。
4.1.2 Queue的分類
一般來說Queue可以分為BlockingQueue，Deque和TransferQueue三種。
- BlockingQueue
BlockingQueue是Queue的一種實作，它提供了兩種額外的功能：
- 當目前Queue是空的時候，從BlockingQueue中擷取元素的操作會被阻塞。
- 當目前Queue達到最大容量的時候，插入BlockingQueue的操作會被阻塞。
BlockingQueue的操作可以分為下面四類：
| 操作類型 | Throws exception | Special value | Blocks | Times out |
|---|---|---|---|---|
| add(e) | offer(e) | put(e) | offer(e, time, unit) | |
| remove() | poll() | take() | poll(time, unit) | |
| element() | peek() | not applicable |
第一類是會抛出異常的操作，當遇到插入失敗，隊列為空的時候抛出異常。
第二類是不會抛出異常的操作。
第三類是會Block的操作。當Queue為空或者達到最大容量的時候。
第四類是time out的操作，在給定的時間裡會Block，逾時會直接傳回。
BlockingQueue是線程安全的Queue,可以在生産者消費者模式的多線程中使用，如下所示：
class Producer implements Runnable {
private final BlockingQueue queue;
Producer(BlockingQueue q) { queue = q; }
public void run() {
try {
while (true) { queue.put(produce()); }
} catch (InterruptedException ex) { ... handle ...}
}
Object produce() { ... }
}
class Consumer implements Runnable {
private final BlockingQueue queue;
Consumer(BlockingQueue q) { queue = q; }
public void run() {
try {
while (true) { consume(queue.take()); }
} catch (InterruptedException ex) { ... handle ...}
}
void consume(Object x) { ... }
}
class Setup {
void main() {
BlockingQueue q = new SomeQueueImplementation();
Producer p = new Producer(q);
Consumer c1 = new Consumer(q);
Consumer c2 = new Consumer(q);
new Thread(p).start();
new Thread(c1).start();
new Thread(c2).start();
}
} 最後，在一個線程中向BlockQueue中插入元素之前的操作happens-before另外一個線程中從BlockQueue中删除或者擷取的操作。
- Deque
Deque是Queue的子類，它代表double ended queue，也就是說可以從Queue的頭部或者尾部插入和删除元素。
同樣的，我們也可以将Deque的方法用下面的表格來表示，Deque的方法可以分為對頭部的操作和對尾部的操作：
| addFirst(e) | offerFirst(e) | addLast(e) | offerLast(e) | |
| removeFirst() | pollFirst() | removeLast() | pollLast() | |
| getFirst() | peekFirst() | getLast() | peekLast() |
和Queue的方法描述基本一緻，這裡就不多講了。
當Deque以 FIFO (First-In-First-Out)的方法處理元素的時候，Deque就相當于一個Queue。
當Deque以LIFO (Last-In-First-Out)的方式處理元素的時候，Deque就相當于一個Stack。
- TransferQueue
TransferQueue繼承自BlockingQueue，為什麼叫Transfer呢？因為TransferQueue提供了一個transfer的方法，生産者可以調用這個transfer方法，進而等待消費者調用take或者poll方法從Queue中拿取資料。
還提供了非阻塞和timeout版本的tryTransfer方法以供使用。
我們舉個TransferQueue實作的生産者消費者的問題。
先定義一個生産者：
@Slf4j
@Data
@AllArgsConstructor
class Producer implements Runnable {
private TransferQueue<String> transferQueue;
private String name;
private Integer messageCount;
public static final AtomicInteger messageProduced = new AtomicInteger();
@Override
public void run() {
for (int i = 0; i < messageCount; i++) {
try {
boolean added = transferQueue.tryTransfer( "第"+i+"個", 2000, TimeUnit.MILLISECONDS);
log.info("transfered {} 是否成功: {}","第"+i+"個",added);
if(added){
messageProduced.incrementAndGet();
}
} catch (InterruptedException e) {
log.error(e.getMessage(),e);
}
}
log.info("total transfered {}",messageProduced.get());
}
} 在生産者的run方法中，我們調用了tryTransfer方法，等待2秒鐘，如果沒成功則直接傳回。
再定義一個消費者：
@Slf4j
@Data
@AllArgsConstructor
public class Consumer implements Runnable {
private TransferQueue<String> transferQueue;
private String name;
private int messageCount;
public static final AtomicInteger messageConsumed = new AtomicInteger();
@Override
public void run() {
for (int i = 0; i < messageCount; i++) {
try {
String element = transferQueue.take();
log.info("take {}",element );
messageConsumed.incrementAndGet();
Thread.sleep(500);
} catch (InterruptedException e) {
log.error(e.getMessage(),e);
}
}
log.info("total consumed {}",messageConsumed.get());
}
} 在run方法中，調用了transferQueue.take方法來取消息。
下面先看一下一個生産者，零個消費者的情況：
@Test
public void testOneProduceZeroConsumer() throws InterruptedException {
TransferQueue<String> transferQueue = new LinkedTransferQueue<>();
ExecutorService exService = Executors.newFixedThreadPool(10);
Producer producer = new Producer(transferQueue, "ProducerOne", 5);
exService.execute(producer);
exService.awaitTermination(50000, TimeUnit.MILLISECONDS);
exService.shutdown();
} [pool-1-thread-1] INFO com.flydean.Producer - transfered 第0個 是否成功: false
[pool-1-thread-1] INFO com.flydean.Producer - transfered 第1個 是否成功: false
[pool-1-thread-1] INFO com.flydean.Producer - transfered 第2個 是否成功: false
[pool-1-thread-1] INFO com.flydean.Producer - transfered 第3個 是否成功: false
[pool-1-thread-1] INFO com.flydean.Producer - transfered 第4個 是否成功: false
[pool-1-thread-1] INFO com.flydean.Producer - total transfered 0 可以看到，因為沒有消費者，是以消息并沒有發送成功。
再看下一個有消費者的情況：
@Test
public void testOneProduceOneConsumer() throws InterruptedException {
TransferQueue<String> transferQueue = new LinkedTransferQueue<>();
ExecutorService exService = Executors.newFixedThreadPool(10);
Producer producer = new Producer(transferQueue, "ProducerOne", 2);
Consumer consumer = new Consumer(transferQueue, "ConsumerOne", 2);
exService.execute(producer);
exService.execute(consumer);
exService.awaitTermination(50000, TimeUnit.MILLISECONDS);
exService.shutdown();
} [pool-1-thread-2] INFO com.flydean.Consumer - take 第0個
[pool-1-thread-1] INFO com.flydean.Producer - transfered 第0個 是否成功: true
[pool-1-thread-2] INFO com.flydean.Consumer - take 第1個
[pool-1-thread-1] INFO com.flydean.Producer - transfered 第1個 是否成功: true
[pool-1-thread-1] INFO com.flydean.Producer - total transfered 2
[pool-1-thread-2] INFO com.flydean.Consumer - total consumed 2 可以看到Producer和Consumer是一個一個來生産和消費的。
4.2 PriorityQueue和PriorityBlockingQueue
Queue一般來說都是FIFO的，當然之前我們也介紹過Deque可以做為棧來使用。今天我們介紹一種PriorityQueue，可以安裝對象的自然順序或者自定義順序在Queue中進行排序。
4.2.1 PriorityQueue
先看PriorityQueue，這個Queue繼承自AbstractQueue，是非線程安全的。
PriorityQueue的容量是unbounded的，也就是說它沒有容量大小的限制，是以你可以無限添加元素，如果添加的太多，最後會報OutOfMemoryError異常。
這裡教大家一個識别的技能，隻要集合類中帶有CAPACITY的，其底層實作大部分都是數組，因為隻有數組才有capacity，當然也有例外，比如LinkedBlockingDeque。
隻要集合類中帶有comparator的，那麼這個集合一定是個有序集合。
我們看下PriorityQueue：
private static final int DEFAULT_INITIAL_CAPACITY = 11;
private final Comparator<? super E> comparator;
定義了初始Capacity和comparator，那麼PriorityQueue的底層實作就是Array，并且它是一個有序集合。
有序集合預設情況下是按照natural ordering來排序的，如果你傳入了 Comparator,則會按照你指定的方式進行排序，我們看兩個排序的例子：
@Slf4j
public class PriorityQueueUsage {
@Test
public void usePriorityQueue(){
PriorityQueue<Integer> integerQueue = new PriorityQueue<>();
integerQueue.add(1);
integerQueue.add(3);
integerQueue.add(2);
int first = integerQueue.poll();
int second = integerQueue.poll();
int third = integerQueue.poll();
log.info("{},{},{}",first,second,third);
}
@Test
public void usePriorityQueueWithComparator(){
PriorityQueue<Integer> integerQueue = new PriorityQueue<>((a,b)-> b-a);
integerQueue.add(1);
integerQueue.add(3);
integerQueue.add(2);
int first = integerQueue.poll();
int second = integerQueue.poll();
int third = integerQueue.poll();
log.info("{},{},{}",first,second,third);
}
} 預設情況下會按照升序排列，第二個例子中我們傳入了一個逆序的Comparator，則會按照逆序排列。
4.2.2 PriorityBlockingQueue
PriorityBlockingQueue是一個BlockingQueue，是以它是線程安全的。
我們考慮這樣一個問題，如果兩個對象的natural ordering或者Comparator的順序是一樣的話，兩個對象的順序還是固定的嗎？
出現這種情況，預設順序是不能确定的，但是我們可以這樣封裝對象，讓對象可以在排序順序一緻的情況下，再按照建立順序先進先出FIFO的二次排序：
public class FIFOEntry<E extends Comparable<? super E>>
implements Comparable<FIFOEntry<E>> {
static final AtomicLong seq = new AtomicLong(0);
final long seqNum;
final E entry;
public FIFOEntry(E entry) {
seqNum = seq.getAndIncrement();
this.entry = entry;
}
public E getEntry() { return entry; }
public int compareTo(FIFOEntry<E> other) {
int res = entry.compareTo(other.entry);
if (res == 0 && other.entry != this.entry)
res = (seqNum < other.seqNum ? -1 : 1);
return res;
}
} 上面的例子中，先比較兩個Entry的natural ordering，如果一緻的話，再按照seqNum進行排序。
4.3 SynchronousQueue詳解
SynchronousQueue是BlockingQueue的一種，是以SynchronousQueue是線程安全的。SynchronousQueue和其他的BlockingQueue不同的是SynchronousQueue的capacity是0。即SynchronousQueue不存儲任何元素。
也就是說SynchronousQueue的每一次insert操作，必須等待其他線性的remove操作。而每一個remove操作也必須等待其他線程的insert操作。
這種特性可以讓我們想起了Exchanger。和Exchanger不同的是，使用SynchronousQueue可以在兩個線程中傳遞同一個對象。一個線程放對象，另外一個線程取對象。
4.3.1 舉例說明
我們舉一個多線程中傳遞對象的例子。還是舉生産者消費者的例子，在生産者中我們建立一個對象，在消費者中我們取出這個對象。先看一下用CountDownLatch該怎麼做：
@Test
public void useCountdownLatch() throws InterruptedException {
ExecutorService executor = Executors.newFixedThreadPool(2);
AtomicReference<Object> atomicReference= new AtomicReference<>();
CountDownLatch countDownLatch = new CountDownLatch(1);
Runnable producer = () -> {
Object object=new Object();
atomicReference.set(object);
log.info("produced {}",object);
countDownLatch.countDown();
};
Runnable consumer = () -> {
try {
countDownLatch.await();
Object object = atomicReference.get();
log.info("consumed {}",object);
} catch (InterruptedException ex) {
log.error(ex.getMessage(),ex);
}
};
executor.submit(producer);
executor.submit(consumer);
executor.awaitTermination(50000, TimeUnit.MILLISECONDS);
executor.shutdown();
} 上例中，我們使用AtomicReference來存儲要傳遞的對象，并且定義了一個型号量為1的CountDownLatch。
在producer中，我們存儲對象，并且countDown。
在consumer中，我們await,然後取出對象。
[pool-1-thread-1] INFO com.flydean.SynchronousQueueUsage - produced java.lang.Object@683d1b4b
[pool-1-thread-2] INFO com.flydean.SynchronousQueueUsage - consumed java.lang.Object@683d1b4b 可以看到傳入和輸出了同一個對象。
上面的例子我們也可以用SynchronousQueue來改寫：
@Test
public void useSynchronousQueue() throws InterruptedException {
ExecutorService executor = Executors.newFixedThreadPool(2);
SynchronousQueue<Object> synchronousQueue=new SynchronousQueue<>();
Runnable producer = () -> {
Object object=new Object();
try {
synchronousQueue.put(object);
} catch (InterruptedException ex) {
log.error(ex.getMessage(),ex);
}
log.info("produced {}",object);
};
Runnable consumer = () -> {
try {
Object object = synchronousQueue.take();
log.info("consumed {}",object);
} catch (InterruptedException ex) {
log.error(ex.getMessage(),ex);
}
};
executor.submit(producer);
executor.submit(consumer);
executor.awaitTermination(50000, TimeUnit.MILLISECONDS);
executor.shutdown();
} 上面的例子中，如果我們使用synchronousQueue，則可以不用手動同步，也不需要額外的存儲。
如果我們需要在代碼中用到這種線程中傳遞對象的情況，那麼使用synchronousQueue吧。
4.4 DelayQueue的使用
今天給大家介紹一下DelayQueue,DelayQueue是BlockingQueue的一種，是以它是線程安全的，DelayQueue的特點就是插入Queue中的資料可以按照自定義的delay時間進行排序。隻有delay時間小于0的元素才能夠被取出。
4.4.1 DelayQueue
先看一下DelayQueue的定義：
public class DelayQueue<E extends Delayed> extends AbstractQueue<E>
implements BlockingQueue<E> 從定義可以看到，DelayQueue中存入的對象都必須是Delayed的子類。
Delayed繼承自Comparable，并且需要實作一個getDelay的方法。
為什麼這樣設計呢？
因為DelayQueue的底層存儲是一個PriorityQueue，在之前的文章中我們講過了，PriorityQueue是一個可排序的Queue，其中的元素必須實作Comparable方法。而getDelay方法則用來判斷排序後的元素是否可以從Queue中取出。
4.4.2 DelayQueue的應用
DelayQueue一般用于生産者消費者模式，我們下面舉一個具體的例子。
首先要使用DelayQueue，必須自定義一個Delayed對象：
@Data
public class DelayedUser implements Delayed {
private String name;
private long avaibleTime;
public DelayedUser(String name, long delayTime){
this.name=name;
//avaibleTime = 目前時間+ delayTime
this.avaibleTime=delayTime + System.currentTimeMillis();
}
@Override
public long getDelay(TimeUnit unit) {
//判斷avaibleTime是否大于目前系統時間，并将結果轉換成MILLISECONDS
long diffTime= avaibleTime- System.currentTimeMillis();
return unit.convert(diffTime,TimeUnit.MILLISECONDS);
}
@Override
public int compareTo(Delayed o) {
//compareTo用在DelayedUser的排序
return (int)(this.avaibleTime - ((DelayedUser) o).getAvaibleTime());
}
} 上面的對象中，我們需要實作getDelay和compareTo方法。
接下來我們建立一個生産者：
@Slf4j
@Data
@AllArgsConstructor
class DelayedQueueProducer implements Runnable {
private DelayQueue<DelayedUser> delayQueue;
private Integer messageCount;
private long delayedTime;
@Override
public void run() {
for (int i = 0; i < messageCount; i++) {
try {
DelayedUser delayedUser = new DelayedUser(
new Random().nextInt(1000)+"", delayedTime);
log.info("put delayedUser {}",delayedUser);
delayQueue.put(delayedUser);
Thread.sleep(500);
} catch (InterruptedException e) {
log.error(e.getMessage(),e);
}
}
}
} 在生産者中，我們每隔0.5秒建立一個新的DelayedUser對象，并入Queue。
再建立一個消費者：
@Slf4j
@Data
@AllArgsConstructor
public class DelayedQueueConsumer implements Runnable {
private DelayQueue<DelayedUser> delayQueue;
private int messageCount;
@Override
public void run() {
for (int i = 0; i < messageCount; i++) {
try {
DelayedUser element = delayQueue.take();
log.info("take {}",element );
} catch (InterruptedException e) {
log.error(e.getMessage(),e);
}
}
}
} 在消費者中，我們循環從queue中擷取對象。
最後看一個調用的例子：
@Test
public void useDelayedQueue() throws InterruptedException {
ExecutorService executor = Executors.newFixedThreadPool(2);
DelayQueue<DelayedUser> queue = new DelayQueue<>();
int messageCount = 2;
long delayTime = 500;
DelayedQueueConsumer consumer = new DelayedQueueConsumer(
queue, messageCount);
DelayedQueueProducer producer = new DelayedQueueProducer(
queue, messageCount, delayTime);
// when
executor.submit(producer);
executor.submit(consumer);
// then
executor.awaitTermination(5, TimeUnit.SECONDS);
executor.shutdown();
} 上面的測試例子中，我們定義了兩個線程的線程池，生産者産生兩條消息，delayTime設定為0.5秒，也就是說0.5秒之後，插入的對象能夠被擷取到。
線程池在5秒之後會被關閉。
運作看下結果：
[pool-1-thread-1] INFO com.flydean.DelayedQueueProducer - put delayedUser DelayedUser(name=917, avaibleTime=1587623188389)
[pool-1-thread-2] INFO com.flydean.DelayedQueueConsumer - take DelayedUser(name=917, avaibleTime=1587623188389)
[pool-1-thread-1] INFO com.flydean.DelayedQueueProducer - put delayedUser DelayedUser(name=487, avaibleTime=1587623188899)
[pool-1-thread-2] INFO com.flydean.DelayedQueueConsumer - take DelayedUser(name=487, avaibleTime=1587623188899) 我們看到消息的put和take是交替進行的，符合我們的預期。
如果我們做下修改，将delayTime修改為50000，那麼線上程池關閉之前插入的元素是不會過期的，也就是說消費者是無法擷取到結果的。
DelayQueue是一種有奇怪特性的BlockingQueue，可以在需要的時候使用。
5. 其他的要點
5.1 Comparable和Comparator的差別
java.lang.Comparable和java.util.Comparator是兩個容易混淆的接口,兩者都帶有比較的意思，那麼兩個接口到底有什麼差別，分别在什麼情況下使用呢？
5.1.1 Comparable
Comparable是java.lang包下面的接口，lang包下面可以看做是java的基礎語言接口。
實際上Comparable接口隻定義了一個方法：
public int compareTo(T o); 實作這個接口的類都需要實作compareTo方法，表示兩個類之間的比較。
這個比較排序之後的order，按照java的說法叫做natural ordering。這個order用在一些可排序的集合比如：SortedSet，SortedMap等等。
當使用這些可排序的集合添加相應的對象時，就會調用compareTo方法來進行natural ordering的排序。
幾乎所有的數字類型對象：Integer, Long，Double等都實作了這個Comparable接口。
5.1.2 Comparator
Comparator是一個FunctionalInterface，需要實作compare方法：
int compare(T o1, T o2); Comparator在java.util包中，代表其是一個工具類，用來輔助排序的。
在講Comparable的時候，我們提到Comparable指定了對象的natural ordering，如果我們在添加到可排序集合類的時候想按照我們自定義的方式進行排序，這個時候就需要使用到Comparator了。
Collections.sort(List,Comparator),Arrays.sort(Object[],Comparator) 等這些輔助的方法類都可以通過傳入一個Comparator來自定義排序規則。
在排序過程中，首先會去檢查Comparator是否存在，如果不存在則會使用預設的natural ordering。
還有一個差別就是Comparator允許對null參數的比較，而Comparable是不允許的，否則會爬出NullPointerException。
5.1.3 舉個例子
最後，我們舉一個natural ordering和Comparator的例子：
@Test
public void useCompare(){
List<Integer> list1 = Arrays.asList(5, 3, 2, 4, 1);
Collections.sort(list1);
log.info("{}",list1);
List<Integer> list2 = Arrays.asList(5, 3, 2, 4, 1);
Collections.sort(list2, (a, b) -> b - a);
log.info("{}",list2);
} [main] INFO com.flydean.CompareUsage - [1, 2, 3, 4, 5]
[main] INFO com.flydean.CompareUsage - [5, 4, 3, 2, 1] 預設情況下Integer是按照升序來排的，但是我們可以通過傳入一個Comparator來改變這個過程。
5.2 Reference和引用類型
java中有值類型也有引用類型，引用類型一般是針對于java中對象來說的，今天介紹一下java中的引用類型。java為引用類型專門定義了一個類叫做Reference。Reference是跟java垃圾回收機制息息相關的類，通過探讨Reference的實作可以更加深入的了解java的垃圾回收是怎麼工作的。
本文先從java中的四種引用類型開始，一步一步揭開Reference的面紗。
java中的四種引用類型分别是：強引用，軟引用，弱引用和虛引用。
5.2.1 強引用Strong Reference
java中的引用預設就是強引用，任何一個對象的指派操作就産生了對這個對象的強引用。
我們看一個例子：
public class StrongReferenceUsage {
@Test
public void stringReference(){
Object obj = new Object();
}
} 上面我們new了一個Object對象，并将其指派給obj，這個obj就是new Object()的強引用。
強引用的特性是隻要有強引用存在，被引用的對象就不會被垃圾回收。
5.2.2 軟引用Soft Reference
軟引用在java中有個專門的SoftReference類型，軟引用的意思是隻有在記憶體不足的情況下，被引用的對象才會被回收。
先看下SoftReference的定義：
public class SoftReference<T> extends Reference<T> SoftReference繼承自Reference。它有兩種構造函數：
public SoftReference(T referent) 和：
public SoftReference(T referent, ReferenceQueue<? super T> q) 第一個參數很好了解，就是軟引用的對象，第二個參數叫做ReferenceQueue，是用來存儲封裝的待回收Reference對象的，ReferenceQueue中的對象是由Reference類中的ReferenceHandler内部類進行處理的。
我們舉個SoftReference的例子：
@Test
public void softReference(){
Object obj = new Object();
SoftReference<Object> soft = new SoftReference<>(obj);
obj = null;
log.info("{}",soft.get());
System.gc();
log.info("{}",soft.get());
} 22:50:43.733 [main] INFO com.flydean.SoftReferenceUsage - java.lang.Object@71bc1ae4
22:50:43.749 [main] INFO com.flydean.SoftReferenceUsage - java.lang.Object@71bc1ae4 可以看到在記憶體充足的情況下，SoftReference引用的對象是不會被回收的。
5.2.3 弱引用weak Reference
weakReference和softReference很類似，不同的是weekReference引用的對象隻要垃圾回收執行，就會被回收，而不管是否記憶體不足。
同樣的WeakReference也有兩個構造函數：
public WeakReference(T referent)；
public WeakReference(T referent, ReferenceQueue<? super T> q)； 含義和SoftReference一緻，這裡就不再重複表述了。
我們看下弱引用的例子：
@Test
public void weakReference() throws InterruptedException {
Object obj = new Object();
WeakReference<Object> weak = new WeakReference<>(obj);
obj = null;
log.info("{}",weak.get());
System.gc();
log.info("{}",weak.get());
} 22:58:02.019 [main] INFO com.flydean.WeakReferenceUsage - java.lang.Object@71bc1ae4
22:58:02.047 [main] INFO com.flydean.WeakReferenceUsage - null 我們看到gc過後，弱引用的對象被回收掉了。
5.2.4 虛引用PhantomReference
PhantomReference的作用是跟蹤垃圾回收器收集對象的活動，在GC的過程中，如果發現有PhantomReference，GC則會将引用放到ReferenceQueue中，由程式員自己處理，當程式員調用ReferenceQueue.pull()方法，将引用出ReferenceQueue移除之後，Reference對象會變成Inactive狀态，意味着被引用的對象可以被回收了。
和SoftReference和WeakReference不同的是，PhantomReference隻有一個構造函數，必須傳入ReferenceQueue：
public PhantomReference(T referent, ReferenceQueue<? super T> q) 看一個PhantomReference的例子：
@Slf4j
public class PhantomReferenceUsage {
@Test
public void usePhantomReference(){
ReferenceQueue<Object> rq = new ReferenceQueue<>();
Object obj = new Object();
PhantomReference<Object> phantomReference = new PhantomReference<>(obj,rq);
obj = null;
log.info("{}",phantomReference.get());
System.gc();
Reference<Object> r = (Reference<Object>)rq.poll();
log.info("{}",r);
}
} 07:06:46.336 [main] INFO com.flydean.PhantomReferenceUsage - null
07:06:46.353 [main] INFO com.flydean.PhantomReferenceUsage - java.lang.ref.PhantomReference@136432db 我們看到get的值是null，而GC過後，poll是有值的。
因為PhantomReference引用的是需要被垃圾回收的對象，是以在類的定義中，get一直都是傳回null：
public T get() {
return null;
} 5.2.5 Reference和ReferenceQueue
講完上面的四種引用,接下來我們談一下他們的父類Reference和ReferenceQueue的作用。
Reference是一個抽象類，每個Reference都有一個指向的對象，在Reference中有5個非常重要的屬性：referent，next，discovered，pending，queue。
private T referent; /* Treated specially by GC */
volatile ReferenceQueue<? super T> queue;
Reference next;
transient private Reference<T> discovered; /* used by VM */
private static Reference<Object> pending = null; 每個Reference都可以看成是一個節點，多個Reference通過next，discovered和pending這三個屬性進行關聯。
先用一張圖來對Reference有個整體的概念：
referent就是Reference實際引用的對象。
通過next屬性，可以建構ReferenceQueue。
通過discovered屬性，可以建構Discovered List。
通過pending屬性，可以建構Pending List。
- 四大狀态
在講這三個Queue/List之前，我們先講一下Reference的四個狀态：
從上面的圖中，我們可以看到一個Reference可以有四個狀态。
因為Reference有兩個構造函數，一個帶ReferenceQueue,一個不帶。
Reference(T referent) {
this(referent, null);
}
Reference(T referent, ReferenceQueue<? super T> queue) {
this.referent = referent;
this.queue = (queue == null) ? ReferenceQueue.NULL : queue;
} 對于帶ReferenceQueue的Reference，GC會把要回收對象的Reference放到ReferenceQueue中，後續該Reference需要程式員自己處理（調用poll方法）。
不帶ReferenceQueue的Reference，由GC自己處理，待回收的對象其Reference狀态會變成Inactive。
建立好了Reference，就進入active狀态。
active狀态下，如果引用對象的可到達狀态發送變化就會轉變成Inactive或Pending狀态。
Inactive狀态很好了解，到達Inactive狀态的Reference狀态不能被改變，會等待GC回收。
Pending狀态代表等待入Queue，Reference内部有個ReferenceHandler，會調用enqueue方法，将Pending對象入到Queue中。
入Queue的對象，其狀态就變成了Enqueued。
Enqueued狀态的對象，如果調用poll方法從ReferenceQueue拿出，則該Reference的狀态就變成了Inactive，等待GC的回收。
這就是Reference的一個完整的生命周期。
- 三個Queue/List
有了上面四個狀态的概念，我們接下來講三個Queue/List：ReferenceQueue，discovered List和pending List。
ReferenceQueue在講狀态的時候已經講過了，它本質是由Reference中的next連接配接而成的。用來存儲GC待回收的對象。
pending List就是待入ReferenceQueue的list。
discovered List這個有點特别，在Pending狀态時候，discovered List就等于pending List。
在Active狀态的時候，discovered List實際上維持的是一個引用鍊。通過這個引用鍊，我們可以獲得引用的鍊式結構，當某個Reference狀态不再是Active狀态時，需要将這個Reference從discovered List中删除。
5.2.6 WeakHashMap
最後講一下WeakHashMap，WeakHashMap跟WeakReference有點類似，在WeakHashMap如果key不再被使用，被指派為null的時候，該key對應的Entry會自動從WeakHashMap中删除。
我們舉個例子：
@Test
public void useWeakHashMap(){
WeakHashMap<Object, Object> map = new WeakHashMap<>();
Object key1= new Object();
Object value1= new Object();
Object key2= new Object();
Object value2= new Object();
map.put(key1, value1);
map.put(key2, value2);
log.info("{}",map);
key1 = null;
System.gc();
log.info("{}",map);
} [main] INFO com.flydean.WeakHashMapUsage - {java.lang.Object@14899482=java.lang.Object@2437c6dc, java.lang.Object@11028347=java.lang.Object@1f89ab83}
[main] INFO com.flydean.WeakHashMapUsage - {java.lang.Object@14899482=java.lang.Object@2437c6dc} 可以看到gc過後，WeakHashMap隻有一個Entry了。
5.3 類型擦除type erasure
泛型是java從JDK 5開始引入的新特性，泛型的引入可以讓我們在代碼編譯的時候就強制檢查傳入的類型，進而提升了程式的健壯度。
泛型可以用在類和接口上，在集合類中非常常見。本文将會講解泛型導緻的類型擦除。
5.3.1 舉個例子
我們先舉一個最簡單的例子：
@Slf4j
public class TypeErase {
public static void main(String[] args) {
ArrayList<String> stringArrayList = new ArrayList<String>();
stringArrayList.add("a");
stringArrayList.add("b");
action(stringArrayList);
}
public static void action(ArrayList<Object> al){
for(Object o: al)
log.info("{}",o);
}
} 上面的例子中，我們定義了一個ArrayList，其中指定的類型是String。
然後調用了action方法，action方法需要傳入一個ArrayList，但是這個list的類型是Object。
乍看之下好像沒有問題，因為String是Object的子類，是可以進行轉換的。
但是實際上代碼編譯出錯：
Error:(18, 16) java: 不相容的類型: java.util.ArrayList<java.lang.String>無法轉換為java.util.ArrayList<java.lang.Object> 5.3.2 原因
上面例子的原因就是類型擦除（type erasure)。java中的泛型是在編譯時做檢測的。而編譯後生成的二進制檔案中并不儲存類型相關的資訊。
上面的例子中，編譯之後不管是ArrayList<String> 還是ArrayList<Object> 都會變成ArrayList。其中的類型Object/String對JVM是不可見的。
但是在編譯的過程中，編譯器發現了兩者的類型不同，然後抛出了錯誤。
5.3.3 解決辦法
要解決上面的問題，我們可以使用下面的辦法：
public static void actionTwo(ArrayList<?> al){
for(Object o: al)
log.info("{}",o);
} 通過使用通配符？，可以比對任何類型，進而通過編譯。
但是要注意這裡actionTwo方法中，因為我們不知道傳入的類型到底是什麼，是以我們不能在actionTwo中添加任何元素。
5.3.4 總結
從上面的例子我們可以看出，ArrayList<String>并不是ArrayList<Object>的子類。如果一定要找出父子關系，那麼ArrayList<String>是Collection<String>的子類。
但是Object[] objArray是String[] strArr的父類。因為對Array來說，其具體的類型是已知的。
5.4 深入了解java的泛型
泛型是JDK 5引入的概念，泛型的引入主要是為了保證java中類型的安全性，有點像C++中的模闆。
但是Java為了保證向下相容性，它的泛型全部都是在編譯期間實作的。編譯器執行類型檢查和類型推斷，然後生成普通的非泛型的位元組碼。這種就叫做類型擦除。編譯器在編譯的過程中執行類型檢查來保證類型安全，但是在随後的位元組碼生成之前将其擦除。
這樣就會帶來讓人困惑的結果。本文将會詳細講解泛型在java中的使用，以避免進入誤區。
5.4.1 泛型和協變
有關協變和逆變的詳細說明可以參考:
深入了解協變和逆變這裡我再總結一下，協變和逆變隻有在類型聲明中的類型參數裡才有意義，對參數化的方法沒有意義，因為該标記影響的是子類繼承行為，而方法沒有子類。
當然java中沒有顯示的表示參數類型是協變還是逆變。
協變意思是如果有兩個類 A<T> 和 A<C>, 其中C是T的子類，那麼我們可以用A來替代A。
逆變就是相反的關系。
Java中數組就是協變的，比如Integer是Number的子類，那麼Integer[]也是 Number[]的子類，我們可以在需要 Number[] 的時候傳入 Integer[]。
接下來我們考慮泛型的情況，List<Number> 是不是 List<Integer>的父類呢？很遺憾，并不是。
我們得出這樣一個結論：泛型不是協變的。
為什麼呢？我們舉個例子：
List<Integer> integerList = new ArrayList<>();
List<Number> numberList = integerList; // compile error
numberList.add(new Float(1.111)); 假如integerList可以指派給numberList，那麼numberList可以添加任意Number類型，比如Float，這樣就違背了泛型的初衷，向Integer list中添加了Float。是以上面的操作是不被允許的。
剛剛我們講到Array是協變的，如果在Array中帶入泛型，則會發生編譯錯誤。比如new List<String>[10]是不合法的，但是 new List<?>[10]是可以的。因為在泛型中?表示的是未知類型。
List<?>[] list1 = new List<?>[10];
List<String>[] list2 = new List<String>[10]; //compile error 5.4.2 泛型在使用中會遇到的問題
因為類型擦除的原因，List<String>和List<Integer>在運作是都會被當做成為List。是以我們在使用泛型時候的一些操作會遇到問題。
假如我們有一個泛型的類，類中有一個方法，方法的參數是泛型，我們想在這個方法中對泛型參數進行一個拷貝操作。
public class CustUser<T> {
public void useT(T param){
T copy = new T(param); // compile error
}
} 上面操作會編譯失敗，因為我們并不知道T是什麼，也不知道T到底有沒有相應的構造函數。
直接clone T是沒有辦法了，如果我們想copy一個Set，set中的類型是未定義的該怎麼做呢？
public void useTSet(Set<?> set){
Set<?> copy1 = new HashSet<?>(set); // compile error
Set<?> copy2 = new HashSet<>(set);
Set<?> copy3 = new HashSet<Object>(set);
} 可以看到?是不能直接用于執行個體化的。但是我們可以用下面的兩種方式代替。
再看看Array的使用：
public void useArray(){
T[] typeArray1= new T[20]; //compile error
T[] typeArray2=(T[]) new Object[20];
T[] typeArray3 = (T[]) Array.newInstance(String.class, 20);
} 同樣的，T是不能直接用于執行個體化的，但是我們可以用下面兩種方式代替。
5.4.3 類型擦除要注意的事項
因為類型擦除的原因，我們在接口實作中，實作同一個接口的兩個不同類型是無意義的：
public class someClass implements Comparable<Number>, Comparable<String> { ... } // no 因為在編譯過後的位元組碼看來，兩個Comparable是一樣的。
同樣的，我們使用T來做類型強制轉換也是沒有意義的：
public <T> T cast(T t, Object o) { return (T) o; } 因為編譯器并不知道這個強制轉換是對還是錯。
總結
集合是java中一個非常重要的工具類型，希望大家能夠熟練掌握。
本文的代碼例子
https://github.com/ddean2009/learn-java-collections本文的PDF
java-collection-all-in-one.pdf本文已收錄于 http://www.flydean.com/java-collection-all-in-one/最通俗的解讀，最深刻的幹貨，最簡潔的教程，衆多你不知道的小技巧等你來發現！
歡迎關注我的公衆号:「程式那些事」,懂技術，更懂你！