存儲(chǔ)結(jié)構(gòu)
首先，HashMap是基于哈希表存儲(chǔ)的。它內(nèi)部有一個(gè)數(shù)組，當(dāng)元素要存儲(chǔ)的時(shí)候，先計(jì)算其key的哈希值，根據(jù)哈希值找到元素在數(shù)組中對(duì)應(yīng)的下標(biāo)。如果這個(gè)位置沒(méi)有元素，就直接把當(dāng)前元素放進(jìn)去，如果有元素了(這里記為A)，就把當(dāng)前元素鏈接到元素A的前面，然后把當(dāng)前元素放入數(shù)組中。所以在Hashmap中，數(shù)組其實(shí)保存的是鏈表的首節(jié)點(diǎn)。下面是百度百科的一張圖：

如上圖，每個(gè)元素是一個(gè)Entry對(duì)象，在其中保存了元素的key和value，還有一個(gè)指針可用于指向下一個(gè)對(duì)象。所有哈希值相同的key(也就是沖突了)用鏈表把它們串起來(lái)，這是拉鏈法。

內(nèi)部變量

//默認(rèn)初始容量
static final int DEFAULT_INITIAL_CAPACITY = 16;
//最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//默認(rèn)裝載因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//哈希表
transient Entry<K,V>[] table;
//鍵值對(duì)的數(shù)量
transient int size;
//擴(kuò)容的閾值
int threshold;
//哈希數(shù)組的裝載因子
final float loadFactor;

在上面的變量中，capacity是指哈希表的長(zhǎng)度，也就是table的大小，默認(rèn)為16。裝載因子loadFactor是哈希表的“裝滿(mǎn)程度”，JDK的文檔是這樣說(shuō)的：

The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.
大體意思是：裝載因子是哈希表在擴(kuò)容之前能裝多滿(mǎn)的度量值。當(dāng)哈希表中“鍵值對(duì)”的數(shù)量超過(guò)當(dāng)前容量(capacity)和裝載因子的乘積后，哈希表重新散列(也就是內(nèi)部的數(shù)據(jù)結(jié)構(gòu)重建了)，并且哈希表的容量大約變?yōu)樵瓉?lái)的兩倍。

從上面的變量定義可以看出，默認(rèn)的裝載因子DEFAULT_LOAD_FACTOR 是0.75。這個(gè)值越大，空間利用率越高，但查詢(xún)速度(包括get和put)操作會(huì)變慢。明白了裝載因子之后，threshold也就能理解了，它其實(shí)等于容量*裝載因子。

構(gòu)造器

public HashMap(int initialCapacity, float loadFactor) {
  if (initialCapacity < 0)
    throw new IllegalArgumentException("Illegal initial capacity: " +
                      initialCapacity);
  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) //計(jì)算出大于指定容量的最小的2的冪
    capacity <<= 1;

  this.loadFactor = loadFactor;
  threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
  table = new Entry[capacity];  //給哈希表分配空間
  useAltHashing = sun.misc.VM.isBooted() &&
      (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
  init();
}

構(gòu)造器有好幾個(gè)，最終都會(huì)調(diào)用上面的這個(gè)。它接受兩個(gè)參數(shù)，一個(gè)是初始容量，還有一個(gè)是裝載因子。剛開(kāi)始先判斷值合不合法，有問(wèn)題的話(huà)會(huì)拋出異常。重要的是下面的capacity的計(jì)算，它的邏輯是計(jì)算出大于initialCapacity的最小的2的冪。其實(shí)目的就是要讓容量能大于等于指定的初始容量，但這個(gè)值還得是2的指數(shù)倍，這是一個(gè)關(guān)鍵的問(wèn)題。這么做的原因主要是為了哈希值的映射。先來(lái)看一下HashMap中有關(guān)哈希的方法：

final int hash(Object k) {
  int h = 0;
  if (useAltHashing) {
    if (k instanceof String) {
      return sun.misc.Hashing.stringHash32((String) k);
    }
    h = hashSeed;
  }
  h ^= k.hashCode();
  // This function ensures that hashCodes that differ only by
  // constant multiples at each bit position have a bounded
  // number of collisions (approximately 8 at default load factor).
  h ^= (h >>> 20) ^ (h >>> 12);
  return h ^ (h >>> 7) ^ (h >>> 4);
}
static int indexFor(int h, int length) {
  return h & (length-1);
}

hash()方法重新計(jì)算了key的哈希值，用了比較復(fù)雜的位運(yùn)算，具體邏輯我也不清楚，反正肯定是比較好的方法，能減少?zèng)_突什么的。

下面的indexFor()是根據(jù)哈希值得到元素在哈希表中的下標(biāo)。一般在哈希表中是用哈希值對(duì)表長(zhǎng)取模得到。當(dāng)length(也就是capacity)為2的冪時(shí)，h & (length-1)是同樣的效果。并且，2的冪一定是偶數(shù)，那么減1之后就是奇數(shù)，二進(jìn)制的最后一位一定是1。那么h & (length-1)的最后一位可能是1，也可能是0，可以均勻地散列。如果length是奇數(shù)，那么length-1就是偶數(shù)，最后一位是0。此時(shí)h & (length-1)的最后一位只可能是0，所有得到的下標(biāo)都是偶數(shù)，那么哈希表就浪費(fèi)了一半的空間。所以HashMap中的容量(capacity)一定要是2的冪。可以看到默認(rèn)的DEFAULT_INITIAL_CAPACITY=16和MAXIMUM_CAPACITY=1<<30都是這樣的。

Entry對(duì)象
HashMap中的鍵值對(duì)被封裝成Entry對(duì)象，這是HashMap中的一個(gè)內(nèi)部類(lèi)，看一下它的實(shí)現(xiàn)：

static class Entry<K,V> implements Map.Entry<K,V> {
  final K key;
  V value;
  Entry<K,V> next;
  int hash;

  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;
  }

  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();
  }
  void recordAccess(HashMap<K,V> m) {
  }
  void recordRemoval(HashMap<K,V> m) {
  }
}

這個(gè)類(lèi)的實(shí)現(xiàn)還是簡(jiǎn)潔易懂的。提供了getKey()、getValue()等方法供調(diào)用，判斷相等是要求key和value均相等。

put操作
先put了才能get，所以先看一下put()方法：

public V put(K key, V value) {
  if (key == null)
    return putForNullKey(value);
  int hash = hash(key);
  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;
}

在這個(gè)方法中，先判斷key是否為null，是的話(huà)調(diào)用putForNullKey()方法，這說(shuō)明HashMap允許key為null(其實(shí)value可以)。如果不是null，計(jì)算哈希值并且得到在表中的下標(biāo)。然后到對(duì)應(yīng)的鏈表中查詢(xún)是否已經(jīng)存在相同的key，如果已經(jīng)存在就直接更新值(value)。否則，調(diào)用addEntry()方法進(jìn)行插入。

看一下putForNullKey()方法：

private V putForNullKey(V value) {
  for (Entry<K,V> e = table[0]; e != null; e = e.next) {
    if (e.key == null) {
      V oldValue = e.value;
      e.value = value;
      e.recordAccess(this);
      return oldValue;
    }
  }
  modCount++;
  addEntry(0, null, value, 0);
  return null;
}

可以看到，key為null時(shí)直接在下標(biāo)0處插入，同樣是存在就更新值，否則調(diào)用addEntry()插入。

下面是addEntry()方法的實(shí)現(xiàn)：

void addEntry(int hash, K key, V value, int bucketIndex) {
  if ((size >= threshold) && (null != table[bucketIndex])) {
    resize(2 * table.length);
    hash = (null != key) ? hash(key) : 0;
    bucketIndex = indexFor(hash, table.length);
  }

  createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
  Entry<K,V> e = table[bucketIndex];
  table[bucketIndex] = new Entry<>(hash, key, value, e);
  size++;
}

首先判斷是否要擴(kuò)容(擴(kuò)容會(huì)重新計(jì)算下標(biāo)值，并且復(fù)制元素)，然后計(jì)算數(shù)組下標(biāo)，最后在createEntry()中使用頭插法插入元素。

get操作

public V get(Object key) {
  if (key == null)
    return getForNullKey();
  Entry<K,V> entry = getEntry(key);

  return null == entry ? null : entry.getValue();
}
private V getForNullKey() {
  for (Entry<K,V> e = table[0]; e != null; e = e.next) {
    if (e.key == null)
      return e.value;
  }
  return null;
}
final Entry<K,V> getEntry(Object key) {
  int hash = (key == null) ? 0 : 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 != null && key.equals(k))))
      return e;
  }
  return null;
}

這個(gè)比put()簡(jiǎn)單一些，同樣要判斷key是不是null，然后就是鏈表的遍歷查詢(xún)。

性能優(yōu)化
HashMap是一個(gè)高效通用的數(shù)據(jù)結(jié)構(gòu)，它在每一個(gè)Java程序中都隨處可見(jiàn)。先來(lái)介紹些基礎(chǔ)知識(shí)。你可能也知 道，HashMap使用key的hashCode()和equals()方法來(lái)將值劃分到不同的桶里。桶的數(shù)量通常要比map中的記錄的數(shù)量要稍大，這樣 每個(gè)桶包括的值會(huì)比較少（最好是一個(gè)）。當(dāng)通過(guò)key進(jìn)行查找時(shí)，我們可以在常數(shù)時(shí)間內(nèi)迅速定位到某個(gè)桶（使用hashCode()對(duì)桶的數(shù)量進(jìn)行取模） 以及要找的對(duì)象。

這些東西你應(yīng)該都已經(jīng)知道了。你可能還知道哈希碰撞會(huì)對(duì)hashMap的性能帶來(lái)災(zāi)難性的影響。如果多個(gè)hashCode()的值落到同一個(gè)桶內(nèi)的 時(shí)候，這些值是存儲(chǔ)到一個(gè)鏈表中的。最壞的情況下，所有的key都映射到同一個(gè)桶中，這樣hashmap就退化成了一個(gè)鏈表——查找時(shí)間從O(1)到 O(n)。我們先來(lái)測(cè)試下正常情況下hashmap在Java 7和Java 8中的表現(xiàn)。為了能完成控制hashCode()方法的行為，我們定義了如下的一個(gè)Key類(lèi)：

class Key implements Comparable<Key> {
private final int value;
Key(int value) {
this.value = value;
}
@Override
public int compareTo(Key o) {
return Integer.compare(this.value, o.value);
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass())
return false;
Key key = (Key) o;
return value == key.value;
}
@Override
public int hashCode() {
return value;
}
}

Key類(lèi)的實(shí)現(xiàn)中規(guī)中矩：它重寫(xiě)了equals()方法并且提供了一個(gè)還算過(guò)得去的hashCode()方法。為了避免過(guò)度的GC，我將不可變的Key對(duì)象緩存了起來(lái)，而不是每次都重新開(kāi)始創(chuàng)建一遍：

class Key implements Comparable<Key> {
public class Keys {
public static final int MAX_KEY = 10_000_000;
private static final Key[] KEYS_CACHE = new Key[MAX_KEY];
static {
for (int i = 0; i < MAX_KEY; ++i) {
KEYS_CACHE[i] = new Key(i);
}
}
public static Key of(int value) {
return KEYS_CACHE[value];
}

現(xiàn)在我們可以開(kāi)始進(jìn)行測(cè)試了。我們的基準(zhǔn)測(cè)試使用連續(xù)的Key值來(lái)創(chuàng)建了不同的大小的HashMap（10的乘方，從1到1百萬(wàn)）。在測(cè)試中我們還會(huì)使用key來(lái)進(jìn)行查找，并測(cè)量不同大小的HashMap所花費(fèi)的時(shí)間：

import com.google.caliper.Param;
import com.google.caliper.Runner;
import com.google.caliper.SimpleBenchmark;
public class MapBenchmark extends SimpleBenchmark {
private HashMap<Key, Integer> map;
@Param
private int mapSize;
@Override
protected void setUp() throws Exception {
map = new HashMap<>(mapSize);
for (int i = 0; i < mapSize; ++i) {
map.put(Keys.of(i), i);
}
}
public void timeMapGet(int reps) {
for (int i = 0; i < reps; i++) {
map.get(Keys.of(i % mapSize));
}
}
}

有意思的是這個(gè)簡(jiǎn)單的HashMap.get()里面，Java 8比Java 7要快20%。整體的性能也相當(dāng)不錯(cuò)：盡管HashMap里有一百萬(wàn)條記錄，單個(gè)查詢(xún)也只花了不到10納秒，也就是大概我機(jī)器上的大概20個(gè)CPU周期。 相當(dāng)令人震撼！不過(guò)這并不是我們想要測(cè)量的目標(biāo)。

假設(shè)有一個(gè)很差勁的key，他總是返回同一個(gè)值。這是最糟糕的場(chǎng)景了，這種情況完全就不應(yīng)該使用HashMap:

class Key implements Comparable<Key> {
//...
@Override
public int hashCode() {
return 0;
}
}

Java 7的結(jié)果是預(yù)料中的。隨著HashMap的大小的增長(zhǎng)，get()方法的開(kāi)銷(xiāo)也越來(lái)越大。由于所有的記錄都在同一個(gè)桶里的超長(zhǎng)鏈表內(nèi)，平均查詢(xún)一條記錄就需要遍歷一半的列表。因此從圖上可以看到，它的時(shí)間復(fù)雜度是O(n)。

不過(guò)Java 8的表現(xiàn)要好許多！它是一個(gè)log的曲線(xiàn)，因此它的性能要好上好幾個(gè)數(shù)量級(jí)。盡管有嚴(yán)重的哈希碰撞，已是最壞的情況了，但這個(gè)同樣的基準(zhǔn)測(cè)試在JDK8中的時(shí)間復(fù)雜度是O(logn)。單獨(dú)來(lái)看JDK 8的曲線(xiàn)的話(huà)會(huì)更清楚，這是一個(gè)對(duì)數(shù)線(xiàn)性分布：

為什么會(huì)有這么大的性能提升，盡管這里用的是大O符號(hào)（大O描述的是漸近上界）？其實(shí)這個(gè)優(yōu)化在JEP-180中已經(jīng)提到了。如果某個(gè)桶中的記錄過(guò) 大的話(huà)（當(dāng)前是TREEIFY_THRESHOLD = 8），HashMap會(huì)動(dòng)態(tài)的使用一個(gè)專(zhuān)門(mén)的treemap實(shí)現(xiàn)來(lái)替換掉它。這樣做的結(jié)果會(huì)更好，是O(logn)，而不是糟糕的O(n)。它是如何工作 的？前面產(chǎn)生沖突的那些KEY對(duì)應(yīng)的記錄只是簡(jiǎn)單的追加到一個(gè)鏈表后面，這些記錄只能通過(guò)遍歷來(lái)進(jìn)行查找。但是超過(guò)這個(gè)閾值后HashMap開(kāi)始將列表升 級(jí)成一個(gè)二叉樹(shù)，使用哈希值作為樹(shù)的分支變量，如果兩個(gè)哈希值不等，但指向同一個(gè)桶的話(huà)，較大的那個(gè)會(huì)插入到右子樹(shù)里。如果哈希值相等，HashMap希 望key值最好是實(shí)現(xiàn)了Comparable接口的，這樣它可以按照順序來(lái)進(jìn)行插入。這對(duì)HashMap的key來(lái)說(shuō)并不是必須的，不過(guò)如果實(shí)現(xiàn)了當(dāng)然最 好。如果沒(méi)有實(shí)現(xiàn)這個(gè)接口，在出現(xiàn)嚴(yán)重的哈希碰撞的時(shí)候，你就并別指望能獲得性能提升了。

這個(gè)性能提升有什么用處？比方說(shuō)惡意的程序，如果它知道我們用的是哈希算法，它可能會(huì)發(fā)送大量的請(qǐng)求，導(dǎo)致產(chǎn)生嚴(yán)重的哈希碰撞。然后不停的訪(fǎng)問(wèn)這些 key就能顯著的影響服務(wù)器的性能，這樣就形成了一次拒絕服務(wù)攻擊（DoS）。JDK 8中從O(n)到O(logn)的飛躍，可以有效地防止類(lèi)似的攻擊，同時(shí)也讓HashMap性能的可預(yù)測(cè)性稍微增強(qiáng)了一些。我希望這個(gè)提升能最終說(shuō)服你的 老大同意升級(jí)到JDK 8來(lái)。

測(cè)試使用的環(huán)境是：Intel Core i7-3635QM @ 2.4 GHz，8GB內(nèi)存，SSD硬盤(pán)，使用默認(rèn)的JVM參數(shù)，運(yùn)行在64位的Windows 8.1系統(tǒng) 上。

總結(jié)
HashMap的基本實(shí)現(xiàn)就如上面所分析的，最后做下總結(jié)：

• HashMap內(nèi)部用Entry對(duì)象保存鍵值對(duì)，基于哈希表存儲(chǔ)，用拉鏈法解決沖突。
• HashMap的默認(rèn)容量大小為16，默認(rèn)裝載因子為0.75?？梢灾付ㄈ萘看笮?，容量最終一定會(huì)被設(shè)置為2的冪，這是為了均勻地散列。
• HashMap的key和value都可以是null，當(dāng)然只能有一個(gè)key是null，value可以有多個(gè)。
• HashMap的鍵值對(duì)數(shù)量超過(guò)容量*裝載因子時(shí)會(huì)擴(kuò)容，擴(kuò)容后的容量大約是原來(lái)的兩倍。擴(kuò)容會(huì)重新散列，所以元素的位置可能發(fā)生會(huì)變化，而且這是一個(gè)耗時(shí)操作。
• HashMap是線(xiàn)程不安全的。