HashMap的工作原理
1.前言
在探討HashMap源碼之前，先說一下HashCode，為什么呢？因為HashMap有一個特性是Key是唯一值，如何確定key的唯一性呢，這就用到了hash算法。在HashMap（jdk1.7）的put方法實現中首先利用了hash()生成key的hashCode，然后比較key的hashCode是否已經存在集合，如果不存在，就插入到集合，如果已存在，則返回null。
1.1 hashCode方法和equals方法比較
為什么用HashCode比較比用equals方法比較要快呢？我們要想比較hashCode與equals的性能，得先了解HashCode是什么。HashCode是jdk根據對象的地址或字符串或者數字利用hash算法計算出的int類型的數值。Java采用了哈希表的原理，將數據依照特定算法直接指定到一個地址上，這樣可以簡單的理解為hashCode方法返回的就是對象存儲位置的映像。因此HashCode能夠快速的定位對象所在的地址，并且根據Hash常規協定，如果兩個對象相等，則他們一定有相同的HashCode。而equals方法對比兩個對象實例是否相等時，對比的就是對象示例的ID（內存地址）是否是同一個對象實例；該方法是利用的等號（==）的判斷結果。所以HashCode的效率遠遠大于equals
但是HashCode并不保證唯一性，因此當對象的HashCode相同時，再利用equals方法來判斷兩個對象是否相同，就大大加快了對比的速度。
1.2 java對象比較方法總結
等號（==）：對比對象實例的內存地址來判斷是否是同一對象實例；也可以說是判斷對象實例是否物理相等。
equals()：當對象沒有重寫Object的equals方法時，equals方法判斷的是對象實例的ID，也就是內存地址，是否是同一對象實例；該方法就是使用等號（==）的判斷結果。Object類的源碼如下：
public boolean equals(Object obj) {
return (this == obj);
}
當對象所屬的類重寫equals方法時，要根據自身邏輯來判斷是否相等。
hashCode()：根據對象的地址或字符串或者數字等計算出對象實例的哈希碼。可以簡單的說，hashCode比較的是對象的內存地址。
1.3 為什么要hash算法
Hash算法一般也被稱為散列算法，通過散列算法將任意的值轉化成固定的長度輸出，該輸出就是散列值，這是一種壓縮映射，也就是，散列值的空間遠遠小于輸入的值空間。
簡單的說，hash算法的意義在于提供了一種快速存取數據的方法,它用一種算法建立鍵值與真實值之間的對應關系,(每一個真實值只能有一個鍵值,但是一個鍵值可以對應多個真實值),這樣可以快速在數組等里面存取數據。HashMap就是采用了Hash算法來實現快速存取數據。
注意：jdk1.8版本對HashMap改動很大，jdk1.7之前的版本，HashMap采用的是鏈表+位桶的方式，也就是我們經常說的散列表的方式，但是在jdk1.8版本中，HashMap采用的是位桶+鏈表/紅黑樹的方式，也是非線程安全的。當某個位桶的鏈表的長度到達某個閾值的時候，這個鏈表就轉化為紅黑樹。
2.HashMap（JDK1.6）簡介
2.1.HashMap是什么
HashMap基于哈希表的 Map 接口的實現。此實現提供所有可選的Map操作，并允許使用 null 值和 null 鍵。（除了非同步和允許使用 null 之外，HashMap 類與 Hashtable 大致相同。）此類不保證映射的順序，特別是它不保證該順序恒久不變。
HashMap的實例有兩個參數影響其性能： 初始容量 和 加載因子 。 容量是 哈希表 中桶的數量，初始容量只是哈希表在創建時的容量。加載因子是哈希表在其容量自動增加之前可以達到多滿的一種尺度。當哈希表中的條目數超出了加載因子與當前容量的乘積時，則要對該哈希表進行rehash操作（重建內部數據結構），從而哈希表將具有大約兩倍的桶數。
通常默認加載因子(.75)在時間和空間成本上尋求一種折衷。加載因子過高雖然減小了空間開銷，但是同時也增加了查詢成本。在設置初始容量時應該考慮到映射中所需的條目數及其加載因子，以便最大限度地減少rehash操作次數。如果初始容量大于最大條目數除以加載因子，則不會發生rehash操作。
如果很多映射關系要存儲到HashMap實例中，則相對于按需執行自動的rehash操作以增大表的容量來說，使用足夠大的初始化容量創建它將使得映射關系能夠更有效的存儲。
注意，此實現不是同步。如果多個線程同時訪問同一個HashMap，而其中至少一個線程從結構上修改了該映射（增刪映射關系），則它必須保持外部同步。這一般通過對自然封裝該映射的對象進行同步操作來完成。如果不存在這樣的對象，則應該使用Collections.synchronizedMap方法來“包裝”該映射。最好在創建時完成這一操作，防止對映射進行意外的非同步訪問，示例代碼如下：
private static Map<String, CbossHomeDuplicateConfigDataModule> cbossHomeDuplicateConfigMap = Collections.synchronizedMap(new HashMap<String, CbossHomeDuplicateConfigDataModule>()); //
這樣能夠面對并發的修改時，迭代器很快就完全失敗，就避免了在不確定的時間發生任意不確定行為的風險。
但是，雖然有Collections.synchronizedMap方法來規避風險，但是還是應該盡量避免在并發程序中使用HashMap.可以考慮使用current包下的ConcurrentHashMap。
2.2.HashTable是什么
很多時候HashMap與HashTable都糾纏到一起。特別是面試的時候就會HashMap和HashTable的區別。那么HashTable是什么？哈希表（Hashtable）又稱為“散置”，Hashtable是會根據索引鍵的哈希程序代碼組織成的索引鍵（Key）和值（Value）配對的集合。Hashtable 對象是由包含集合中元素的哈希桶（Bucket）所組成的。而Bucket是Hashtable內元素的虛擬子群組，可以讓大部分集合中的搜尋和獲取工作更容易、更快速。
2.3.HashMap和HashTable的區別
我們都知道HashMap和HashTable的主要區別就是：
- HashMap是非線程同步的，HashTable是線程同步的。
- HashMap允許null作為鍵或者值，HashTable不允許
- HashTable中有個一個contains方法，HashMap去掉了此方法
- 效率上來講，HashMap因為是非線程安全的，因此效率比HashTable高
從定義上看，hashTable繼承Dictionary，而HashMap繼承Abstract
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable
從實現上看，hashTable的put方法實現了同步，而hashMap沒有
hashMap的put、get方法源碼：
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}</code></pre>
hashTable的put()、get()方法源碼：
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
V old = e.value;
e.value = value;
return old;
}
}
modCount++;
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
rehash();
tab = table;
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
Entry<K,V> e = tab[index];
tab[index] = new Entry<K,V>(hash, key, value, e);
count++;
return null;
}
public synchronized V get(Object key) {
Entry tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return e.value;
}
}
return null;
}</code></pre>
從源碼中可以看出hashTable實現了synchronized，并不允許null作為鍵值。
2.4 HashMap的存儲結構
HashMap的數據結構是基于數組和鏈表的。數組和鏈表是數據結構的基本組成。但是這兩個都有很大的弊端：
- 數組的存取區間是連續的，占用內存嚴重，因此空間復雜度很大。但是數組的二分查找事件復雜度小為O(1);數組的特點是：尋址容易，插入和刪除困難
- 鏈表的存儲區間離散，占用內存比較松散，因此空間復雜度很小，單事件復雜度很大，達O（N）。鏈表的特點是：尋址困難，插入和刪除容易
鑒于此種情況，為尋求尋址容易且插入和刪除操作也都容易的數據結構。哈希表應運而生。哈希表的存儲結構：
由上圖可以看出哈希表是一個數組+鏈表的存儲結構。HashMap存儲結構文字解釋：
元素0 →[hashCode=1,Entry<K,V>]
元素1 →[hashCode=2,Entry<K,V>]
…
依次類推
2.5 HashMap的數據結構
java.lang.Object
? java.util.AbstractMap<K, V>
? java.util.HashMap<K, V>
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable { }</code></pre>
- HashMap繼承AbstractMap類，實現了Map接口（AbstractMap已經實現了Map接口，不明白為什么HashMap要再次實現Map接口）。
- Java的HashMap是通過“拉鏈法”實現的哈希表。包括table、size、threshold、loadFactor和modCount。其中table是一個Entry[]數組類型，而Entry實際上是一個單向鏈表。哈希表的“key-value鍵值對”都是存放在Entry數組中。size是HashMap的大小，它是HashMap保存的鍵值對的數量。threshold是HashMap的閾值，用于判斷是否需要調整HashMap的容量。threshold = “容量 * 加載因子”，當HashMap中存儲數據的數量達到threshold值時，就需要rehash，將HashMap容量擴展到原來的2倍。loadFactor就是加載因子。modCount用來實現fail-fast機制。
3.源碼解析HashMap
為了更了解HashMap的工作原理，下面對HashMap的源碼做出解析。
3.1.HashMap對HashCode碰撞的處理
Java中HashMap是利用“拉鏈法”處理HashCode的碰撞問題。在調用HashMap的put方法或get方法時，都會首先調用hashcode方法，去查找相關的key，當有沖突時，再調用equals方法。hashMap基于hasing原理，我們通過put和get方法存取對象。當我們將鍵值對傳遞給put方法時，他調用鍵對象的hashCode()方法來計算hashCode，然后找到bucket（哈希桶）位置來存儲對象。當獲取對象時，通過鍵對象的equals()方法找到正確的鍵值對，然后返回值對象。HashMap使用鏈表來解決碰撞問題，當碰撞發生了，對象將會存儲在鏈表的下一個節點中。hashMap在每個鏈表節點存儲鍵值對對象。當兩個不同的鍵卻有相同的hashCode時，他們會存儲在同一個bucket位置的鏈表中。鍵對象的equals()來找到鍵值對。HashMap的put和get方法源碼如下：
/**
* Returns the value to which the specified key is mapped,
* or if this map contains no mapping for the key.
*
* 獲取key對應的value
*/
public V get(Object key) {
if (key == null)
return getForNullKey();
//獲取key的hash值
int hash = hash(key.hashCode());
// 在“該hash值對應的鏈表”上查找“鍵值等于key”的元素
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}
/**
* Offloaded version of get() to look up null keys. Null keys map
* to index 0.
* 獲取key為null的鍵值對，HashMap將此鍵值對存儲到table[0]的位置
*/
private V getForNullKey() {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
/**
* Returns <tt>true</tt> if this map contains a mapping for the
* specified key.
*
* HashMap是否包含key
*/
public boolean containsKey(Object key) {
return getEntry(key) != null;
}
/**
* Returns the entry associated with the specified key in the
* HashMap.
* 返回鍵為key的鍵值對
*/
final Entry<K,V> getEntry(Object key) {
//先獲取哈希值。如果key為null，hash = 0；這是因為key為null的鍵值對存儲在table[0]的位置。
int hash = (key == null) ? 0 : hash(key.hashCode());
//在該哈希值對應的鏈表上查找鍵值與key相等的元素。
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* 將“key-value”添加到HashMap中，如果hashMap中包含了key，那么原來的值將會被新值取代
*/
public V put(K key, V value) {
//如果key是null，那么調用putForNullKey(),將該鍵值對添加到table[0]中
if (key == null)
return putForNullKey(value);
//如果key不為null，則計算key的哈希值，然后將其添加到哈希值對應的鏈表中
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//如果這個key對應的鍵值對已經存在，就用新的value代替老的value。
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}</code></pre>
從HashMap的put()和get方法實現中可以與拉鏈法解決hashCode沖突解決方法相互印證。并且從put方法中可以看出HashMap是使用Entry<K,V>來存儲數據。數據節點Entry的數據結構如下：
// Entry是單向鏈表。
// 它是 “HashMap鏈式存儲法”對應的鏈表。
// 它實現了Map.Entry 接口，即實現getKey(), getValue(), setValue(V value), equals(Object o), hashCode()這些函數
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
//指向下一個節點
Entry<K,V> next;
final int hash;
/**
* Creates new entry.
* 輸入參數包括"哈希值(h)", "鍵(k)", "值(v)", "下一節點(n)"
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
// 判斷兩個Entry是否相等
// 若兩個Entry的“key”和“value”都相等，則返回true。
// 否則，返回false
public final boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;
Object k1 = getKey();
Object k2 = e.getKey();
if (k1 == k2 || (k1 != null && k1.equals(k2))) {
Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
}
return false;
}
public final int hashCode() {
return (key==null ? 0 : key.hashCode()) ^
(value==null ? 0 : value.hashCode());
}
public final String toString() {
return getKey() + "=" + getValue();
}
/**
* This method is invoked whenever the value in an entry is
* overwritten by an invocation of put(k,v) for a key k that's already
* in the HashMap.
*/
void recordAccess(HashMap<K,V> m) {
}
/**
* This method is invoked whenever the entry is
* removed from the table.
*/
void recordRemoval(HashMap<K,V> m) {
}
}
從這段代碼中，我們可以看出Entry是一個單向鏈表，這也是我們為什么說HashMap是通過拉鏈法解決hash沖突的原因。Entry實現了Map.Entry接口。
3.2 HashMap的構造函數
HashMap共包括4個構造函數
// 默認構造函數。構造一個具有默認初始容量 (16) 和默認加載因子 (0.75) 的空 HashMap
public HashMap() {
// 設置“加載因子”
this.loadFactor = DEFAULT_LOAD_FACTOR;
// 設置“HashMap閾值”，當HashMap中存儲數據的數量達到threshold時，就需要將HashMap的容量加倍。
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
// 創建Entry數組，用來保存數據
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}
// 構造一個帶指定初始容量和加載因子的空 HashMap。
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
// HashMap的最大容量只能是MAXIMUM_CAPACITY
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
// 設置“加載因子”
this.loadFactor = loadFactor;
// 設置“HashMap閾值”，當HashMap中存儲數據的數量達到threshold時，就需要將HashMap的容量加倍。
threshold = (int)(capacity * loadFactor);
// 創建Entry數組，用來保存數據
table = new Entry[capacity];
init();
}
// 構造一個帶指定初始容量和默認加載因子 (0.75) 的空 HashMap。
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// 構造一個映射關系與指定 Map 相同的新 HashMap。
public HashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
// 將m中的全部元素逐個添加到HashMap中
putAllForCreate(m);
}
3.3 hashMap的主要方法
hashMap的主要方法
public int size():返回此映射中的鍵-值映射關系數
public void clear():從此映射中移除所有映射關系。此調用返回后，映射將為空。
public boolean containsValue ( Object value):如果此映射將一個或多個鍵映射到指定值，則返回 true。
public boolean containsKey ( Object key):如果此映射包含對于指定鍵的映射關系，則返回 true。
public V put ( K key, V value)：在此映射中關聯指定值與指定鍵。如果該映射以前包含了一個該鍵的映射關系，則舊值被替換。
public void putAll ( Map <? extends K ,? extends V > m)：將指定映射的所有映射關系復制到此映射中，這些映射關系將替換此映射目前針對指定映射中所有鍵的所有映射關系。
public V get ( Object key)：返回指定鍵所映射的值；如果對于該鍵來說，此映射不包含任何映射關系，則返回null。
public Set < K > keySet ()：返回此映射中所包含的鍵的 Set 視圖。它不支持 add 或 addAll 操作。
public Set < Map.Entry < K , V >> entrySet ()：返回此映射所包含的映射關系的 Set 視圖
public boolean isEmpty ()：如果此映射不包含鍵-值映射關系，則返回 true。
put方法詳解：（put方法源碼，請見3.1）。put()的作用是對外提供接口，讓hashMap對象可以通過put()將“key-value”添加到HashMap中。由源碼可以看出若要添加到HashMap中的鍵值對對應的key已經存在HashMap中，則找到該鍵值對；然后新的value取代舊的value，并退出！若要添加到HashMap中的鍵值對對應的key不在HashMap中，則將其添加到該哈希值對應的鏈表中，并調用addEntry()。addEntry的作用是新增Entry。將“key-value”插入指定位置，bucketIndex是位置索引。addEntry的代碼如下：
// 新增Entry。將“key-value”插入指定位置，bucketIndex是位置索引。
void addEntry(int hash, K key, V value, int bucketIndex) {
// 保存“bucketIndex”位置的值到“e”中
Entry<K,V> e = table[bucketIndex];
// 設置“bucketIndex”位置的元素為“新Entry”，
// 設置“e”為“新Entry的下一個節點”
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
// 若HashMap的實際大小 不小于 “閾值”，則調整HashMap的大小
if (size++ >= threshold)
resize(2 * table.length);
}
說到addEntry，就不得不提一下createEntry。createEntry代碼如下：
// 創建Entry。將“key-value”插入指定位置，bucketIndex是位置索引。
// 它和addEntry的區別是：
// (01) addEntry()一般用在 新增Entry可能導致“HashMap的實際容量”超過“閾值”的情況下。
// 例如，我們新建一個HashMap，然后不斷通過put()向HashMap中添加元素；
// put()是通過addEntry()新增Entry的。
// 在這種情況下，我們不知道何時“HashMap的實際容量”會超過“閾值”；
// 因此，需要調用addEntry()
// (02) createEntry() 一般用在 新增Entry不會導致“HashMap的實際容量”超過“閾值”的情況下。
// 例如，我們調用HashMap“帶有Map”的構造函數，它繪將Map的全部元素添加到HashMap中；
// 但在添加之前，我們已經計算好“HashMap的容量和閾值”。也就是，可以確定“即使將Map中
// 的全部元素添加到HashMap中，都不會超過HashMap的閾值”。
// 此時，調用createEntry()即可。
void createEntry(int hash, K key, V value, int bucketIndex) {
// 保存“bucketIndex”位置的值到“e”中
Entry<K,V> e = table[bucketIndex];
// 設置“bucketIndex”位置的元素為“新Entry”，
// 設置“e”為“新Entry的下一個節點”
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
size++;
}
寫不動了……其他的方法，你們自己根據源碼和JDKAPI文檔研究下吧
3.4 hashMap的遍歷方式
3.4.1 遍歷hashMap的鍵值對
【1】根據entrySet()獲取HashMap的鍵值對的Set集合
【2】通過Iterator迭代器遍歷Set集合
3.4.2 遍歷HashMap的鍵
【1】根據keySet()獲取HashMap的鍵的Set集合
【2】通過Iterator迭代器遍歷Set集合
3.4.3遍歷HashMap的值
【1】根據value()獲取HashMap的“值”集合
【2】通過Iterator迭代器遍歷集合
4 關于hashMap的其他問題
-
為什么String, Interger這樣的wrapper類適合作為鍵？ HashMap的鍵盡量使用String、Integer這樣的wrapper類。因為String是不可變的，也是final的，而且已經重寫了equals()和hashCode()方法了。其他的wrapper類也有這個特點。不可變性是必要的，因為為了要計算hashCode()，就要防止鍵值改變，如果鍵值在放入時和獲取時返回不同的hashcode的話，那么就不能從HashMap中找到你想要的對象。不可變性還有其他的優點如線程安全。如果你可以僅僅通過將某個field聲明成final就能保證hashCode是不變的，那么請這么做吧。因為獲取對象的時候要用到equals()和hashCode()方法，那么鍵對象正確的重寫這兩個方法是非常重要的。如果兩個不相等的對象返回不同的hashcode的話，那么碰撞的幾率就會小些，這樣就能提高HashMap的性能。
-
我們可以使用自定義的對象作為鍵嗎？ 我們可以利用自己的對象作為鍵，只要它遵守了equals()和hashCode()方法的定義規則。
-
我們可以使用CocurrentHashMap來代替Hashtable嗎？ 我們知道Hashtable是synchronized的，但是ConcurrentHashMap同步性能更好，因為它僅僅根據同步級別對map的一部分進行上鎖。ConcurrentHashMap當然可以代替HashTable，但是HashTable提供更強的線程安全性。
-
多線程條件下，重調整hashMap大小會出現什么問題？ 當重新調整HashMap大小的時候，確實存在條件競爭，因為如果兩個線程都發現HashMap需要重新調整大小了，它們會同時試著調整大小。在調整大小的過程中，存儲在鏈表中的元素的次序會反過來，因為移動到新的bucket位置的時候，HashMap并不會將元素放在鏈表的尾部，而是放在頭部，這是為了避免尾部遍歷(tail traversing)。如果條件競爭發生了，那么就死循環了。
5.總結
HashMap基于hashing原理，我們通過put()和get()方法儲存和獲取對象。當我們將鍵值對傳遞給put()方法時，它調用鍵對象的hashCode()方法來計算hashcode，讓后找到bucket位置來儲存值對象。當獲取對象時，通過鍵對象的equals()方法找到正確的鍵值對，然后返回值對象。HashMap使用鏈表（拉鏈法）來解決hashCode碰撞問題，當發生碰撞了，對象將會儲存在鏈表的下一個節點中。 HashMap在每個鏈表節點中儲存鍵值對對象。如果兩個不同的鍵對象的hashCode相同，那么它們會儲存在同一個bucket位置的鏈表中。鍵對象的equals()方法用來找到鍵值對。由于HashMap的種種好處，我們經常可以利用hashMap作為緩存
來自：http://www.androidchina.net/5561.html