java集合類主要分為兩大體系，繼承自Collection的List和Set,還有自己作為根的Map.大體的結(jié)構(gòu)如下.

Collection
├List
│├LinkedList
│├ArrayList
│└Vector
│　└Stack
└Set
 ├HashSet
 ├TreeSet
Map
├Hashtable
├HashMap
└TreeMap
└WeakHashMap

Map

HashMap通過hash表實(shí)現(xiàn)的key-value存儲(chǔ)，按照key的hashCode存儲(chǔ)，可以有null key,
TreeMap是有序的，通過key的Comparable比較器實(shí)現(xiàn)key-value的有序存儲(chǔ)
LinkedHashMap也是有序的，也是通過key的hashCode存儲(chǔ)，但是遍歷是增加了有序?qū)傩裕磁c加入的順序保持一致

HashMap

HashMap是基于hash算法實(shí)現(xiàn)的，通過hash因子的作用，將元素"比較平均"的分散，以提高元素查找的命中率.具體的實(shí)現(xiàn)原理如下圖：

HashMap是非線程安全的，允許null key,當(dāng)threshold=capacity*loadfactor時(shí)會(huì)擴(kuò)容為capacity<<1,這里capacity為桶的數(shù)量.

以下是put<k,v>()方法：

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    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;
}

可以看到優(yōu)先判斷null key，然后計(jì)算key的hash值，通過hash值與capacity結(jié)合判斷位于Hash桶的位置,然后判斷是否有當(dāng)前key的Entry,如果存在，替換value為新值，并返回舊的value，否則添加一個(gè)新的Entry,并且返回null，如果一個(gè)桶已有至少一個(gè)Entry，則會(huì)作為鏈表的第一個(gè)元素插入.

HashTable

HashTable的原理與HashMap原理類似，只是比較特殊的所有操作加上了對(duì)當(dāng)前對(duì)象操作的synchronized,以達(dá)到同步鎖的功能，從而實(shí)現(xiàn)線程同步.

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;
}

 private int hash(Object k) {
        // hashSeed will be zero if alternative hashing is disabled.
        return hashSeed ^ k.hashCode();
    }

從上可知,HashTable不允許加入null key,null value.

還有一個(gè)就是，HashTable初始容量是11.

Collection

Hashset

Hashset本應(yīng)不在map系列,但由于Hashset的實(shí)現(xiàn)是基于HashMap實(shí)現(xiàn)的，所以這里列出，

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

/**
 * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
 * default initial capacity (16) and load factor (0.75).
 */
public HashSet() {
    map = new HashMap<>();
}

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

從上可以看出,每次add一個(gè)元素，其實(shí)是將該元素當(dāng)做一個(gè)key存入Hashmap中,value為一個(gè)"dummy value"(一個(gè)Object對(duì)象).所以其實(shí)是通過Hashmap保證了元素的唯一.

LinkedList與Queue

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

可知LinkedList實(shí)現(xiàn)了Deque，而Deque是豐富了父接口Queue，
Queue是Collection接口的子類，Collection實(shí)現(xiàn)了Iterable,所以是可遍歷的。

而Map沒有實(shí)現(xiàn)Iterable，但是通過一系列方法如entrySet()等轉(zhuǎn)換成集合類Set來實(shí)現(xiàn)遍歷功能.

Arraylist

Arraylist的實(shí)現(xiàn)是基于數(shù)組的，初始數(shù)組大小為10,容量不足時(shí)擴(kuò)展為原來的1.5倍.

Collections

Collections主要是作為集合方法的一些擴(kuò)展，有大量的static方法，來幫助我們方便的處理集合，在其中主要摘兩點(diǎn)做一些研究：

不變的empty集合

Collections含有很多的靜態(tài)空集合方法，其實(shí)我們使用這些特性的地方無非有兩處：

1. 在自己的方法中return null處return Collections.emptyList(),這樣可以避免上層調(diào)用使用時(shí)發(fā)生NullPointException.
   2.返回一個(gè)不可變(引用不可變)的集合實(shí)例.

  @SuppressWarnings("unchecked")
   public static final <T> List<T> emptyList() {
       return (List<T>) EMPTY_LIST;
   }

  @SuppressWarnings("unchecked")
   public static final List EMPTY_LIST = new EmptyList<>();

上面是返回emptyList的源碼.

不變的empty迭代器

大多數(shù)空方法返回的是不變空集合，但是有以下三個(gè)方法返回的是空迭代器：<T> Enumeration<T> emptyEnumeration() (classic iteration method), <T> Iterator<T> emptyIterator(), and <T> ListIterator<T> emptyListIterator()
作用也無非上面返回空集合的那些作用.

    @SuppressWarnings("unchecked")
    public static <T> Iterator<T> emptyIterator() {
        return (Iterator<T>) EmptyIterator.EMPTY_ITERATOR;
    }

    private static class EmptyIterator<E> implements Iterator<E> {
        static final EmptyIterator<Object> EMPTY_ITERATOR
            = new EmptyIterator<>();

        public boolean hasNext() { return false; }
        public E next() { throw new NoSuchElementException(); }
        public void remove() { throw new IllegalStateException(); }
    }

綜上，我們可以得出結(jié)論，這些空方法可以幫助我們讓編碼更安全，防止空引用的發(fā)生。

Extend

ConcurrentModificationException while Iterating over ArrayList

3 ways to find duplicate elements in an array Java