java_basic

list

List以線性方式存儲元素，集合中可以存放重復對象，元素有序。
最常用實現(xiàn)類：

ArrayList：隨機訪問元素快，增刪元素慢。
Vector：Vector與ArrayList相似。但Vector的方法是線程安全的，而ArrayList的方法不是，
        由于線程的同步必然要影響性能，因此ArrayList的性能比Vector好。
LinkedList：隨機訪問元素慢，順序訪問快，增刪元素快。
Stack：棧，繼承Vector，特點是先進后出(FILO, First In Last Out)。

set

Set不保存重復的元素。Set與Collection有完全一樣的接口。Set接口不保證維護元素的次序。
最常用實現(xiàn)類：

HashSet : 隨機查找快。存入HashSet的對象必須定義hashCode()。HashSet查找某個對象時，
          首先用hashCode()方法計算出這個對象的Hash碼，然后再根據(jù)Hash碼到相應的存儲區(qū)域用equals()方法查找，從而提高了效率。
TreeSet : 保存次序的Set, 底層為樹結構。使用它可以從Set中提取有序的序列。
LinkedHashSet : 具有HashSet的查詢速度，且內(nèi)部使用鏈表維護元素的順序。于是在使用迭代器遍歷Set時，結果會按元素插入的次序顯示。

Map

Map 是一種把鍵對象和值對象映射的集合，它的每一個元素都包含一對鍵對象和值對象。 Map沒有繼承于Collection接口。
最常用的實現(xiàn)類：

HashMap：Map基于哈希表的 Map 接口的實現(xiàn)。
HashTable：hashtable和hashmap，從存儲結構和實現(xiàn)來講基本上都是相同的，最大的不同就是hashtable是線程安全的。
LinkedHashMap： LinkedHashMap是HashMap的一個子類，是Map接口的哈希表和鏈接列表實現(xiàn)。
               它維護著一個雙重鏈接列表。此鏈接列表定義了迭代順序，該迭代順序可以是插入順序或者是訪問順序。
TreeMap ： 基于紅黑樹的實現(xiàn)。

工具類

Iterator迭代器、ListIterator迭代器、Enumeration枚舉類、Arrays 和 Collections

Iterator迭代器:        迭代器是一個用來遍歷并選擇序列中的對象。Java的Iterator的只能單向移動。
ListIterator迭代器:    ListIterator是一個更加強大的Iterator的子類型。它只能用于各種List類的訪問。它最大的優(yōu)點是可以雙向移動。
Arrays:               Java.util.Arrays類能方便地操作數(shù)組，它提供的所有方法都是靜態(tài)的。
Collections:          java.util.Collections是一個包含各種有關集合操作的靜態(tài)多態(tài)方法的工具類，服務于Java的Collection框架。

ArrayList Vector LinkedList Stack fail-fast

1   arraylist 主要是擴容
    
 private void grow(int minCapacity) {
        // 獲取當前數(shù)組的容量
        int oldCapacity = elementData.length;
        // 擴容。新的容量=當前容量+當前容量/2.即將當前容量增加一半。
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //如果擴容后的容量還是小于想要的最小容量
        if (newCapacity - minCapacity < 0)
            //將擴容后的容量再次擴容為想要的最小容量
            newCapacity = minCapacity;
        //如果擴容后的容量大于臨界值，則進行大容量分配
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData,newCapacity);
    }
 Iterator迭代器、ListIterator迭代器  都是快速失敗的 （fail-fast）

2   Vector

    Vector底層是數(shù)組。
    有序。Vector底層是數(shù)組，數(shù)組是有序的。
    可重復。數(shù)組是可重復的。
    隨機訪問效率高，增刪效率低。通過索引可以很快的查找到對應元素，而增刪元素許多元素的位置都要改變。
    線程安全。很多方法都是synchronized的。

3 fail-fast

    fail-fast 機制是java容器（Collection和Map都存在fail-fast機制）中的一種錯誤機制。在遍歷一個容器對象時，當容器結構被修改，
    很有可能會拋出ConcurrentModificationException，產(chǎn)生fail-fast。  

4   LinkedList

    LinkedList底層是雙向鏈表。
    有序。鏈表是有序的。
    元素可重復。鏈表元素可重復。
    隨機訪問效率低，增刪效率高。

    ArrayList與迭代器模式
    Vector與迭代器模式
    LinkedList與迭代器模式
    
5   棧 Stack  先進后出(FILO, First In Last Out) 

    public class Stack<E> extends Vector<E>
    它繼承Vector，并額外提供了push、pop、peek、empty、search這幾個方法。
    當stack被第一次創(chuàng)建時，它包含0個元素。
    Deque接口和它的實現(xiàn)是更強大的先進先出的棧的實現(xiàn)。
    
總結:

List以線性方式存儲元素，集合中可以存放重復對象，元素有序。

最常用實現(xiàn)類：
ArrayList：隨機訪問元素快，增刪元素慢。
Vector：Vector與ArrayList相似。但Vector的方法是線程安全的，而ArrayList的方法不是，由于線程的同步必然要影響性能，因此ArrayList的性能比Vector好。
LinkedList：隨機訪問元素慢，順序訪問快，增刪元素快。
Stack：棧，繼承Vector，特點是先進后出(FILO, First In Last Out)。
從上面List的各個實現(xiàn)類的特點不難得出以下結論：

需要快速插入刪除元素，應使用LinkedList
不需要快速插入刪除元素，需要快速隨機訪問元素
只有單個線程操作list，應使用ArrayList
有多個線程操作list，應使用Vector

Hashtable與HashMap不同點

Hashtable不建議在新代碼中使用，不需要線程安全的場合可以用HashMap替換，需要線程安全的場合可以用ConcurrentHashMap替換。

HashMap與LinkedHashMap比較

不同點:

相同點:

都是基于哈希表的實現(xiàn)。
存儲的是鍵值對映射。
都繼承了AbstractMap，實現(xiàn)了Map、Cloneable、Serializable。
它們的構造函數(shù)都一樣。
默認的容量大小是16，默認的加載因子是0.75。
都允許key和value為null。
都是線程不安全的。

TreeMap與HashMap比較

不同點:

增刪改查操作的時間復雜度 O(1) log(n)

相同點:

都以鍵值對的形式存儲數(shù)據(jù)。
都繼承了AbstractMap，實現(xiàn)了Map、Cloneable、Serializable。
都是非同步的。

實現(xiàn)類比較

內(nèi)部排序，至少掌握基礎算法如歸并排序、交換排序（冒泡、快排）、選擇排序、插入排序等。
外部排序，掌握利用內(nèi)存和外部存儲處理超大數(shù)據(jù)集，至少要理解過程和思路。