聽說微信搜尋《Java魚仔》會變更強哦！
本文收錄于github和gitee ，裡面有我完整的Java系列文章，學習或面試都可以看看
（一）Map方法概述
首先先看一下官方對Map接口的解釋，《Java Platform SE 8》:
An object that maps keys to values. A map cannot contain duplicate keys; each key can map to at most one value.
Map是一個通過鍵值對儲存的對象，一個map隻能由一個key，但是一個key可以有多個value。
Map的使用很簡單：
1.1 Map的幾個常用方法
通過代碼展示一下Map中常用的方法：
public class MapTest {
public static void main(String[] args) {
Map map=new HashMap();
//添加 put(key,value)
map.put("a1",1);
map.put("a2",1);
map.put(null,1);
System.out.println(map);
//删除 remove(key)
map.remove("a2");
System.out.println(map);
//是否包含 key value
//containsKey(key) containsValue(value)
System.out.println(map.containsKey("a1"));
System.out.println(map.containsValue("1"));
//擷取資料 get(key)
System.out.println(map.get("a1"));
//擷取大小 size()
System.out.println(map.size());
//是否為空 isEmpty()
System.out.println(map.isEmpty());
//擷取所有的關系 entrySet()
System.out.println(map.entrySet());
//擷取所有的key keySet()
System.out.println(map.keySet());
//擷取所有的value values()
System.out.println(map.values());
}
} （二）HashMap的特點
HashMap底層是一個哈希表，以數組加連結清單的形式存儲值。HashMap具有以下特點：
1.HashMap允許key和value為空
2.HashMap是線程不安全的
3.HashMap的初始容量為16，負載因子大小為0.75
4.在jdk7.0中，底層是數組加連結清單；在jdk8.0中，底層是數組加連結清單加紅黑樹（這一點在後面會重點講一下）
（三）HashMap的源碼分析
通過代碼斷點的方法逐個添加元素，單步觀察代碼執行步驟，首先進入HashMap的構造方法：
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
} 該構造方法把負載因子設定為0.75，負載因子的意思是當存入的資料大于總容量的0.75倍時，就擴容。構造方法結束後進入put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
} put方法直接傳回putVal()方法，putVal方法的第一個參數是根據key計算的一個哈希值，可以看一下這個hash方法：通過hash運算和異或操作得到hash值并傳回
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
} 接下來就進入了比較重要的putVal方法：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//檢視此時table的容量（即哈希表數組部分的長度），如果為空（第一次進入），則進入resize()方法
//resize()是個初始化或擴容方法，初始化成16或擴容2倍
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//根據此時數組的長度n和計算的hash值算出索引
//計算出的索引一定在0~n-1之間
//如果該索引位置沒有元素，則直接将元素添加進入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//如果該索引位置存在元素，執行以下代碼塊
else {
Node<K,V> e; K k;
//如果該元素和要儲存的元素相同，則覆寫
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果不相同，并且是樹狀結構，則按樹狀結構的方式添加元素
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//如果是鍊狀結構，則按照連結清單的方式添加元素
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//判斷容量是否超過臨界值，如果超過了就2倍擴容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
} 源碼分析：
HashMap中維護了Node類型的數組table，當HashMap建立對象時，設定負載因子為0.75，table還是null。
當第一次添加元素時，将table的容量設定為16，臨界值設定為12
每次添加元素調用putVal方法：
1.将key的hash值和table容量-1進行與運算，得到索引值
2.判斷該存放位置上是否有元素，如若沒有元素則直接放上去；如果該索引位置已存在元素，則繼續判斷
3.如果該位置的元素和添加元素相等，則直接覆寫，如果不相等，則繼續判斷是連結清單結構還是樹狀結構，按照相對應的方式添加。
如果添加的數量大于臨界值，執行resize方法對容量雙倍擴容。并打亂順序重新排列。
（四）HashMap在JDK1.7和JDK1.8中的差別
前面一直提到樹狀結構和紅黑樹，這是HashMap在JDK1.7和JDK1.8之間最大的差別。數組+連結清單的結構下，如果一個索引後跟着的連結清單數量很多時，會很影響查找效率，是以在JDK1.8中，HashMap當滿足某種條件（連結清單長度大于8，table容量大于64）時，會将連結清單轉化為紅黑樹結構，提高效率。
截取一段源碼：當連結清單長度大于等于（TREEIFY_THRESHOLD - 1）時，這個值是7，進入treeifyBin方法。連結清單長度大于等于7，再加上數組上的一個元素，一共是8個元素。
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash); 進入treeifyBin方法：
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//如果進入treeifyBin但是table的容量小于64，則執行resize擴容并重新打亂
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
//連結清單長度大于8，table容量大于64，轉化成紅黑樹
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
} 如果進入treeifyBin但是table的容量小于64，則執行resize擴容并重新打亂。是以并非容量大于臨界容量才會擴容。
第二個差異是插入元素時的變化，JDK1.7中是用頭插法的方式插入元素，在JDK1.8中這個插入方式變成了尾插法。這個變化的原因是用頭插法插入元素存在連結清單循環的風險。當兩個線程同時put元素并且剛好觸發擴容，就會造成連結清單死循環。
JDK1.7和JDK1.8差別總結：
1.初始化對象時，JDK1.7直接初始化對象容量為16，JDK1.8僅僅初始化負載因子為0.75
2.table類型：JDK1.7是Entry（映射key和value），JDK1.8是Node類型（為了紅黑樹）
3.底層結構：JDK1.7數組+連結清單，JDK1.8數組+連結清單+紅黑樹（連結清單長度大于8，table容量大于64）
4.元素插入方式：JDK1.7 頭插法，JDK1.8尾插法
（四）HashMap和HashTable的對比
HashMap和HashTable的處境有點像Vector和ArrayList，HashTable現在很少使用，就用一個表格來總結它和HashMap的差別
| 底層結構 | 版本 | 線程安全（同步） | 允許null | |
|---|---|---|---|---|
| HashMap | 哈希表 | 1.2 | 不安全 | 允許鍵值為null |
| HashTable | 1.0 | 安全 | 不允許鍵值null |
（五）TreeMap的介紹
A Red-Black tree based NavigableMap implementation. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.
根據官方文檔的介紹，TreeMap底層是一個紅黑樹，map是根據keys進行自然排序或者定制排序。
自然排序和定制排序的用法和TreeSet類似。
使用自然排序：需要在類中繼承Comparable接口，并重寫compareTo方法。
public class Book implements Comparable{
private String name;
private float price;
public Book(String name, float price){
this.name=name;
this.price=price;
}
//.........
@Override
public int compareTo(Object o) {
Book book= (Book) o;
return Double.compare(book.price,this.price);
}
} TreeMap map=new TreeMap(new Comparator() {
@Override
public int compare(Object o1, Object o2) {
Book book1= (Book) o1;
Book book2= (Book) o2;
return Double.compare(book1.getPrice(),book2.getPrice());
}
}); ![Java小案例——随機數猜測随機數猜測[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)