collection1.png

　　Java的類集（Collection）框架使你的程序處理對象組的方法標準化。類集框架被設計用于適應幾個目的今布。首先经备，這種框架是高性能的。對基本類集（動態(tài)數(shù)組部默，鏈接表侵蒙，樹和散列表）的實現(xiàn)是高效率的。一般很少需要人工去對這些“數(shù)據(jù)引擎”編寫代碼（如果有的話）傅蹂。第二點纷闺，框架必須允許不同類型的類集以相同的方式和高度互操作方式工作算凿。第三點，類集必須是容易擴展和/或修改的犁功。為了實現(xiàn)這一目標氓轰，類集框架被設計成包含一組標準的接口。對這些接口浸卦，提供了幾個標準的實現(xiàn)工具（例如LinkedList戒努，HashSet和TreeSet），通常就是這樣使用的镐躲。如果你愿意的話，也可以實現(xiàn)你自己的類集侍筛。為了方便起見萤皂，創(chuàng)建用于各種特殊目的的實現(xiàn)工具。一部分工具可以使你自己的類集實現(xiàn)更加容易匣椰。最后裆熙，增加了允許將標準數(shù)組融合到類集框架中的機制。
Set接口：
　　集合接口定義了一個集合禽笑。它擴展了Collection并說明了不允許復制元素的類集的特性入录。因此，如果試圖將復制元素加到集合中時佳镜，add()方法將返回false（不拋異常）僚稿。
HashSet:
　　對于 HashSet 而言，它是基于 HashMap 實現(xiàn)的蟀伸，HashSet 底層采用 HashMap 來保存所有元素蚀同，因此 HashSet 的實現(xiàn)比較簡單，它只是封裝了一個 HashMap 對象來存儲所有的集合元素啊掏，所有放入 HashSet 中的集合元素實際上由 HashMap 的 key 來保存蠢络，而 HashMap 的 value 則存儲了一個 PRESENT，它是一個靜態(tài)的 Object 對象迟蜜。 HashSet 的絕大部分方法都是通過調(diào)用 HashMap 的方法來實現(xiàn)的刹孔，因此 HashSet 和 HashMap 兩個集合在實現(xiàn)本質(zhì)上是相同的。

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

TreeSet:
　　TreeSet是實現(xiàn)了SortedSet接口娜睛，SortedSet接口定義了幾種方法髓霞，使得對集合的處理更加方便。調(diào)用first()方法微姊，可以獲得集合中的第一個對象酸茴。調(diào)用last()方法，可以獲得集合中的最后一個元素兢交。調(diào)用subSet()方法薪捍，可以獲得排序集合的一個指定了第一個和最后一個對象的子集合。如果需要得到從集合的第一個元素開始的一個子集合，可以使用headSet()方法酪穿。如果需要獲得集合尾部的一個子集合凳干，可以使用tailSet()方法。
　　TreeSet支持兩種排序方法：自然排序和定制排序被济。
　　自然排序：TreeSet調(diào)用集合元素的compareTo(Object obj)方法來比較元素之間的大小救赐，然后按照元素升序排列。這就要求對象元素必須實現(xiàn)Comparable接口中的compareTo(Object obj)方法只磷。在自然排序下经磅，TreeSet判斷兩個對象是否相同的唯一標準：兩個對象通過compareTo(Object o)方法比較是否相等：該方法返回0，則認為相等钮追，返回1則認為不相等预厌。java的一些常見的類，例如Character元媚，String轧叽，Date等已經(jīng)實現(xiàn)了Comparable接口。
　　定制排序：在創(chuàng)建TreeSet集合對象時刊棕，需要關(guān)聯(lián)一個Comparator對象炭晒，并且實現(xiàn)Comparator中的compare(T obj1,T obj 2)。當通過Comparator對象實現(xiàn)TreeSet的定制排序時甥角，也不可以向TreeSet中添加不同類型的對象(public TreeSet(Comparator<? super E> comparator))网严。

public class Text {
    public static void main(String[] args) {
        TreeSet<String> set = new TreeSet<String>();
                set.add("c");
        set.add("a");
        set.add("ef");
        set.add("b");
        set.add("e");
        set.add("d");
        SortedSet<String> subSet1 = set.subSet("b", "e");
        System.out.println(subSet1); //[b, c, d]
        SortedSet<String> subSet2 = set.headSet("b");
        System.out.println(subSet2);  //[a]
        SortedSet<String> subSet3 = set.tailSet("e");
        System.out.println(subSet3);  //[e, ef]
    }
}

用Set獲取數(shù)據(jù)時只能用迭代或者foreach來取值。
List接口
　　List是有序的Collection嗤无，使用此接口能夠精確的控制每個元素插入的位置屿笼。用戶能夠使用索引（元素在List中的位置，類似于數(shù)組下 >標）來訪問List中的元素翁巍，這類似于Java的數(shù)組驴一。
ArrayList：
　　ArrayList是一個基于數(shù)組上的鏈表，它擴展AbstractList并執(zhí)行List接口灶壶。ArrayList支持可隨需要而增長的動態(tài)數(shù)組肝断。在Java中，標準數(shù)組是定長的驰凛。在數(shù)組創(chuàng)建之后胸懈，它們不能被加長或縮短，這也就意味著你必須事先知道數(shù)組可以容納多少元素恰响。但是趣钱，你直到運行時才能知道需要多大的數(shù)組。為了解決這個問題胚宦，類集框架定義了ArrayList首有。本質(zhì)上燕垃，ArrayList是對象引用的一個變長數(shù)組。也就是說井联，ArrayList能夠動態(tài)地增加或減小其大小卜壕。數(shù)組列表以一個原始大小被創(chuàng)建。當超過了它的大小烙常，類集自動增大（當前長度的1.5倍轴捎，初始化長度為10，這里可以用初始化長度來進行性能優(yōu)化）蚕脏。
　　當使用ArrayList時侦副，有時想要獲得一個實際的數(shù)組，這個數(shù)組包含了列表的內(nèi)容驼鞭≡韭澹可以通過調(diào)用方法toArray()來實現(xiàn)它。（數(shù)組轉(zhuǎn)list：Arrays.asList()返回一個受指定數(shù)組支持的固定大小的列表）

public class Text {
    public static void main(String[] args) {
        String[] array = new String[2];
        List<String> list2 = Arrays.asList(array);
        array[0] = "test2";
        System.out.println(list2);
        list2.add("test");
        System.out.println(list2);
    }
}

在add時會拋出UnsupportedOperationException终议，原因是asList返回的是一個Array的一個內(nèi)部類而不是真正的ArrayList：

image.png

Vector：
　　同ArrayList一樣是一個基于數(shù)組上的鏈表，但是不同的是Vector是同步的葱蝗。
LinkedList：
　　與ArrayList一樣實現(xiàn)List接口穴张，只是ArrayList是List接口的大小可變數(shù)組的實現(xiàn)，LinkedList是List接口鏈表的實現(xiàn)两曼≡砀剩基于鏈表實現(xiàn)的方式使得LinkedList在插入和刪除時更優(yōu)于ArrayList，而隨機訪問則比ArrayList遜色些悼凑。
　　LinkedList除了它繼承的方法之外偿枕，LinkedList類本身還定義了一些有用的方法，這些方法主要用于操作和訪問列表户辫。使用addFirst()方法可以在列表頭增加元素渐夸；使用。使用add()方法的add(int, Object)形式渔欢，插入項目到指定的位置墓塌。調(diào)用getFirst()方法可以獲得第一個元素。調(diào)用getLast()方法可以得到最后一個元素奥额。為了刪除第一個元素苫幢，可以使用removeFirst()方法；為了刪除最后一個元素垫挨，可以調(diào)用removeLast()方法韩肝。

List 在很多方面跟 Array 數(shù)組感覺很相似，尤其是 ArrayList九榔，那 List 和數(shù)組究竟哪個更好呢哀峻？
　　相似之處：
　　　　都可以表示一組同類型的對象
　　　　都使用下標進行索引
　　不同之處：
　　　　數(shù)組可以存任何類型元素
　　　　List 不可以存基本數(shù)據(jù)類型涡相，必須要包裝
　　　　數(shù)組容量固定不可改變；List 容量可動態(tài)增長
　　　　數(shù)組效率高; List 由于要維護額外內(nèi)容谜诫，效率相對低一些

Map 接口：
　　Map用于保存具體映射關(guān)系的數(shù)據(jù)漾峡，因此Map集合里保存著兩組值，一組值用于保存Map里的key喻旷，另外一組值用于保存Map里的value生逸，key和value都可以是任意類型的數(shù)據(jù)。Map的key不允許重復且预，即同一個Map對象的任何兩個key通過equals方法比較總是返回false槽袄，每個key只能映射一個value。Map接口提供3種集合的視圖锋谐，Map的內(nèi)容可以被當作一組key集合遍尺，一組value集合，或者一組key-value映射涮拗。
HashMap:
　　對于 HashMap 而言乾戏，系統(tǒng) key-value 當成一個整體進行處理，系統(tǒng)總是根據(jù) Hash 算法來計算 key-value 的存儲位置三热，這樣可以保證能快速存鼓择、取 Map 的 key-value 對。
　　當程序執(zhí)行 put(key, value)方法時就漾，系統(tǒng)將調(diào)用key的 hashCode() 方法得到其 hashCode 值——每個 Java 對象都有 hashCode() 方法呐能，都可通過該方法獲得它的 hashCode 值。得到這個對象的 hashCode 值之后抑堡，系統(tǒng)會根據(jù)該 hashCode 值來決定該元素的存儲位置摆出。
　　取值時，HashMap 可以根據(jù)索引首妖、快速地取出該 bucket 里的 Entry偎漫；在發(fā)生“Hash 沖突”的情況下，單個 bucket 里存儲的不是一個 Entry有缆，而是一個 Entry 鏈骑丸，系統(tǒng)只能必須按順序遍歷每個 Entry，直到找到想搜索的 Entry 為止

public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }
 public V get(Object key) {
        if (key == null)
            return getForNullKey();
        Entry<K,V> entry = getEntry(key);
        return null == entry ? null : entry.getValue();
    }
final Entry<K,V> getEntry(Object key) {
        int hash = (key == null) ? 0 : hash(key);
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
    }

Hashtable：
　　Hashtable（先存在的）幾乎可以等價于HashMap妒貌。與HashMap相比Hashtable是synchronized通危，這意味著Hashtable是線程安全的，多個線程可以共享一個Hashtable灌曙；而如果沒有正確的同步的話菊碟，多個線程是不能共享HashMap的。Hashtable是線程安全的在刺，性能上就要比HashMap差一點逆害。
　　另一個區(qū)別是HashMap的迭代器(Iterator)是fail-fast迭代器头镊，而Hashtable的enumerator迭代器不是fail-fast的。所以當有其它線程改變了HashMap的結(jié)構(gòu)（增加或者移除元素）魄幕，將會拋出ConcurrentModificationException相艇，但迭代器本身的remove()方法移除元素則不會拋出ConcurrentModificationException異常。但這并不是一個一定發(fā)生的行為纯陨，要看JVM坛芽。這條同樣也是Enumeration和Iterator的區(qū)別。
　　Hashtable不可以接受null(HashMap可以接受為null的鍵值(key)和值(value))翼抠。

public synchronized V put(K key, V value) {
        // Make sure the value is not null
        if (value == null) {
            throw new NullPointerException();
        }
        // Makes sure the key is not already in the hashtable.
        Entry tab[] = table;
        int hash = hash(key);
        int index = (hash & 0x7FFFFFFF) % tab.length;
        for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                V old = e.value;
                e.value = value;
                return old;
            }
        }
        modCount++;
        if (count >= threshold) {
            // Rehash the table if the threshold is exceeded
            rehash();
            tab = table;
            hash = hash(key);
            index = (hash & 0x7FFFFFFF) % tab.length;
        }
        // Creates the new entry.
        Entry<K,V> e = tab[index];
        tab[index] = new Entry<>(hash, key, value, e);
        count++;
        return null;
    }
int hash(Object k) {
        if (useAltHashing) {
            if (k.getClass() == String.class) {
                return sun.misc.Hashing.stringHash32((String) k);
            } else {
                int h = hashSeed ^ k.hashCode();

                // This function ensures that hashCodes that differ only by
                // constant multiples at each bit position have a bounded
                // number of collisions (approximately 8 at default load factor).
                h ^= (h >>> 20) ^ (h >>> 12);
                return h ^ (h >>> 7) ^ (h >>> 4);
             }
        } else  {
            return k.hashCode();
        }
    }

ConcurrentHashMap:
　　ConcurrentHashMap也是題中線程安全的map咙轩，他融合了hashtable和hashmap二者的優(yōu)勢。

鎖.png

public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {
        return new SynchronizedMap<>(m);
    }

    /**
     * @serial include
     */
    private static class SynchronizedMap<K,V>
        implements Map<K,V>, Serializable {
        private static final long serialVersionUID = 1978198479659022715L;

        private final Map<K,V> m;     // Backing Map
        final Object      mutex;        // Object on which to synchronize

        SynchronizedMap(Map<K,V> m) {
            if (m==null)
                throw new NullPointerException();
            this.m = m;
            mutex = this;
        }

        SynchronizedMap(Map<K,V> m, Object mutex) {
            this.m = m;
            this.mutex = mutex;
        }

        public int size() {
            synchronized (mutex) {return m.size();}
        }
        public boolean isEmpty() {
            synchronized (mutex) {return m.isEmpty();}
        }
        public boolean containsKey(Object key) {
            synchronized (mutex) {return m.containsKey(key);}
        }
        public boolean containsValue(Object value) {
            synchronized (mutex) {return m.containsValue(value);}
        }
        public V get(Object key) {
            synchronized (mutex) {return m.get(key);}
        }
        //......
}

性能：ConcurrentHashMap性能是明顯優(yōu)于Hashtable和SynchronizedMap的。