HashMap也是我們使用非常多的Collection，它是基于哈希表的 Map 接口的實現，以key-value的形式存在。在HashMap中，key-value總是會當做一個整體來處理，系統會根據hash算法來來計算key-value的存儲位置，我們總是可以通過key快速地存、取value。下面就來分析HashMap的存取。
HashMap實現了Map接口，繼承AbstractMap。其中Map接口定義了鍵映射到值的規則，而AbstractMap類提供 Map 接口的骨干實現，以最大限度地減少實現此接口所需的工作，其實AbstractMap類已經實現了Map，這里標注Map LZ覺得應該是更加清晰吧！
[java] view plain copy
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable 從上圖我們可以看出HashMap底層實現還是數組，只是數組的每一項都是一條鏈。其中參數initialCapacity就代表了該數組的長度。下面為HashMap構造函數的源碼：
[java] view plain copypublic HashMap(int initialCapacity, float loadFactor) { //初始容量不能<0 if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); //初始容量不能 > 最大容量值，HashMap的最大容量值為2^30 if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; //負載因子不能 < 0 if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); // 計算出大于 initialCapacity 的最小的 2 的 n 次方值。 int capacity = 1; while (capacity < initialCapacity) capacity <<= 1; this.loadFactor = loadFactor; //設置HashMap的容量極限，當HashMap的容量達到該極限時就會進行擴容操作 threshold = (int) (capacity * loadFactor); //初始化table數組 table = new Entry[capacity]; init(); } 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. */ Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; } ....... } public V put(K key, V value) { //當key為null，調用putForNullKey方法，保存null與table第一個位置中，這是HashMap允許為null的原因 if (key == null) return putForNullKey(value); //計算key的hash值 int hash = hash(key.hashCode()); ------(1) //計算key hash 值在 table 數組中的位置 int i = indexFor(hash, table.length); ------(2) //從i出開始迭代 e,找到 key 保存的位置 for (Entry<K, V> e = table[i]; e != null; e = e.next) { Object k; //判斷該條鏈上是否有hash值相同的(key相同) //若存在相同，則直接覆蓋value，返回舊value if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; //舊值 = 新值 e.value = value; e.recordstatic int hash(int h) { h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } static int indexFor(int h, int length) { return h & (length-1); } 當n=15時，6和7的結果一樣，這樣表示他們在table存儲的位置是相同的，也就是產生了碰撞，6、7就會在一個位置形成鏈表，這樣就會導致查詢速度降低。誠然這里只分析三個數字不是很多，那么我們就看0-15。
從上面的圖表中我們看到總共發生了8此碰撞，同時發現浪費的空間非常大，有1、3、5、7、9、11、13、15處沒有記錄，也就是沒有存放數據。這是因為他們在與14進行&運算時，得到的結果最后一位永遠都是0，即0001、0011、0101、0111、1001、1011、1101、1111位置處是不可能存儲數據的，空間減少，進一步增加碰撞幾率，這樣就會導致查詢速度慢。而當length = 16時，length – 1 = 15 即1111，那么進行低位&運算時，值總是與原來hash值相同，而進行高位運算時，其值等于其低位值。所以說當length = 2^n時，不同的hash值發生碰撞的概率比較小，這樣就會使得數據在table數組中分布較均勻，查詢速度也較快。
這里我們再來復習put的流程：當我們想一個HashMap中添加一對key-value時，系統首先會計算key的hash值，然后根據hash值確認在table中存儲的位置。若該位置沒有元素，則直接插入。否則迭代該處元素鏈表并依此比較其key的hash值。如果兩個hash值相等且key值相等(e.hash == hash && ((k = e.key) == key || key.equals(k))),則用新的Entry的value覆蓋原來節點的value。如果兩個hash值相等但key值不等 ，則將該節點插入該鏈表的鏈頭。具體的實現過程見addEntry方法，如下：
[java] view plain copyvoid addEntry(int hash, K key, V value, int bucketIndex) { //獲取bucketIndex處的Entry Entry<K, V> e = table[bucketIndex]; //將新創建的 Entry 放入 bucketIndex 索引處，并讓新的 Entry 指向原來的 Entry table[bucketIndex] = new Entry<K, V>(hash, key, value, e); //若HashMap中元素的個數超過極限了，則容量擴大兩倍 if (size++ >= threshold) resize(2 * table.length); } public V get(Object key) { // 若為null，調用getForNullKey方法返回相對應的value if (key == null) return getForNullKey(); // 根據該 key 的 hashCode 值計算它的 hash 碼 int hash = hash(key.hashCode()); // 取出 table 數組中指定索引處的值 for (Entry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; //若搜索的key與查找的key相同，則返回相對應的value if (e.hash == hash && ((k = e.key) == key || key.equals(k))) return e.value; } return null; } 在這里能夠根據key快速的取到value除了和HashMap的數據結構密不可分外，還和Entry有莫大的關系，在前面就提到過，HashMap在存儲過程中并沒有將key，value分開來存儲，而是當做一個整體key-value來處理的，這個整體就是Entry對象。同時value也只相當于key的附屬而已。在存儲的過程中，系統根據key的hashcode來決定Entry在table數組中的存儲位置，在取的過程中同樣根據key的hashcode取出相對應的Entry對象。
新聞熱點
疑難解答
