1?Map
Map 定義了鍵值存儲的數(shù)據(jù)操作的接口葡公， 主要用于鍵值的存儲饺鹃，使用鍵可以得到值莫秆，并且不允許重復(fù)的鍵，值可以重復(fù)悔详，可以起到數(shù)據(jù)的快速獲取的目的镊屎。Java 1.5 后有了 concurrent 包，因此處理 java.utils 里面有 Map 的實(shí)現(xiàn)外茄螃，concurrent 包中也增加了同步 Map 的實(shí)現(xiàn)缝驳。
1.1?java.util 中的 Map 實(shí)現(xiàn)
1.1.1?HashMap
1. HashMap 繼承自AbstractMap, 實(shí)現(xiàn)了 Map、Serializable, Cloneable 接口归苍。
2. HashMap是單向鏈表數(shù)組的存儲結(jié)構(gòu)(拉鏈法)用狱，根據(jù) Key 的 HashCode 值運(yùn)算后作為數(shù)組的 index 存儲數(shù)據(jù)，根據(jù) key 可以直接獲取它的值拼弃，具有很快的訪問速度夏伊，遍歷時(shí)，取得數(shù)據(jù)的順序時(shí)完全隨機(jī)的吻氧。
3. HashMap 只允許一條記錄的鍵為 Null溺忧；
4. HashMap 不支持多線程的同步咏连，即任意時(shí)刻可以有多個(gè)線程同時(shí)寫 HashMap，可能會導(dǎo)致數(shù)據(jù)的不一致砸狞。如果需要同步捻勉，可以使用 Collections 的 synchronizedMap 方法使 HashMap 具有同步的能力， 或者使用 ConcurrentHashMap刀森。
5. 不能使用 get() 方法返回 null值判斷是否包含是否包含該鍵，而應(yīng)該使用 constainsKey() 方法來判斷报账。
6. 默認(rèn)的長度為16研底， 擴(kuò)充是按照 2 的指數(shù)倍進(jìn)行擴(kuò)充，這一點(diǎn)可以看下 HashMap 的 resize() 方法透罢。
final Node[] resize() {
????Node[] oldTab = table;
????int oldCap = (oldTab == null) ? 0 : oldTab.length;
????int oldThr = threshold;
????int newCap, newThr = 0;
????if (oldCap > 0)
????{
????????if (oldCap >= MAXIMUM_CAPACITY) // 長度超過最大限制時(shí)不再擴(kuò)充
????????{
????????????threshold = Integer.MAX_VALUE;
????????????return oldTab;
????????} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
????????????// 原 size 擴(kuò)充一倍小于最大限制且舊的 size 大于等于默認(rèn)大小時(shí)榜晦，
????????????//設(shè)置新的大小原來 threshold 一倍, 那么 threshold 在使用無參構(gòu)造函數(shù)時(shí)是怎么設(shè)置值呢？在本函數(shù)中羽圃，繼續(xù)向下看
????????????newThr = oldThr << 1; // double threshold
????????} else if (oldThr > 0)
????????????// 默認(rèn) threshold 為 0, 默認(rèn)的初始化方法乾胶，第一次存放數(shù)據(jù)時(shí)該代碼不會執(zhí)行
????????????newCap = oldThr;
? ? ? ? ?else // zero initial threshold signifies using defaults
????????{
????????????//此處為默認(rèn)的初始化的 Map ，第一次存放數(shù)據(jù)執(zhí)行的地方朽寞，為設(shè)置 size 為默認(rèn)的大小即：16识窿，
? ? ? ? ? ? //下次調(diào)整大小的為默認(rèn)的 factor (0.75) * 16 。
????????????newCap = DEFAULT_INITIAL_CAPACITY;
????????????newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
????????????}
? ? ?if (newThr == 0)
????{
????????????float ft = (float)newCap * loadFactor;
????????????newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
? ? ?}
????????threshold = newThr;
????????// 脑融。喻频。。肘迎。甥温。。妓布。姻蚓。
????????return newTab;
}
7. 計(jì)算 Key 的 hash() 值
static final int hash(Objectkey)
?{
????int h;
?????return(key ==null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
8. hashMap 實(shí)際存儲的是一個(gè)單項(xiàng)鏈表的數(shù)組；
9. 新增元素時(shí)匣沼，key 為 null 的值直接放到數(shù)組的首位狰挡，否則使用 hash()計(jì)算的值，與當(dāng)前的存儲數(shù)組的長度length-1 后有 key 的 hash 做 按位與(&)的操作或許下標(biāo)肛著，如果該 index 下已經(jīng)存在項(xiàng)圆兵，則創(chuàng)建新的 node，并做存儲的鏈表的開始位置枢贿，將 next 指向想一個(gè)元素殉农，否則，存儲新的節(jié)點(diǎn)局荚，下一個(gè)元素為 null超凳。
10. get() 元素時(shí), 使用 key 的 hashcode 運(yùn)算后獲取到 index愈污， 使用 index 獲取鏈表后進(jìn)行遍歷， 找到 key 對應(yīng)的值;
11. HashMap 提供了 keySet() 方法集獲取 key 的 set 集合轮傍， values() 方法獲取值的 collection, entrySet() 方法返回了 entry 的 set 集合暂雹。
1.1.2?Hashtable
1. Hashtable 繼承自 java.util.Dictionary 抽象類，實(shí)現(xiàn)了 Map创夜，Cloneable, Serializable 接口杭跪；
2. Hashtable 存儲結(jié)構(gòu)與 HashMap 一樣，使用的單向鏈表數(shù)組驰吓，但是涧尿，hastable 不允許 key 和 value 為 null；
3. key 的 hashCode 是使用的 key 本身的 hashkey;
4. Hashtable 是線程安全檬贰，它使用 synchronized 對public 的函數(shù)加鎖實(shí)現(xiàn)到了同步;
5. Hashtable 默認(rèn)大小是 11姑廉，這個(gè)在其默認(rèn)的構(gòu)造函數(shù)里面可以看到：
public Hashtable()
{
????this(11, 0.75f);
}
當(dāng)需要擴(kuò)充是，Hashtable 是擴(kuò)充為原來大小的 1 倍 + 1
protected void rehash()
{
????int oldCapacity= table.length;
????Entry[] oldMap= table;
????// overflow-conscious code
????int newCapacity= (oldCapacity << 1) + 1;
????if(newCapacity - MAX_ARRAY_SIZE > 0)
????????{
????????????????if(oldCapacity == MAX_ARRAY_SIZE)
????????????????// Keep running with MAX_ARRAY_SIZE buckets
????????????????return;? ? ? ?
????????newCapacity = MAX_ARRAY_SIZE;? ?
????????}?
????? .........
}
1.1.3?LinkedHashMap
LinkedHashMap 繼承自 HashMap翁涤，實(shí)現(xiàn)了 Map 接口桥言。LinedHashMap 存入元素默認(rèn)是按照插入的順序保存。遍歷LinkedHashMap時(shí)葵礼，先得到的記錄肯定是先插入的号阿。也可以在構(gòu)造時(shí)用帶參數(shù)，按照應(yīng)用次數(shù)排序章咧。在遍歷的時(shí)候會比HashMap慢倦西，不過有種情況例外，當(dāng)HashMap容量很大赁严，實(shí)際數(shù)據(jù)較少時(shí)扰柠，遍歷起來可能會比 LinkedHashMap慢，因?yàn)長inkedHashMap的遍歷速度只和實(shí)際數(shù)據(jù)有關(guān)疼约，和容量無關(guān)卤档，而HashMap的遍歷速度和他的容量有關(guān)。
LinkedHashMap 存儲元素 Entry 在 HashMap.Node 的基礎(chǔ)上增加了如下的before 和 after程剥，使之變成了雙向的鏈表結(jié)構(gòu)劝枣，源碼如下:
static class Entry?extends HashMap.Node?
{
????Entry?before,after;
????Entry(int hash,K key,V value,Node?next)
????{
????????super(hash, key, value, next);? ?
????}
}
1.1.4?TreeMap
1. TreeMap 繼承自 AbstractMap， 實(shí)現(xiàn)了 SortedMap 的接口织鲸。實(shí)現(xiàn)了NavigableMap接口舔腾，意味著它支持一系列的導(dǎo)航方法。比如返回有序的key集合搂擦。
2. 基于紅黑樹實(shí)現(xiàn)稳诚。TreeMap沒有調(diào)優(yōu)選項(xiàng)，因?yàn)樵摌淇偺幱谄胶鉅顟B(tài)瀑踢。
3. TreeMap 會按照 key 的存儲順序進(jìn)行排序扳还，默認(rèn)使用使用字典升序排列才避， 可以自己實(shí)現(xiàn) Comparator 來自定義排序規(guī)則。
TreeMap 提供構(gòu)造函數(shù)如下：
// 默認(rèn)構(gòu)造函數(shù)氨距。使用該構(gòu)造函數(shù)桑逝，TreeMap中的元素按照自然排序進(jìn)行排列。
TreeMap()
// 創(chuàng)建的TreeMap包含
Map TreeMap(Map copyFrom)
// 指定Tree的比較器
TreeMap(Comparator?comparator)
// 創(chuàng)建的TreeSet包含copyFrom
TreeMap(SortedMap copyFrom)
關(guān)于詳細(xì)的介紹俏让，大家可以去看這里?http://www.cnblogs.com/skywang12345/p/3310928.html?楞遏， 介紹的非常詳細(xì)，同時(shí)對紅黑樹也相應(yīng)的文章進(jìn)行介紹舆驶。
1.1.5?WeakHashMap
WeakHashMap 實(shí)現(xiàn)了 Map 接口橱健，繼承自 AbstractMap, 與 HashMap 的用法基本相同，不同的是它使用弱引用作為存儲內(nèi)部數(shù)據(jù)的方案沙廉，當(dāng)系統(tǒng)內(nèi)存不夠的時(shí)候，垃圾收集器會自動的清除沒有在其他任何地方被引用的鍵值對臼节。在使用 WeakHashMap 進(jìn)行大量數(shù)據(jù)的進(jìn)行緩存時(shí)撬陵，如果超過 JVM 的內(nèi)存大小，會先對引用的數(shù)據(jù)進(jìn)行 GC网缝，然后再存放新的數(shù)據(jù)巨税。可以看看在執(zhí)行 put(K k, V v) 方法時(shí)粉臊，會執(zhí)行 getTable 的方法
public V put(K key, V value)
{
????Object k = maskNull(key);
????int h = hash(k);
????Entry[] tab = getTable();
????int i = indexFor(h, tab.length);
????……
?return null;
}
而 getTable() 的方法會執(zhí)行 expungeStaleEntries()草添， 移除沒有引用的鍵值對。
private void expungeStaleEntries()
{
????for (Object x; (x = queue.poll()) != null; )
????{
????synchronized (queue)
????{
????????????@SuppressWarnings("unchecked")
????????????Entry e = (Entry) x;
????????int i = indexFor(e.hash, table.length);
????????Entry prev = table[i];
????????Entry p = prev;
????????while (p != null)
????????{
????????????????Entry next = p.next;
????????????????if (p == e)
????????????????{
????????????????????????if (prev == e)
????????????????????????????????table[i] = next;
????????????????????????else prev.next = next;
????????????????????????// Must not null out e.next;
????????????????????????// stale entries may be in use by a HashIterator
????????????????????????e.value = null; // Help GC
????????????????????????size--; break;
????????????????}
????????????????prev = p;
????????????????p = next;
????????????}
????????}
????}
}
這就是有人覺得使用 WeakHashMap 不靠譜的地方吧扼仲。
1.2?java.util.concurrent
concurrent 包是java1.5 后添加的远寸，包含許多線程安全、測試良好屠凶、高性能的并發(fā)構(gòu)建塊驰后。
1.2.1?ConcurrentHashMap
ConcurrentHashMap 與 HashMap 非常相似，
ConcurrentHashMap 在線程安全的基礎(chǔ)上提供了更好的寫并發(fā)能力矗愧。
繼承自 AbstractMap灶芝，實(shí)現(xiàn)了 ConcurrentMap 接口。
基本的操作與 HashMap 是一致的唉韭，一些關(guān)鍵的屬性增加了線程同步的控制夜涕。
1.2.2?ConcurrentSkipListMap
首先簡單的介紹下 SkipList 跳表，跳表也是使用的一種擴(kuò)展的單向鏈表的數(shù)據(jù)結(jié)構(gòu)属愤，普通的單向鏈表是一種線性結(jié)構(gòu)女器，前一個(gè)節(jié)點(diǎn)指向后一個(gè)節(jié)點(diǎn)，而跳表則是前一個(gè)節(jié)點(diǎn)可能執(zhí)行后一個(gè)和后續(xù)的其他節(jié)點(diǎn)春塌，以空間換時(shí)間晓避，提高了查找的效率簇捍。
ConcurrentSkipListMap 提供了一種線程安全的排序的映射表。內(nèi)部是SkipList（跳表）結(jié)構(gòu)實(shí)現(xiàn)俏拱，在理論上能夠 O(log(n)) 時(shí)間內(nèi)完成查找暑塑、插入、刪除等操作锅必。
2?參考資料
http://blog.csdn.net/io_field/article/details/53281884
http://www.importnew.com/22007.html
