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采用二分法查找；