hashmap怎麼取值_java源碼解析之HashMap

Map是java中用于存儲建值對的一種資料結構方式。鍵不能重複，每一個鍵可以比對多個值(也就是一個連結清單)。這個接口是用于替換Dictionary這個抽象類的。

HashMap用于存儲鍵值對，其中key可以為null，同時他的key存放索引方式是通過hash方式來實作的，是以他能快速的定位到你需要的key處。在HashMap内部是存放的一個Entry的數組。Entry的定義如下：

Entry(int h, K k, V v, Entry n) { value = v; next = n; key = k; hash = h; }
           

類定義

public class HashMap extends AbstractMap implements Map, Cloneable, Serializable
           

成員變量

構造方式

• public HashMap() 無參構造方式：用預設容量,預設擴容因子構造map
• public HashMap(int initialCapacity) 用initialCapacity容量,預設擴容因子構造map
• public HashMap(int initialCapacity, float loadFactor)用initialCapacity容量，loadFactor擴容因子構造map
• public HashMap(Map extends K, ? extends V> m) 用其他map構造新的map

核心方法

• 添加元素public V put(K key, V value)

public V put(K key, V value) { // 下面第一點講解 if (table == EMPTY_TABLE) { inflateTable(threshold); } // 下面第二點講解 if (key == null) return putForNullKey(value);  // 取key的hash值,并用這個hash值來計算 // 此鍵值對應該放置的數組中的索引(bucketIndex) int hash = hash(key); int i = indexFor(hash, table.length);  // 根據key算出的索引,根據索引取得數組i處的Entry(連結清單) // 循環判斷此連結清單中是否存在此key對應的節點 for (Entry e = table[i]; e != null; e = e.next) { Object k; // 如果節點e的hash值與key的hash值相等(就是比較的hashCode), // 也就是說發生了hash碰撞(key的hashCode跟e.key的hashCode是同一值) // 并且key相等(同一位置或者equals),也就是key已經存在對應節點 // 那麼就執行替換操作,并傳回老的那個值 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } }  // 1. 如果數組索引i處沒有放置過任何值,也就是table[i]=null // 2. table[i]已經放置了Entry,但是hash值不相等(不可能)或者是key不equals() // 則新增一個Entry節點 modCount++; addEntry(hash, key, value, i); return null; }
           

• 代碼分析：

1. 如果目前map中沒有任何元素，也就是說為空({})，那麼就重新擴充table，inflateTable()方法源碼如下：

private void inflateTable(int toSize) { // 将toSize向上取值到2的倍數 int capacity = roundUpToPowerOf2(toSize);  threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); table = new Entry[capacity]; // 重新給table指派 initHashSeedAsNeeded(capacity); // 重新計算hashSeed值 }
           

2. 如果key為null，則專門處理key為null的情況，putForNullKey()代碼如下：

private V putForNullKey(V value) { // 從下述循環代碼可以看出, key為null的元素, // 在内部數組中是放置在索引為0處位置的 // (可能key不為null也會放置在這裡,取決hash的結果如何) for (Entry e = table[0]; e != null; e = e.next) { if (e.key == null) { // 查找連結清單中key為null的節點,找到并用新值替換 V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } }  // 如果在數組0處沒有找到key為null的對應節點,則新增一個Entry節點 modCount++; // key為null,hash直接取0,放置在數組中的位置也直接取0 addEntry(0, null, value, 0); return null; }  // 在數組索引bucketIndex處添加新的節點(注意是新增節點,并不一定是新增數組元素) void addEntry(int hash, K key, V value, int bucketIndex) { // map目前容量達到了要擴容的值并且數組中待放置節點的元素位置已被占用 // 則擴容,并重新計算新的節點要放置在數組中的索引位置 if ((size >= threshold) && (null != table[bucketIndex])) { resize(2 * table.length); hash = (null != key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); } // 建立新的節點,并放置在數組中索引為buckedIndex處 createEntry(hash, key, value, bucketIndex); }  // 建立新的Entry節點(一個連結清單), 并将新的節點重新挂到數組上 // 在這裡要注意的: bucketIndex的計算方式是怎麼計算來的,在上面有講到 void createEntry(int hash, K key, V value, int bucketIndex) { // 擷取之前挂在數組bucketIndex處的Entry節點 Entry e = table[bucketIndex];  // new Entry<>(hash, key, value, e); // 建立一個新的節點,并跟原來的節點建立關系 table[bucketIndex] = new Entry<>(hash, key, value, e); size++; }
           

• 擷取元素public V get(Object key)

public V get(Object key) { // key為null,專門處理 if (key == null) return getForNullKey(); //取得數組0處的Entry Entry entry = getEntry(key);  return null == entry ? null : entry.getValue(); }  final Entry getEntry(Object key) { // map中沒有元素傳回null if (size == 0) { return null; }  // 根據key的hash值取得對應key存放在數組中的位置 int hash = (key == null) ? 0 : hash(key); for (Entry 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; }
           

• 擴容void resize(int newCapacity) 在put()等增加size的操作中調用，在上述的addEntry()方法中被調用

void resize(int newCapacity) { // 如果map容量已經達到Integer的最大值則不在擴容 Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; }  // 建立一個擴容後的新的空數組 Entry[] newTable = new Entry[newCapacity]; // 将map現在數組轉移到新的空數組中 // initHashSeedAsNeeded(newCapacity)用于确定在新數組 // 每個key是否要重新計算hash值 transfer(newTable, initHashSeedAsNeeded(newCapacity)); table = newTable; threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); }  /** * Transfers all entries from current table to newTable. */ void transfer(Entry[] newTable, boolean rehash) { // 新數組的長度 int newCapacity = newTable.length; // 對map中現有元素的老數組循環 for (Entry e : table) { // 取得的數組中元素不為空(對應索引處存在Entry連結清單) while(null != e) { // 将連結清單的下一個節點拎出來儲存 Entry next = e.next; // 是否需要重新計算key的hash值 if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } // 重新計算在新數組中的索引 int i = indexFor(e.hash, newCapacity); // 将已經轉換到新數組的entry拼接到目前處理entry的後面組成新的連結清單 e.next = newTable[i]; // 将新的連結清單重新放置在新數組的索引處 newTable[i] = e; // 處理老數組連結清單的下一個entry e = next; } } }
           

• map疊代器Iterator核心private abstract class HashIterator map中的KeyIterator，ValueIterator等疊代器均繼承自HashIterator。map中的疊代器跟list中的疊代器一樣，都會根據size變化次數來fail-fast(快速失敗檢查)

private abstract class HashIterator implements Iterator { Entry next; // next entry to return int expectedModCount; // For fast-fail int index; // current slot Entry current; // current entry  HashIterator() { expectedModCount = modCount; // 指派modCount // map有元素,就定位數組索引到第一個不為null的位置,并賦給next if (size > 0) { // advance to first entry Entry[] t = table; while (index < t.length && (next = t[index++]) == null) ; } }  public final boolean hasNext() { return next != null; }  final Entry nextEntry() { // 在疊代期間, modCount值發生變化 // (也就是map的size發生改變(執行了put, remove操作(疊代器的remove()除外))) if (modCount != expectedModCount) throw new ConcurrentModificationException(); Entry e = next; if (e == null) throw new NoSuchElementException(); // 繼續判斷下一個entry,如果為空,則繼續搜尋數組下一個索引位置 if ((next = e.next) == null) { Entry[] t = table; while (index < t.length && (next = t[index++]) == null) ; } // 傳回目前的entry 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; } }