在JDK8中rt.jar文件中，java.util.*包中的容器主要包括List、Set、Queue和Map四大類，其中List、Set、Queue是和Collection接口相關(guān)的容器，而Map是單獨列出來的容器。

類圖.png

• Collection是最基本的集合接口，一個Collection代表一組Object，即Collection的元素（Element）。一些Collection允許相同的元素而另一些不行。一些能排序而另一些不行。Java SDK不提供直接繼承自Collection的類JavaSDK提供的類都是繼承自Collection的子接口，如List和Set。
• 所有實現(xiàn)Collection接口的類都必須提供兩個標(biāo)準(zhǔn)的構(gòu)造函數(shù)：無參數(shù)的構(gòu)造函數(shù)用于構(gòu)建一個空的Collection，有一個Collection的參數(shù)的構(gòu)造函數(shù)用于創(chuàng)建一個新的Collection，這個新的Collection與傳入的Collection有相同的元素。后一個構(gòu)造函數(shù)允許用戶復(fù)制一個Collection。
• 如何遍歷Collection中的每一個元素？
  • 不論Collection的實際類型如何，它都支持一個iterator()的方法，該方法返回一個對象，使用該迭代對象即可逐一訪問Collection中每一個元素。典型用法如下：

Iterator it = collection.iterator();//獲得一個迭代對象
    while(it.hasNext()){
Object obj = it.next();//得到下一個對象
}

具體

• Set集合
  • Set集合是最簡單的集合，集合中的對象不按照特定的方式排序。主要有：HashSet()和TreeSet().
• HashSet
  • HashSet類按照哈希算法來存取集合中的對象，具有很好的存取性能。當(dāng)HashSet向集合中加入一個對象時，會調(diào)用對象的HashCode()方法獲取哈希碼，然后根據(jù)這個哈希碼進(jìn)一步計算出對象在集合中的存放位置。
• TreeSet實現(xiàn)了SortedSet接口可以對集合中的元素排序。

List集合

• List繼承自Collection接口。List是一種有序集合，List中的元素可以根據(jù)索引（順序號：元素在集合中處于的位置信息） 進(jìn)行取得/刪除/插入操作。
  跟Set集合不同的是，List允許有重復(fù)元素。對于滿足e1.equals(e2)條件的e1與e2對象元素，可以同時存在于List集合中。當(dāng)然，也有List的實現(xiàn)類不允許重復(fù)元素的存在。同時，List還提供一個listIterator()方法，返回一個ListIterator接口對象，和Iterator接口相比，ListIterator添加元素的添加，刪除，和設(shè)定等方法，還能向前或向后遍歷，具體的方法往下看。List接口的實現(xiàn)類主要有ArrayList，LinkedList，Vector，Stack等。

List算法

ArrayList

• ArrayList實現(xiàn)了可變大小的數(shù)組。它允許所有元素，包括null。ArrayList沒有同步。size、isEmpty、get、set方法運行時間為常數(shù)。但是add方法開銷為分?jǐn)偟某?shù)，添加n個元素需要O(n)的時間。其他的方法運行時間為線性。

  每個ArrayList實例都有一個容量（Capacity），即用于存儲元素的數(shù)組大小。這個容量可隨著不斷添加新元素而自動增加，但是增長算法并沒有定義。當(dāng)需要插入大量元素時，在插入前可以調(diào)用ensureCapacity方法來增加ArrayList的容量以提高插入效率。

• 主要方法：

• 排序方法

LinkedList

LinkedList實現(xiàn)了List接口，允許null元素。此外LinkedList提供額外的get，remove，insert方法在LinkedList的首部或尾部。這些操作使LinkedList可被用作堆棧（stack），隊列（queue）或雙向隊列（deque）。

<font color=red>注意LinkedList沒有同步方法。如果多個線程同時訪問一個List，則必須自己實現(xiàn)訪問同步。一種解決方法是在創(chuàng)建List時構(gòu)造一個同步的List：</font>

List list = Collections.synchronizedList(new LinkedList(...));

Map.jpg

Map

• Map是一種把鍵對象和值對象進(jìn)行映射的集合，它的每一個元素都包含一堆鍵對象和值對象；
• 向Map添加元素時，必須提供鍵對象和值對象；
• 從Map中檢索元素時，只要給出鍵對象，就可以返回對應(yīng)的值對象；
• 鍵對象不能重復(fù)，但值對象可以重復(fù)；
• Map有兩種常見的實現(xiàn)類：HashMap和TreeMap。

HashMap

HashMap按照哈希算法來存取鍵對象，有很好的存取性能。和HashSet一樣，要求當(dāng)兩個鍵對象通過equals()方法比較為true時，這兩個鍵對象的hashCode()方法返回的哈希碼也一樣。

HashCode:

1. HashCode的存在主要是用于<font color=red>查找的快捷性</font>，如Hashtable，HashMap，等，HashCode經(jīng)藏用語確定對象的存儲地址
2. 如果兩個對象相同，equals方法一定返回true，并且這兩個對象的HashCode一定相同
3. <font color=red>兩個對象的HashCode相同，并不一定表示兩個對象就相同</font>，即equals()不一定為true，只能說明這兩個對象在一個散列存儲結(jié)構(gòu)中
4. <font color=red>如果對象的equals()方法被重寫，那么對象的HashCode也盡量重寫</font>

• 作用：

  從Object的角度看，JVM每new一個Object，它都會將這個Object懟到一個Hash表中去，這樣的話，下次做Object的比較或者取這個對象的時候（讀取過程），它會根據(jù)對象的HashCode再從Hash表中取這個對象。這樣做的目的是。若HashCode相同再去調(diào)用equal。

TreeMap

TreeMap實現(xiàn)了SortedMap接口，能對鍵對象進(jìn)行排序。同TreeSet一樣，TreeMap也支持自然排序和客戶化排序兩種方式。

如果涉及到堆棧，隊列等操作，應(yīng)該考慮用List，對于需要快速插入，刪除元素，應(yīng)該使用LinkedList，如果需要快速隨機(jī)訪問元素，應(yīng)該使用ArrayList。盡量返回接口而非實際的類型，如返回List而非ArrayList，這樣如果以后需要將ArrayList換成LinkedList時，客戶端代碼不用改變。這就是針對抽象編程。

Interface Iterable<T>

• The functions forEach() and spliterator() both use a keword “default” which means we could provide the default implement in an abstruct class，breaking the previous rule in JAVA.

<font color=blue>JDK8 Functional interface</font>

remark1:

1. Three methods

   1.1 The only abstract method

   1.2 use default to define general methods, invoking through an instance.

   1.3 use static define static methods, invoking through interface name.

2. a new annotation

   if some interface is functional interface ,then making it has only one abstract method when defining.So there is a new annonation:

   @FunctionInterface

remark2(lambda expression):

<font color=blue>use anonymous inner class to impement an interface:</font>

Function<Integer,String> fun = new Function<Integer,String>(){
  @Override
  public String apply(Integer t){
        return String.valueOf(t);
  }
}

<font color=blue>use lambda expression to implement:</font>

Function<Integer,string> -> (t){String.valueOf(t);}

Collection<E> extends Iterable<E>

• 

  • if the collection contains more than Integer.MAX_VALUE elements, returns Integer.MAX_VALUE, otherwise return the number of elements in it.

• ;

  • if the collection empty, return true;

• <font color=blue>boolean contains(Object o)</font>

  • return ture if the collection contain the specified element.

• 

  • return an iterator over the elements in the collection, unless provide a guarantee itself, there are no guarantee concerning the order in which the elements are returned.

• 

  • returns am array containing all of the elements in this collection.

• 

  • Params:
    • a: the array into which the elements of this collection are to stored,if it is big enough; otherwise. a new array of the same runtime type is allocated for this purpose.If the collecition fits in the specified array with room to spare, the element in the array immediately following the end of the collection is set to null.
  • Returns:
    • an array containing all of the elements in this collection.

• 

  • return true if operation successful;

• <font color=blue>boolean remove(Object o)</font>

• <font color=blue>boolean containsAll(Collection<?> c);</font>

  • return true if this collection contains all of the elements in the specified collection.

• <font color=blue>boolean addAll(Collection<? extends E> c);</font>

• <font color=blue>boolean removeAll(Collection<?> c);</font>

• <font color=blue>default boolean removeIf(Predicate<? super E> filter){...}</font>

  • Removes all of the elements of this collection that satisfy the given predicate.
  • true if any elements were removed.

• <font color=blue>boolean retainAll(Collection<?> c);</font>

  • Removes from this collection all of its elements that are not contained in the specified collection.

• <font color=blue>void clear();</font>

  • Removes all of the elements from this collection.The collection will be empty after this methods returns.

• <font color=blue>boolean equals(Object o);</font>

  • <font color=red>Attention: if implements the Controller interface ”directly“ ， must exercise care if if they choose to override the Object.equals.(When need compare the value instead of inference)</font>
  • returns true if the specified object is equals to this collection.

• <font color=blue>int hashCode();</font>

  • <font color=red>Attention:if override the method Object.equals then must override Object.hashCode()</font>（because of hashcode contract）
  • Returns the hashcode of the collection

• <font color=blue>default Spliterator<E> spliterator(){...}</font>

  • Creates a Spliterator over the elements in this collection.
    • Spliterator: always used with steam to traverse and divide sequential.

• <font color=blue>default Stream<E> stream() {...}</font>

  • Returns a sequential Stream with this collection as its source.

• <font color=blue>default Stream<E> parallelStream() {...}</font>

  • Returns a possibly parallel Stream with this collection as its source. It is allowable for this method to return a sequential stream.

List<E> extends Collection<E>

• <font color=blue>boolean addAll(int index,Collection<? extends E> c);</font>

  • Inserts all of the elements in the specified collection into this list at the specified position.

• <font color=blue>boolean retainAll(Collection<?> c)</font>

  • Retains only the elements in this list that are contained in the specified collection.

• <font color=blue>default void replaceAll(UnaryOperator<E> operator){...}</font>

  • Replaces each element of the list with the result of applying the operator to that element.

• <font color=blue>default void sort(Comparator<? super E> c){...}</font>

  • sorts this list according to the order induced by the specified Comparator.

• <font color=blue>E set(int index, E element);</font>

  • replace the element at the specified position in this list with the specified element.
  • returns the element previously at the specified position.

• <font color=blue>E get(int index)</font>

  • reurns the element at the specified position.

• <font color=blue>int indexOf(Object o);</font>

  • Returns the index of the last occurrence of the specified element in this list, or -1 if this list does not contain the element.

• <font color=blue>int lastIndexOf(Object o);</font>

  • Returns the index of the last occurrence of the specified element in this list , or -1 if there is no such index.

• <font color=blue>ListIterator<E> listIterator();</font>

  • returns a list iterator over the elements in this list(in proper sequence).

• <font color=blue>ListIterator<E> listIterator(int index);</font>

  • Returns a list iterator over the elements in this list, starting at the specified position in the list.

• <font color=blue>List<E> subList(int fromIndex,int toIndex);</font>

  • returns a view of portion of this list between the specified fromIndex, inclusive,and toIndex, exclusive.(If fromIndex and toIndex are equal, the returned list is empty).

AbstractList<E> extends AbstractCollection<E> implements list<E>

Transient: the key word to avoid serializable;

checkForComodification();

used to realize fail-fast mechanism.

There are two threads, one is for traversing the list and another is for modifying the list.Sometimes thread A is traversing the list(at this moment expectedModCount=modCount=N), meanwhile thread B adds an element leading to the value of modCount modified(modCount+1=N+1). Method checkForComodification find that expectedModCunt=N, while modCount=N+1 which means two values are not equal, so the ConcurrentModificationException are throwed out and fail-fast mechanism happened.

cursor:the index of next element

lastRet:the index of last element

• <font color=blue>public List<E> subList(int fromIndex, int toIndex)</font>

public List<E> subList(int fromIndex,int toIndex) {
  return (this instance of RandomAccess? new RandomAccessSubList<>(this,fromIndex, toIndex):new SubList<>(this, fromIndex, toIndex));
}

public interface RandomAccess{}

RandomAccess is an empty interface to identify some class backing random access or not. A class that backing random access aparently could use a more efficient arithmetic.

• classes realized random access：
  • ArrayList
  • AttributeList
  • CopyOnWriteArrayList
  • Vector
  • Stack
  • Etc...