類的繼承關系
其中，Map接口中規定了map類的常用方法。比如
get(Object): V
，
put(K, V): V
，
isEmpty(): boolean
，
size(): int
，
remove(Objec): V
等。
Cloneable
與
Serializable
是辨別接口。
類的成員變量
/**
* 預設的初始容量（數組長度），必須是2的幂。
*/
static final int DEFAULT_INITIAL_CAPACITY = << ; // aka 16
/**
* 最大的容量， 用來修正如果有更大的值被設定。必須是2的幂，而且小于等于1<<30.
*/
static final int MAXIMUM_CAPACITY = << ;
/**
* 預設的填充因子，如果目前size大于目前容量（數組長度）乘以填充因子就需要擴容，擴為原來容量的兩倍。
*/
static final float DEFAULT_LOAD_FACTOR = f;
/**
* 當bin中的數量大于此值的時候，就要将list轉成紅黑樹。
*/
static final int TREEIFY_THRESHOLD = ;
/**
* 如果經過resize或者元素被remove，而使得一個bin中的元素數量少于這個值之後就應該紅黑樹轉成list了。
*/
static final int UNTREEIFY_THRESHOLD = ;
/**樹的最小的容量，至少是 4 × TREEIFY_THRESHOLD = 32 然後為了避免(resizing 和 treeification thresholds) 設定成64
*/
static final int MIN_TREEIFY_CAPACITY = ;
/**
* 哈希數組，總是2的幂。
*/
transient Node<K,V>[] table;
/**
* 存放具體元素的集。
*/
transient Set<Map.Entry<K,V>> entrySet;
/**
* 在整個map中存數的key-value對的數目。
*/
transient int size;
/**
* 整個hashmap進行結構調整的次數。用來檢測并發修改異常（ConcurrentModificationException）。
*/
transient int modCount;
/**
* 當size達到這個值時将要被resize。(threshold = capacity * load factor)
*/
int threshold;
/**
* 哈希數組的填充因子。
*/
final float loadFactor;
類的構造函數
public HashMap(int initialCapacity, float loadFactor) {
//初始容量不能小于零
if (initialCapacity < )
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//初始容量不能大于最大容量
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//填充因子不能小于等于零或者非數字
if (loadFactor <= || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
//進行初始化指派
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
其中
static final int tableSizeFor(int cap)
方法傳回大于給定cap的最小2次幂的數值。
static final int tableSizeFor(int cap) {
int n = cap - ;
n |= n >>> ;
n |= n >>> ;
n |= n >>> ;
n |= n >>> ;
n |= n >>> ;
return (n < ) ? : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + ;
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
其中
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict)
函數就是将m中的每個元素放入現在的hashmap中。
hashmap實作原理圖
圖檔來源：http://www.cnblogs.com/leesf456/p/5242233.html
重要的方法
static final int hash(Object key)
static final int hash(Object key)
注意，hashmap的hash值是由此方法計算的。而hashtable的hash值直接使用key.hashCode()。
static final int hash(Object key) {
int h;
return (key == null) ? : (h = key.hashCode()) ^ (h >>> );
}
public V put(K key, V value)
public V put(K key, V value)
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
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為空指針或者table長度為零，則resize擴容。
if ((tab = table) == null || (n = tab.length) == )
n = (tab = resize()).length;
//如果數組中該哈希位為空，也就是該bin中還沒有元素，則生成新節點放入該位置。此時還是在數組中。
//注意使用 (n - 1) & hash 來進行散列避免使用取餘(%)的開銷。
if ((p = tab[i = (n - ) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//若數組中該哈希位已經有元素。
Node<K,V> e; K k;
//如果将插入的key的哈希值和該位置的key的哈希值相等，并且key也相等。（相當于插入重複元素了）
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//用e來記錄該節點
e = p;
//如果該節點是樹節點的類型
else if (p instanceof TreeNode)
//放入樹中
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//不然，在連結清單的最末尾插入該節點
for (int binCount = ; ; ++binCount) {
//此時達到連結清單最末尾
if ((e = p.next) == null) {
//生成新的節點插到連結清單最末尾
p.next = newNode(hash, key, value, null);
//插完之後如果該bin中的節點數過大，則應該将連結清單轉成樹形結構
if (binCount >= TREEIFY_THRESHOLD - ) // -1 for 1st
treeifyBin(tab, hash);
//put成功，跳出
break;
}
//如果在連結清單中找到了重複的key值
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//與循環剛開始的 e = p.next 配合來周遊連結清單
p = e;
}
}
//找到了重複的key
if (e != null) { // existing mapping for key
//儲存舊值
V oldValue = e.value;
//若非僅不存在則插入
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//讓LinkedHashMap回調
afterNodeAccess(e);
//傳回舊值
return oldValue;
}
}
//結構修改次數增加
++modCount;
//如果節點數過多，則擴容
if (++size > threshold)
resize();
//讓LinkedHashMap回調
afterNodeInsertion(evict);
return null;
}
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
//得到根節點
TreeNode<K,V> root = (parent != null) ? root() : this;
//周遊樹的節點
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
//待插入節點key的哈希值比目前key的哈希值小，方向為左子樹
if ((ph = p.hash) > h)
dir = -;
//大于目前，右子樹
else if (ph < h)
dir = ;
//找到重複的key，傳回目前節點
else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
return p;
//若hash值等于目前，而且調用compareComparables方法還是傳回相等
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == ) {
//還未搜尋過
if (!searched) {
TreeNode<K,V> q, ch;
//隻搜尋一次
searched = true;
//在根節點為ch的子樹中尋找key，找到則傳回
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q;
}
//方法用盡，隻能———比類名和System.identityHashCode值
dir = tieBreakOrder(k, pk);
}
TreeNode<K,V> xp = p;
//根據direction選擇左右子樹，找到葉子節點進行插入
if ((p = (dir <= ) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= )
xp.left = x;
else
xp.right = x;
xp.next = x;
//兼顧樹的指針與連結清單的指針
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
public V get(Object key)
public V get(Object key)
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//如果bin中的第一個節點不為空
if ((tab = table) != null && (n = tab.length) > &&
(first = tab[(n - ) & hash]) != null) {
//如果第一個key就已經是了，就傳回
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//不然，如果下一個節點非空
if ((e = first.next) != null) {
//如果是樹的節點類型，則在樹裡面找
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//否則周遊整個連結清單
do {
//找到則傳回
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
//待尋找節點hash值比目前節點key的hash值小
if ((ph = p.hash) > h)
//在左子樹中找
p = pl;
//若大，則在右子樹中找
else if (ph < h)
p = pr;
//若相等做進一步判斷
//如果就是目前key，則傳回目前節點
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
//若相等，還不是目前節點
//左子樹為空，隻能在右子樹中找
else if (pl == null)
p = pr;
//隻能在右子樹中找
else if (pr == null)
p = pl;
//當相等，還不是目前節點，而且目前節點左右子樹都不空
//若調用compareComparables方法能判斷出下一步的尋找方向
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != )
p = (dir < ) ? pl : pr;
//若還是不行的話，則在右子樹中找，找到傳回
else if ((q = pr.find(h, k, kc)) != null)
return q;
//上面所有步驟都不行的話，就讓無論如何都在左子樹中找吧
else
p = pl;
} while (p != null);
//沒轍了，傳回空
return null;
}
這麼重要怎能沒有resize呢？ final Node<K,V>[] resize()
final Node<K,V>[] resize()
final Node<K,V>[] resize() {
//儲存目前數組
Node<K,V>[] oldTab = table;
//儲存數組長度
int oldCap = (oldTab == null) ? : oldTab.length;
//儲存門檻值
int oldThr = threshold;
int newCap, newThr = ;
//如果以前數組有東西
if (oldCap > ) {
//之前的數組大于最大容量了，就不再擴容了
if (oldCap >= MAXIMUM_CAPACITY) {
//更改完門檻值之後就傳回
threshold = Integer.MAX_VALUE;
return oldTab;
}
//最一般的情況，新的數組長度為老數組長度的2倍
else if ((newCap = oldCap << ) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//門檻值也翻倍
newThr = oldThr << ; // double threshold
}
//如果以前數組裡沒東西，但是以前門檻值是被指派過的
else if (oldThr > ) // initial capacity was placed in threshold
//則初始容量被指派為門檻值
newCap = oldThr;
//如果數組也未分貝，門檻值也未曾指派
//使用預設值（如使用HashMap()構造函數，之後再插入一個元素會調用resize函數，會進入這一步）
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//新門檻值為零
if (newThr == ) {
//門檻值為 capacity × loadFactor
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
//為數組申請空間
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//如果之前數組初始化過
if (oldTab != null) {
//周遊數組
for (int j = ; j < oldCap; ++j) {
Node<K,V> e;
//目前下标的元素不為空
if ((e = oldTab[j]) != null) {
//置空
oldTab[j] = null;
//就剩這一個節點
if (e.next == null)
newTab[e.hash & (newCap - )] = e;
//如果目前節點是樹節點類型
else if (e instanceof TreeNode)
//将樹拆分
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//連結清單類型
else { // preserve order
//lo == low, hi == high。由于數組翻倍了，相當于低位是老的數組，高位是新的一半。
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
//将同一bin中的元素按照hash值擴容之後新容量的高位的末位是否為0來判斷是否分割，完成rehash
if ((e.hash & oldCap) == ) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//低位
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//高位（新數組高一半的位置）
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
//傳回新數組
return newTab;
}
關于上面所說的“高位”和“低位”
圖檔來源同上。
References
JDK1.8源碼分析之HashMap（一）