全面解析Java中的HashMap類

更新時間：2016年05月19日 08:59:52 作者：pastqing

HashMap類為Java提供了鍵值對應(yīng)的map類型,本文將從源碼角度全面解析Java中的HashMap類,同時包括其各種常用操作方法等,歡迎參考與借鑒

HashMap 和 HashSet 是 Java Collection Framework 的兩個重要成員，其中 HashMap 是 Map 接口的常用實現(xiàn)類，HashSet 是 Set 接口的常用實現(xiàn)類。雖然 HashMap 和 HashSet 實現(xiàn)的接口規(guī)范不同，但它們底層的 Hash 存儲機制完全一樣，甚至 HashSet 本身就采用 HashMap 來實現(xiàn)的。
實際上，HashSet 和 HashMap 之間有很多相似之處，對于 HashSet 而言，系統(tǒng)采用 Hash 算法決定集合元素的存儲位置，這樣可以保證能快速存、取集合元素；對于 HashMap 而言，系統(tǒng) key-value 當(dāng)成一個整體進行處理，系統(tǒng)總是根據(jù) Hash 算法來計算 key-value 的存儲位置，這樣可以保證能快速存、取 Map 的 key-value 對。
在介紹集合存儲之前需要指出一點：雖然集合號稱存儲的是 Java 對象，但實際上并不會真正將 Java 對象放入 Set 集合中，只是在 Set 集合中保留這些對象的引用而言。也就是說：Java 集合實際上是多個引用變量所組成的集合，這些引用變量指向?qū)嶋H的 Java 對象。

一、HashMap的基本特性

讀完JDK源碼HashMap.class中的注釋部分，可以總結(jié)出很多HashMap的特性。

HashMap允許key與value都為null, 而Hashtable是不允許的。

HashMap是線程不安全的，而Hashtable是線程安全的

HashMap中的元素順序不是一直不變的，隨著時間的推移，同一元素的位置也可能改變（resize的情況）

遍歷HashMap的時間復(fù)雜度與其的容量(capacity)和現(xiàn)有元素的個數(shù)（size）成正比。如果要保證遍歷的高效性，初始容量（capacity)不能設(shè)置太高或者平衡因子（load factor）不能設(shè)置太低。

與之前的相關(guān)List同樣，由于HashMap是線程不安全的, 因此迭代器在迭代過程中試圖做容器結(jié)構(gòu)上的改變的時候，會產(chǎn)生fail-fast。通過Collections.synchronizedMap(HashMap)可以得到一個同步的HashMap

二、Hash table 數(shù)據(jù)結(jié)構(gòu)分析

Hash table(散列表，哈希表),是根據(jù)關(guān)鍵字而直接訪問內(nèi)存存儲位置的數(shù)據(jù)結(jié)構(gòu)。也就是說散列表建立了關(guān)鍵字和存儲地址之間的一種直接映射

如下圖, key經(jīng)過散列函數(shù)得到buckets的一個索引位置。

201651985416482.png (315×230)

通過散列函數(shù)獲取index不可避免會出現(xiàn)相同的情況，也就是沖突。下面簡單介紹幾種解決沖突的方法：

Open addressing(開放定址法):此方法的基本思想就是遇到?jīng)_突時，順序掃描表下N個位置，如果有空閑就填入。具體算法不再說明，下面是示意圖：

201651985454024.png (380×330)

Separate chaining(拉鏈)：此方法基本思想就是遇到?jīng)_突時，將相同索引值的Entry用鏈表串起來。具體算法不再說明，下面是示意圖：

201651985520198.png (620×310)

JDK中的HashMap解決沖突的方法就是用的Separate chaining法。

三、HashMap源碼分析（JDK1.7）

1、HashMap讀寫元素

Entry
HashMap中的存放的元素是Entry類型，下面給出源碼中Entry的源碼：

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;
 }
 //key, value的get與set方法省略，get與set操作會在后面的迭代器中用到
 ...
 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;
 }
 //此處將Key的hashcode與Value的hashcode做亦或運算得到Entry的hashcode
 public final int hashCode() {
  return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
 }
 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包括key, value, hash以及下一個Entry的引用，很明顯這是個單鏈表，其實現(xiàn)了Map.Entry接口。

recordAcess(HashMap<K, V> 與recordRemoval(HashMap<K, V>)在HashMap中是沒有任何具體實現(xiàn)的。但是在LinkedHashMap這兩個方法用來實現(xiàn)LRU算法。

get：讀元素
從HashMap中獲取相應(yīng)的Entry，下面給出get相關(guān)源碼：

public V get(Object key) {
 //key是null的情況
 if (key == null)
  return getForNullKey();
 //根據(jù)key查找Entry
 Entry<K,V> entry = getEntry(key);
 return null == entry ? null : entry.getValue();
 }

getForNullKey源碼

private V getForNullKey() {
 if (size == 0) {
  return null;
 }
 //遍歷沖突鏈
 for (Entry<K,V> e = table[0]; e != null; e = e.next) {
  if (e.key == null)
  return e.value;
 }
 return null;
 }

key為Null的Entry存放在table[0]中，但是table[0]中的沖突鏈中不一定存在key為null，因此需要遍歷。

根據(jù)key獲取entry：

final Entry<K,V> getEntry(Object key) {
 if (size == 0) {
  return null;
 }
 int hash = (key == null) ? 0 : hash(key);
 //通過hash得到table中的索引位置，然后遍歷沖突鏈表找到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;
 }

以上就是HashMap讀取一個Entry的過程及其源碼。時間復(fù)雜度O(1)

put：寫元素
HashMap中put操作相對復(fù)雜，因為put操作的過程中會有HashMap的擴容操作。
新寫入一個元素，如果HashMap中存在要寫入元素的key，則執(zhí)行的是替換value的操作，相當(dāng)于update。下面是put源碼：

public V put(K key, V value) {
 //空表table的話，根據(jù)size的閾值填充
 if (table == EMPTY_TABLE) {
  inflateTable(threshold);
 }
 //填充key為Null的Entry
 if (key == null)
  return putForNullKey(value);
 //生成hash，得到索引Index的映射
 int hash = hash(key);
 int i = indexFor(hash, table.length);
 //遍歷當(dāng)前索引的沖突鏈，找是否存在對應(yīng)的key
 for (Entry<K,V> e = table[i]; e != null; e = e.next) {
  Object k;
  //如果存在對應(yīng)的key， 則替換oldValue并返回oldValue
  if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
  V oldValue = e.value;
  e.value = value;
  e.recordAccess(this);
  return oldValue;
  }
 }
 //沖突鏈中不存在新寫入的Entry的key
 modCount++;
 //插入一個新的Entry
 addEntry(hash, key, value, i);
 return null;
 }

addEntry與createEntry源碼：

void addEntry(int hash, K key, V value, int bucketIndex) {
 //插入新Entry前，先對當(dāng)前HashMap的size和其閾值大小的判斷，選擇是否擴容
 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];
 //頭插法，新寫入的entry插入當(dāng)前索引位置的沖突鏈第一個Entry的前面
 table[bucketIndex] = new Entry<>(hash, key, value, e);
 size++;
 }

以上就是HashMap寫入一個Entry的過程及其源碼。時間復(fù)雜度O(1)

remove移除元素：

final Entry<K,V> removeEntryForKey(Object key) {
 if (size == 0) {
  return null;
 }
 //根據(jù)key計算hash值，獲取索引
 int hash = (key == null) ? 0 : hash(key);
 int i = indexFor(hash, table.length);
 //鏈表的刪除，定義兩個指針，pre表示前驅(qū)
 Entry<K,V> prev = table[i];
 Entry<K,V> e = prev;
 //遍歷沖突鏈，刪除所有為key的Enrty
 while (e != null) {
  Entry<K,V> next = e.next;
  Object k;
  //找到了
  if (e.hash == hash &&
  ((k = e.key) == key || (key != null && key.equals(k)))) {
  modCount++;
  size--;
  //找到第一個結(jié)點就是要刪除的結(jié)點
  if (prev == e)
   table[i] = next;
  else
   prev.next = next;
  e.recordRemoval(this);
  return e;
  }
  prev = e;
  e = next;
 }
 return e;
 }

以上就是HashMap刪除一個Entry的過程及其源碼。時間復(fù)雜度O(1)

2、HashMap的哈希原理（hash function）

HashMap中散列函數(shù)的實現(xiàn)是通過hash(Object k) 與 indexFor(int h, int length)完成，下面看下源碼：

 final int hash(Object k) {
 int h = hashSeed;
 if (0 != h && k instanceof String) {
  return sun.misc.Hashing.stringHash32((String) k);
 }
 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);
 }

獲取Index索引源碼：

static int indexFor(int h, int length) {
 // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
 return h & (length-1);
 }

HashMap通過一個hash function將key映射到[0, table.length]的區(qū)間內(nèi)的索引。這樣的索引方法大體有兩種：

hash(key) % table.length, 其中l(wèi)ength必須為素數(shù)。JDK中HashTable利用此實現(xiàn)方式。
具體使用素數(shù)的原因，可以查找相關(guān)算法資料證明，這里不再陳述。

hash(key) & (table.length - 1 ) 其中l(wèi)ength必須為2指數(shù)次方。JDK中HashMap利用此實現(xiàn)方式。
因為length的大小為2指數(shù)次方倍，因此 hash(key) & (table.length - 1)總會在[0, length - 1]之間。但是僅僅這樣做的話會出現(xiàn)問題一個沖突很大的問題，因為JAVA中hashCode的值為32位，當(dāng)HashMap的容量偏小，例如16時，做異或運算時，高位總是被舍棄，低位運算后卻增加了沖突發(fā)生的概率。

因此為了降低沖突發(fā)生的概率，代碼中做了很多位運算以及異或運算。

3、HashMap內(nèi)存分配策略

成員變量capacity與loadFactor
HashMap中要求容量Capacity是2的指數(shù)倍，默認容量是1 << 4 = 16。HashMap中還存在一個平衡因子（loadFactor），過高的因子會降低存儲空間但是查找（lookup，包括HashMap中的put與get方法）的時間就會增加。 loadFactor默認值為0.75是權(quán)衡了時間復(fù)雜度以及空間復(fù)雜度給出的最優(yōu)值。

 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
 static final int MAXIMUM_CAPACITY = 1 << 30;
 static final float DEFAULT_LOAD_FACTOR = 0.75f;

HashMap的構(gòu)造函數(shù)
HashMap的構(gòu)造就是設(shè)置capacity，與loadFactor的初始值

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);
 this.loadFactor = loadFactor;
 threshold = initialCapacity;
 init();
 }

之前說過HashMap中capacity必須是2的指數(shù)倍，構(gòu)造函數(shù)里并沒有限制，那如何保證保證capacity的值是2的指數(shù)倍呢？
在put操作時候，源碼中會判斷目前的哈希表是否是空表，如果是則調(diào)用inflateTable(int toSize)

private void inflateTable(int toSize) {
 // Find a power of 2 >= toSize
 int capacity = roundUpToPowerOf2(toSize);
 threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
 table = new Entry[capacity];
 initHashSeedAsNeeded(capacity);
 }

其中roundUpToPowerOf2就是獲取大于等于給定參數(shù)的最小的2的n次冪

private static int roundUpToPowerOf2(int number) {
 // assert number >= 0 : "number must be non-negative";
 return number >= MAXIMUM_CAPACITY
  ? MAXIMUM_CAPACITY
  : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
 }

Integer.hightestOneBit(int)是將給定參數(shù)的最高位的1保留，剩下的變?yōu)?的操作，簡單說就是將參數(shù)int變?yōu)樾∮诘扔谒淖畲蟮?的n次冪。

若number為2的n次冪，減1后最高位處于原來的次高位，再左移1位仍然可以定位到最高位位置
若number不是2的n次冪，減1左移1位后最高位仍是原來的最高位

擴容：
HashMap在put操作的時候會發(fā)生resize行為，具體源碼如下：

void resize(int newCapacity) {
 Entry[] oldTable = table;
 int oldCapacity = oldTable.length;
 //哈希表已達到最大容量，1 << 30
 if (oldCapacity == MAXIMUM_CAPACITY) {
  threshold = Integer.MAX_VALUE;
  return;
 }
 Entry[] newTable = new Entry[newCapacity];
 //將oldTable中的Entry轉(zhuǎn)移到newTable中
 //initHashSeedAsNeeded的返回值決定是否重新計算hash值
 transfer(newTable, initHashSeedAsNeeded(newCapacity));
 table = newTable;
 //重新計算threshold
 threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
 }
void transfer(Entry[] newTable, boolean rehash) {
 int newCapacity = newTable.length;
 //遍歷oldTable
 for (Entry<K,V> e : table) {
  //遍歷沖突鏈
  while(null != e) {
  Entry<K,V> next = e.next;
  if (rehash) {
   //重新計算hash值
   e.hash = null == e.key ? 0 : hash(e.key);
  }
  int i = indexFor(e.hash, newCapacity);
  //將元素插入到頭部，頭插法
  e.next = newTable[i];
  newTable[i] = e;
  e = next;
  }
 }
 }

以上就是HashMap內(nèi)存分配的整個過程，總結(jié)說來就是，hashMap在put一個Entry的時候會檢查當(dāng)前容量與threshold的大小來選擇是否擴容。每次擴容的大小是2 * table.length。在擴容期間會根據(jù)initHashSeedAsNeeded判斷是否需要重新計算hash值。

四、HashMap的迭代器

HashMap中的ValueIterator， KeyIterator, EntryIterator等迭代器都是基于HashIterator的，下面看下它的源碼：

private abstract class HashIterator<E> implements Iterator<E> {
 Entry<K,V> next; // next entry to return
 int expectedModCount; // For fast-fail
 int index;  // current slot，table index
 Entry<K,V> current; // current entry
 HashIterator() {
  expectedModCount = modCount;
  //在哈希表中找到第一個Entry
  if (size > 0) { 
  Entry[] t = table;
  while (index < t.length && (next = t[index++]) == null)
   ;
  }
 }
 public final boolean hasNext() {
  return next != null;
 }
 final Entry<K,V> nextEntry() {
  //HashMap是非線程安全的，遍歷時仍然先判斷是否有表結(jié)構(gòu)的修改
  if (modCount != expectedModCount)
  throw new ConcurrentModificationException();
  Entry<K,V> e = next;
  if (e == null)
  throw new NoSuchElementException();
  if ((next = e.next) == null) {
  //找到下一個Entry
  Entry[] t = table;
  while (index < t.length && (next = t[index++]) == null)
   ;
  }
  current = e;
  return e;
 }
 public void remove() {
  if (current == null)
  throw new IllegalStateException();
  if (modCount != expectedModCount)
  throw new ConcurrentModificationException();
  Object k = current.key;
  current = null;
  HashMap.this.removeEntryForKey(k);
  expectedModCount = modCount;
 }
 }

Key, Value, Entry這個三個迭代器進行封裝就變成了keySet, values, entrySet三種集合視角。這三種集合視角都支持對HashMap的remove, removeAll, clear操作，不支持add， addAll操作。

您可能感興趣的文章: