Ø map中的每個成員方法由一個關鍵字（key）和一個值（value）構成。map接口不直接繼承于collection接口，因為它包裝的是一組成對的“鍵-值”對象的集合，而且在map接口的集合中也不能有重複的key出現，因為每個鍵隻能與一個成員元素相對應。
Ø map接口的子接口以及主要實作類有：
子接口：bindings、concurrentmap、concurrentnavigablemap、messagecontext、logicmessagecontext、navigablemap、soapmessagemap、sortedmap
實作類：abstractmap, attributes,authprovider, concurrenthashmap, enummap,concurrentskiplistmap,hashmap, hashtable, identityhashmap, linkedhashmap, printerstatereasons,properties,provider, renderinghints,
simplebindings, tabulardatasupport,treemap,uidefaults,weakhashmap
map接口中定義的方法清單：
Ø map中定義的方法說明：
在map接口中定義的通用方法并不是很多。
a) 添加和删除map中的某個元素
• put(k, v) ： 将給定的“鍵-值”對放入到給定的map當中
• putall(map<? extends k, ? extends v) : 将指定的map中的“鍵-值”對放入到給定的map當中
• remove(object key) : 從該集合中移除指定的對象，并傳回對應的value
• clear() : 清空map中的所有對象
b) 查詢與map有關的資料
• int size() : 傳回此map中“鍵-值”對的個數
• boolean isempty() : 判斷此map中“鍵-值”對的個數是否為0
• boolean containskey(object key) : 測試此map中是否有該key
• boolean containsvalue(object value) : 測試此map中是否包含該value
• v get(object key) : 通過指定的key查詢map中對應的value
• collection<object value> values() : 取得map中所有的value
• set<object key> keyset() : 取得目前map中key的集合
• set<entry<k, v>> entryset() : 取得目前map中entry的集合
hashmap實作了map、clonemap、serializable三個接口，并且繼承自abstractmap類。
hashmap基于hash數組實作，若key的hash值相同則使用連結清單方式進行儲存，詳見hashset中的說明。我引用網上一個名詞叫“連結清單散列”來形容這樣的資料結構。
建立一個hashmap時會初始化一個大小為16，負載因子為0.75的空的hashmap。
<span style="font-size:10px;">1. /**
2. * the table, resized as necessary. length must always be a power of two.
3. */
4. transient entry[] table; </span>
那麼entry到底是怎麼實作的呢？
1. static class entry<k,v> implements map.entry<k,v> {
2. final k key;
3. v value;
4. entry<k,v> next;
5. final int hash;
6. ......
上面代碼其實告訴我們entry是一個結點，它持有下一個元素的引用，這樣就構成了一個連結清單。
那麼，整體上來說hashmap底層就是使用這樣一個資料結構來實作的。
我們提到使用hash，但是hash值如何與元素的存儲建立關系呢？（hash算法）
在資料結構課中我們學習過hash的簡單算法，就是給你一個hash因子，通過對該元素的hashcode簡單的求餘，來實作對其快速的定位和索引。
在hashmap中有這樣的代碼：
1. /**
2. * returns index for hash code h.
3. */
4. static int indexfor(int h, int length) {
5. return h & (length-1);
6. }
這個方法在hashmap中非常重要，凡是與查詢、添加、删除有關的方法中都有調用該方法，為什麼這麼短的一個代碼使用率這麼高？根據代碼注釋我們知道，這個方法是根據hashcode及目前table的長度（數組的長度，不是map的size）得到該元素應該存放的位置，或者在table中的索引。
現在我們需要看一下當資料量已經超過初始定義的負載因子時，hashmap如何處理？
在hashmap中當資料量很多時，并且已經達到了負載限度時，會重新做一次哈希，也就是說會再散列。調用的方法為resize()，并且java預設傳入的參數為2*table.length。先看一下jdk源碼：
1. /**
2. * rehashes the contents of this map into a new array with a
3. * larger capacity. this method is called automatically when the
4. * number of keys in this map reaches its threshold.
5. *
6. * if current capacity is maximum_capacity, this method does not
7. * resize the map, but sets threshold to integer.max_value.
8. * this has the effect of preventing future calls.
9. *
10. * @param newcapacity the new capacity, must be a power of two;
11. * must be greater than current capacity unless current
12. * capacity is maximum_capacity (in which case value
13. * is irrelevant).
14. */
15. void resize(int newcapacity) {
16. entry[] oldtable = table;
17. int oldcapacity = oldtable.length;
18. if (oldcapacity == maximum_capacity) {
19. threshold = integer.max_value;
20. return;
21. }
22.
23. entry[] newtable = new entry[newcapacity];
24. transfer(newtable);
25. table = newtable;
26. threshold = (int)(newcapacity * loadfactor);
27. }
28.
29. /**
30. * transfers all entries from current table to newtable.
31. */
32. void transfer(entry[] newtable) {
33. entry[] src = table;
34. int newcapacity = newtable.length;
35. for (int j = 0; j < src.length; j++) {
36. entry<k,v> e = src[j];
37. if (e != null) {
38. src[j] = null;
39. do {
40. entry<k,v> next = e.next;
41. int i = indexfor(e.hash, newcapacity);
42. e.next = newtable[i];
43. newtable[i] = e;
44. e = next;
45. } while (e != null);
46. }
47. }
48. }
看到這裡我們會發現resize（再哈希）的工作量是不是很大啊。再哈希是重建立一個指定容量的數組，然後将每個元素重新計算它要放的位置，這個工作量确實是很大的。
這裡就産生了一個很重要的問題，那就是怎麼讓哈希表的分布比較均勻，也就是說怎麼讓它即不會成為一個單連結清單（極限情況，每個key的hash值都集中到了一起），又不會使hash空間過大（導緻記憶體浪費）？
上面兩個問題一個是解決了怎麼計算hash值快速存取，一個是怎麼實作再哈希，何時需要再哈希。快速存取的前提是元素分布均勻，不至于集中到一點，再哈希是元素過于零散，導緻不斷的重新建構表。
那麼在第一個問題中我們看到了這樣一個代碼return h & (length-1);在第二個問題中我們說過内部調用傳入的值為2*table.length;并且預設情況下hashmap的大小為一個16的數字，除了預設構造提供大小為16的空間外，如果我們使用
public hashmap(int initialcapacity,float loadfactor)
上面的構造方法，我們會發現這樣的代碼：
1. // find a power of 2 >= initialcapacity
2. int capacity = 1;
3. while (capacity < initialcapacity)
4. capacity <<= 1;
5. ……
6. table = new entry[capacity];
也就是說當我們傳入1000時，它并沒有給我們構造一個容量為1000的哈希表，而是建構了一個容量為1024大小的哈希表。
從整體上我們發現一個問題，那就是無論什麼情況hashmap中哈希表的容量總是2的n次方的一個數。并且有這樣一個公式：
當length=2^n時，hashcode& (length-1) == hashcode % length
也就是這一點驗證了第一個問題，hash索引值的計算方法其實就是對哈希因子求餘。隻有大小為2的n次方時，那樣的計算才成立，是以hashmap為我們維護了一個這樣大小的一個哈希表。（位運算速度比取模運算快的多）
c) hashmap的使用方法：
我在很多代碼中都用到了hashmap，原因是首先它符合存儲關聯資料的要求，其次它的存取速度快，這是一個選擇的問題。
比較重要的是hashmap的周遊方法,keyset,entryset。
1. hashmap采用數組方式存儲key，value構成的entry對象，無容量限制。
2. hashmap基于key hash尋找entry對象存放到數組的位置，對于hash沖突采用連結清單的方式來解決。
3. hashmap在插入元素時可能要擴大數組的容量，擴大容量時對所有的資料要重新計算哈希和存放到新數組中。當元素個數size大于threshold擴容threshold = (int)(newcapacity* loadfactor);
4. hashmap保證數組的大小為2的指數大小。
5. hashmap非線程安全。
1. hashmap從java1.2後開始引進。hashtable從java1.0開始引入。hashtable一開始基于繼承陳舊的抽象類dictionary實作,後面也實作了map接口。hashmap基于map接口實作。
2. hashmap允許存放key為null，value為null。對于key為null時，hashmap首先擷取entry數組中的第一個entry對象，并基于entry對象的next周遊連結清單，當找到其中entry對象的key屬性為null時，更新其value值。如果沒有key屬性為null的entry，則調用addentry(int hash, k key, v value,
int bucketindex)，參數為0,null,value,0，增加一個entry對象，增加時先擷取目前數組的第一個entry對象，記為e，然後建立一個key為null，value為傳入值得得entry對象，next為之前擷取的e。數組的第一個entry對象連結清單，賦為新建立的entry對象。由此，addentry連結清單倒序插入元素的。hashtable不允許key為null或value為null，否則會抛出nullpointerexception。這從put方法的源碼中很容易看出來，置于為什麼真麼限制，不明白？
3. hashmap是非線程安全；hashtable是線程安全的，其方法包含synchronized關鍵字實作線程安全。
4. hashmap的計算hash值方法如下：首先對key取其hashcode,然後通過如下計算：
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h>>> 4);
最後取index時：return h &(length-1);
hashtable計算hash值，直接去key的hashcode值，如下：
int hash =key.hashcode();
取index時：int index = (hash& 0x7fffffff) % tab.length;
5. hashmap和hashtable預設構造時，預設容量值不同。
hashmap預設數組大小為16，加載因子為0.75,重新hash門檻值為12.
hashtable預設數組大小為11,加載因子為0.75，重新hash門檻值為8.
6. hashmap和hashtable的數組擴容方式不同。
hashmap中的數組容量大小始終保證為2的指數。重新hash,擴充容量方式為，目前容量大小*2.
hashtable擴充容量方式為：int newcapacity = oldcapacity * 2 + 1;
7. 一些成員方法不同。
hashtable包含一些舊的方法，如contains方法。
面試中常會碰到。
linkedhashmap繼承自hashmap并且實作了map接口。和hashmap一樣，linkedhashmap允許key和value均為null。
于該資料結構和hashmap一樣使用到hash算法，是以它不能保證映射的順序，尤其是不能保證順序持久不變（再哈希）。
如果你想在多線程中使用，那麼需要使用collections.synchronizedmap方法進行外部同步。
linkedhashmap與hashmap的不同之處在于，linkedhashmap維護着運作于所有條目的雙向連結清單，此連結清單可以是插入順序或者通路順序。
對于linkedhashmap而言，它繼承與hashmap、底層使用哈希表與雙向連結清單來儲存所有元素。其基本操作與父類hashmap相似，它通過重寫父類相關的方法，來實作自己的連結清單特性。下面我們來分析linkedhashmap的源代碼：
linkedhashmap采用的hash算法和hashmap相同，但是它重新定義了數組中儲存的元素entry，該entry除了儲存目前對象的引用外，還儲存了其上一個元素before和下一個元素after的引用，進而在哈希表的基礎上又構成了雙向連結清單。看源代碼：
java代碼
1. /**
2. * 雙向連結清單的表頭元素。
3. */
4. private transient entry<k,v> header;
5.
6. /**
7. * linkedhashmap的entry元素。
8. * 繼承hashmap的entry元素，又儲存了其上一個元素before和下一個元素after的引用。
9. */
10.private static class entry<k,v> extends hashmap.entry<k,v> {
11. entry<k,v> before, after;
12. ……
13.}
通過源代碼可以看出，在linkedhashmap的構造方法中，實際調用了父類hashmap的相關構造方法來構造一個底層存放的table數組。如：
1. public linkedhashmap(int initialcapacity, float loadfactor) {
2. super(initialcapacity, loadfactor);
3. accessorder = false;
4. }
hashmap中的相關構造方法：
1. public hashmap(int initialcapacity, float loadfactor) {
2. if (initialcapacity < 0)
3. throw new illegalargumentexception("illegal initial capacity: " +
4. initialcapacity);
5. if (initialcapacity > maximum_capacity)
6. initialcapacity = maximum_capacity;
7. if (loadfactor <= 0 || float.isnan(loadfactor))
8. throw new illegalargumentexception("illegal load factor: " +
9. loadfactor);
10.
11. // find a power of 2 >= initialcapacity
12. int capacity = 1;
13. while (capacity < initialcapacity)
14. capacity <<= 1;
15.
16. this.loadfactor = loadfactor;
17. threshold = (int)(capacity * loadfactor);
18. table = new entry[capacity];
19. init();
20.}
我們已經知道linkedhashmap的entry元素繼承hashmap的entry，提供了雙向連結清單的功能。在上述hashmap的構造器
中，最後會調用init()方法，進行相關的初始化，這個方法在hashmap的實作中并無意義，隻是提供給子類實作相關的初始化調用。
linkedhashmap重寫了init()方法，在調用父類的構造方法完成構造後，進一步實作了對其元素entry的初始化操作。
1. void init() {
2. header = new entry<k,v>(-1, null, null, null);
3. header.before = header.after = header;
linkedhashmap并未重寫父類hashmap的put方法，而是重寫了父類hashmap的put方法調用的子方法void addentry(int hash, kkey, v value, int bucketindex) 和voidcreateentry(int hash, k key, v value, int bucketindex)，提供了自己特有的雙向連結清單的實作。
1. void addentry(int hash, k key, v value, int bucketindex) {
2. // 調用create方法，将新元素以雙向連結清單的的形式加入到映射中。
3. createentry(hash, key, value, bucketindex);
4.
5. // 删除最近最少使用元素的政策定義
6. entry<k,v> eldest = header.after;
7. if (removeeldestentry(eldest)) {
8. removeentryforkey(eldest.key);
9. } else {
10. if (size >= threshold)
11. resize(2 * table.length);
12. }
1. void createentry(int hash, k key, v value, int bucketindex) {
2. hashmap.entry<k,v> old = table[bucketindex];
3. entry<k,v> e = new entry<k,v>(hash, key, value, old);
4. table[bucketindex] = e;
5. // 調用元素的addbrefore方法，将元素加入到哈希、雙向連結清單。
6. e.addbefore(header);
7. size++;
8. }
1. private void addbefore(entry<k,v> existingentry) {
2. after = existingentry;
3. before = existingentry.before;
4. before.after = this;
5. after.before = this;
6. }
linkedhashmap重寫了父類hashmap的get方法，實際在調用父類getentry()方法取得查找的元素後，再判斷當排序模式accessorder為true時，記錄通路順序，将最新通路的元素添加到雙向連結清單的表頭，并從原來的位置删除。由于的連結清單的增加、删除操作是常量級的，故并不會帶來性能的損失。
1. public v get(object key) {
2. // 調用父類hashmap的getentry()方法，取得要查找的元素。
3. entry<k,v> e = (entry<k,v>)getentry(key);
4. if (e == null)
5. return null;
6. // 記錄通路順序。
7. e.recordaccess(this);
8. return e.value;
9. }
1. void recordaccess(hashmap<k,v> m) {
2. linkedhashmap<k,v> lm = (linkedhashmap<k,v>)m;
3. // 如果定義了linkedhashmap的疊代順序為通路順序，
4. // 則删除以前位置上的元素，并将最新通路的元素添加到連結清單表頭。
5. if (lm.accessorder) {
6. lm.modcount++;
7. remove();
8. addbefore(lm.header);
9. }
10.}
linkedhashmap定義了排序模式accessorder，該屬性為boolean型變量，對于通路順序，為true；對于插入順序，則為false。
1. private final boolean accessorder;
一般情況下，不必指定排序模式，其疊代順序即為預設為插入順序。看linkedhashmap的構造方法，如：
1. public linkedhashmap(int initialcapacity,
2. float loadfactor,
3. boolean accessorder) {
4. super(initialcapacity, loadfactor);
5. this.accessorder = accessorder;
該哈希映射的疊代順序就是最後通路其條目的順序，這種映射很适合建構lru緩存。linkedhashmap提供了removeeldestentry(map.entry<k,v>eldest)方法，在将新條目插入到映射後，put和 putall将調用此方法。該方法可以提供在每次添加新條目時移除最舊條目的實作程式，預設傳回false，這樣，此映射的行為将類似于正常映射，即永遠不能移除最舊的元素。
1. protected boolean removeeldestentry(map.entry<k,v> eldest) {
2. return false;
3. }
此方法通常不以任何方式修改映射，相反允許映射在其傳回值的指引下進行自我修改。如果用此映射建構lru緩存，則非常友善，它允許映射通過删除舊條目來減少記憶體損耗。
例如：重寫此方法，維持此映射隻儲存100個條目的穩定狀态，在每次添加新條目時删除最舊的條目。
1. private static final int max_entries = 100;
2. protected boolean removeeldestentry(map.entry eldest) {
3. return size() > max_entries;
1. linkedhashmap繼承于hashmap，此連結清單定義了疊代順序，該疊代順序可以是插入順序或者是通路順序（按從近期通路最少到近期通路最多的順序）。預設情況下按插入順序通路，當accessorder設定為true時，按最後通路順序周遊資料。
2. linkedhashmap非線程安全。
3. linkedhashmap适合做lru緩存。
treemap是一個支援排序的基于紅黑樹（red-black tree）的<code>navigablemap</code>實作，非線程安全。treemap繼承abstractmap,實作navigablemap，navigablemap接口繼承sortedmap接口。此實作為 containskey、get、put 和 remove 操作提供受保證的 log(n) 時間開銷。
sortedmap提供關于鍵的總體排序的map。該映射是根據其鍵的自然順序進行排序的，或者根據通常在建立有序映射時提供的 comparator 進行排序。對有序映射的 collection 視圖（由 entryset、keyset 和 values 方法傳回）進行疊代時，此順序就會反映出來。
插入sortedmap的所有鍵都必須實作 comparable 接口（或者被指定的比較器接受）。另外，所有這些鍵都必須是可互相比較的：對有序映射中的任意兩個鍵 k1 和 k2 執行 k1.compareto(k2)（或 comparator.compare(k1, k2)）都不得抛出 classcastexception。試圖違反此限制将導緻違反規則的方法或者構造方法調用抛出 classcastexception。
所有通用sortedmap實作類都應該提供 4 個“标準”構造方法：
1) void（無參數）構造方法，它建立一個空的有序映射，按照鍵的自然順序（實作comparable接口，方法compareto為自然比較方法，按此方法比較大小排序）進行排序。 2) 帶有一個 comparator 類型參數的構造方法，它建立一個空的有序映射，根據指定的比較器進行排序。
3) 帶有一個 map 類型參數的構造方法，它建立一個新的有序映射，其鍵-值映射關系與參數相同，按照鍵的自然順序進行排序。
4) 帶有一個 sortedmap 類型參數的構造方法，它建立一個新的有序映射，其鍵-值映射關系和排序方法與輸入的有序映射相同。無法保證強制實施此建議，因為接口不能包含構造方法。
sortedmap新增了一些成員方法，如下圖所示：
navigablemap<k,v>接口，擴充自 sortedmap，具有了針對給定搜尋目标傳回最接近比對項的導航方法。方法 lowerentry、floorentry、ceilingentry 和 higherentry 分别傳回與小于、小于等于、大于等于、大于給定鍵的鍵關聯的 map.entry 對象，如果不存在這樣的鍵，則傳回 null。類似地，方法 lowerkey、floorkey、ceilingkey 和 higherkey 隻傳回關聯的鍵。所有這些方法是為查找條目而不是周遊條目而設計的。
将comparator屬性指派為null。如果要控制treemap中元素的存儲順序，應使用帶comparator參數的構造器。
先判斷root是否為null，如果為null，則建立一個新的entry對象，并指派給root屬性。否則，首先判斷是否傳入了compatator實作，如果是，則基于紅黑樹的方式周遊，直到為樹節點null，使用傳入的comparator比較key的大小，如果找到相等的key則更新其值，若沒有找到……，如果comparator為null，則判斷key是否為null，如果是null，抛出nullpointerexception，對于key不是null時，取key對于的comparator進行紅黑樹的周遊和比較，與上述類似。
如果沒有找到相同的key，則建立一個新的entry對象，并将其parent設定為上面所尋找到的元素，并根據和parent key比較的情況設定parent的left和right屬性。最後對紅黑樹進行調整。
concurrenthashmap是線程安全的hashmap實作。支援擷取，查找時完全并發和更新時可調整并發的哈希表。擷取操作（包括 get）通常不會受阻塞。并發場景中(多個線程的情況下) concurrenthashmap比hashmap優秀很多。
![Java String.format方法的簡單使用[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)