1. HashMap
1.1 基本概念
1.1.1 HashMap 是一個散清單，它存儲的内容是鍵值對(key-value)映射。
1.1.2 HashMap<K,V>extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable
1.1.3 HashMap 的實作不是同步的，這意味着它不是線程安全的
1.1.4 HashMap 的執行個體有兩個參數影響其性能：“初始容量” 和 “加載因子”.
初始容量 隻是哈希表在建立時的容量
-> static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final int MAXIMUM_CAPACITY = 1 << 30;
加載因子 是哈希表在其容量自動增加之前可以達到多滿的一種尺度。當哈希表中的條目數超出了加載因子與目前容量的乘積時，則要對該哈希表進行 rehash 操作（即重建内部資料結構），進而哈希表将具有大約兩倍的桶數。
-> static final float DEFAULT_LOAD_FACTOR = 0.75f;
1.2 HashMap 的資料結構
實際上 HashMap的實作，是一個Entry數組，然後每個Entry元素又是一個單向連結清單。HashMap是以這種資料結構來解決hash碰撞的。在使用HashMap的時候，需要根據自己的實際情況來判斷是否重寫equals 和 hashcode方法 。
因為也是以數組的形式存在，是以擴容的時候，和Arraylist是一樣的，需要開辟一個更大的空間，然後copy老資料。但是擴容的方式是不一樣的，當hashmap的使用達到初始容量*加載因子的時候，HashMap 是直接擴充到原先的2倍。
1.3 主要的對外方法
1.3.1 clear() ：clear() 的作用是清空HashMap。它是通過将所有的元素設為null來實作的。
1.3.2 containsKey() containsKey() 的作用是判斷HashMap是否包含key。
1.3.3 containsValue() containsValue() 的作用是判斷HashMap是否包含“值為value”的元素。
注意： 在hashset的方法中是contains方法，因為set不存在相同的元素，是以不用區分 key 和 value
1.3.4 entrySet()、values()、keySet()
entrySet()的作用是傳回“HashMap中所有Entry的集合”，它是一個集合。當我們通過entrySet()擷取到的Iterator的next()方法去周遊HashMap時，實際上調用的是 nextEntry() 。而nextEntry()的實作方式，先周遊Entry(根據Entry在table中的序号，從小到大的周遊)；然後對每個Entry(即每個單向連結清單)，逐個周遊。
1.3.5 get() get() 的作用是擷取key對應的value，
1.3.6 put() put() 的作用是對外提供接口，讓HashMap對象可以通過put()将“key-value”添加到HashMap中。
注意 ：
若要添加到HashMap中的鍵值對對應的key已經存在HashMap中，則找到該鍵值對；然後新的value取代舊的value，并退出！
若要添加到HashMap中的鍵值對對應的key不在HashMap中，則将其添加到該哈希值對應的連結清單中，并調用addEntry()。
1.3.7 putAll() 将"m"的全部元素都添加到HashMap中
1.3.8 remove() remove() 的作用是删除“鍵為key”元素
2. ConcurrentHashMap
2.1 背景
哈希表是中非常高效，複雜度為O(1)，我們最常見到最頻繁使用的就是HashMap和HashTable，但是線上程競争激烈的并發場景中使用都不夠合理。
HashMap ：先說HashMap，HashMap是線程不安全的，在并發環境下，可能會形成環狀連結清單（擴容時可能造成，具體原因自行百度google或檢視源碼分析），導緻get操作時，cpu空轉，是以，在并發環境中使用HashMap是非常危險的。
HashTable ： HashTable和HashMap的實作原理幾乎一樣，差别無非是1.HashTable不允許key和value為null；2.HashTable是線程安全的。但是HashTable線程安全的政策實作代價卻太大了，簡單粗暴，get/put所有相關操作都是synchronized的，這相當于給整個哈希表加了一把大鎖，多線程通路時候，隻要有一個線程通路或操作該對象，那其他線程隻能阻塞，相當于将所有的操作串行化，在競争激烈的并發場景中性能就會非常差。
HashTable性能差主要是由于所有操作需要競争同一把鎖，而如果容器中有多把鎖，每一把鎖鎖一段資料，這樣在多線程通路時不同段的資料時，就不會存在鎖競争了，這樣便可以有效地提高并發效率。這就是ConcurrentHashMap所采用的"分段鎖"思想。
ConcurrentHashMap采用了非常精妙的"分段鎖"政策，ConcurrentHashMap的主幹是個Segment數組。
final Segment<K,V>[] segments; Segment繼承了ReentrantLock，是以它就是一種可重入鎖（ReentrantLock)。在ConcurrentHashMap，一個Segment就是一個子哈希表，Segment裡維護了一個HashEntry數組，并發環境下，對于不同Segment的資料進行操作是不用考慮鎖競争的。（就按預設的ConcurrentLeve為16來講，理論上就允許16個線程并發執行，有木有很酷）
是以，對于同一個Segment的操作才需考慮線程同步，不同的Segment則無需考慮。
Segment類似于HashMap，一個Segment維護着一個HashEntry數組
transient volatile HashEntry<K,V>[] table; HashEntry是目前我們提到的最小的邏輯處理單元了。一個ConcurrentHashMap維護一個Segment數組，一個Segment維護一個HashEntry數組。
static final class HashEntry<K,V> {
final int hash;
final K key;
volatile V value;
volatile HashEntry<K,V> next;
//其他省略
} 我們說Segment類似哈希表，那麼一些屬性就跟我們之前提到的HashMap差不離，比如負載因子loadFactor，比如門檻值threshold等等，看下Segment的構造方法
從上面的代碼可以看出來,Segment數組的大小ssize是由concurrentLevel來決定的，但是卻不一定等于concurrentLevel，ssize一定是大于或等于concurrentLevel的最小的2的次幂。比如：預設情況下concurrentLevel是16，則ssize為16；若concurrentLevel為14，ssize為16；若concurrentLevel為17，則ssize為32。為什麼Segment的數組大小一定是2的次幂？其實主要是便于通過按位與的雜湊演算法來定位Segment的index。
3. TreeMap （參考 ： https://www.cnblogs.com/skywang12345/p/3310928.html）
3.1 基本概念
3.1.1 TreeMap<K,V> extends AbstractMap<K,V>implements NavigableMap<K,V>, Cloneable, java.io.Serializable
3.1.2 TreeMap 實作了NavigableMap接口，意味着它支援一系列的導航方法。比如傳回有序的key集合。
3.1.3 TreeMap基于紅黑樹（Red-Black tree）實作。該映射根據其鍵的自然順序進行排序，或者根據建立映射時提供的 Comparator 進行排序，具體取決于使用的構造方法。
3.1.4 TreeMap的基本操作 containsKey、get、put 和 remove 的時間複雜度是 log(n) 。
3.1.5 TreeMap是非同步的。 它的iterator 方法傳回的疊代器是fail-fast的。
3.2 TreeMap的資料結構 -> 基于紅黑樹的
3.3 主要的對外方法 ：
3.3.1 TreeMap的Entry相關函數
firstEntry()、 lastEntry()、 lowerEntry()、 higherEntry()、 floorEntry()、 ceilingEntry()、 pollFirstEntry() 、 pollLastEntry()
3.3.2 TreeMap的key相關函數
firstKey()、lastKey()、lowerKey()、higherKey()、floorKey()、ceilingKey()
3.3.3 values()， 傳回“TreeMap中值的集合”
3.3.4 entrySet()函數 傳回“鍵值對集合”。
3.3.5 順序周遊和逆序周遊
由于TreeMap中的元素是從小到大的順序排列的。是以，順序周遊，就是從第一個元素開始，逐個向後周遊；而倒序周遊則恰恰相反，它是從最後一個元素開始，逐個往前周遊。
我們可以通過 keyIterator() 和 descendingKeyIterator()來說明！
keyIterator()的作用是傳回順序的KEY的集合，
descendingKeyIterator()的作用是傳回逆序的KEY的集合。
因為很多操作涉及到紅黑樹（目前了解不是特别好），後續有時間，再多補充一些内容
-》紅黑樹請參考http://www.cnblogs.com/skywang12345/p/3245399.html ， 感謝大神的分析
4. ArrayMap
4.1 存儲方式 ： ArrayMap的存儲中沒有Entry這個東西，他是由兩個數組來維護的
[java] view plaincopy
int[] mHashes;
Object[] mArray;
mHashes數組中儲存的是每一項的HashCode值，mArray中就是鍵值對，每兩個元素代表一個鍵值對，前面儲存key，後面的儲存value，
4.2 擴容
//如果容量不夠
s1 ize >= mHashes.length) {
final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1))
: (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);
if (DEBUG) Log.d(TAG, "put: grow from " + mHashes.length + " to " + n);
final int[] ohashes = mHashes;
final Object[] oarray = mArray;
//配置設定數組
allocArrays(n);
if (mHashes.length > 0) {
if (DEBUG) Log.d(TAG, "put: copy 0-" + mSize + " to 0");
//特别注意這，是copy，而不是new，效率提升
System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
System.arraycopy(oarray, 0, mArray, 0, oarray.length);
}
//釋放無用空間，收縮數組
freeArrays(ohashes, oarray, mSize);
}
ArrayMap用的是copy資料，是以效率相對要高。
4.3、ArrayMap提供了數組收縮的功能，在clear或remove後，會重新收縮數組，是否空間
4.4、ArrayMap采用二分法查找；