前言

? 前段時(shí)間研究了一下JDK 1.6 的 HashMap 源碼，把部份重要的方法分析一下，當(dāng)然HashMap中還有一些值得研究得就交給讀者了，如有不正確之處還望留言指正。

準(zhǔn)備

? 需要熟悉數(shù)組和鏈表這兩個(gè)基本數(shù)據(jù)結(jié)構(gòu)。如果對(duì)鏈表不太熟悉的話，可以來幾道leetcode上的相關(guān)的鏈表算法題。熟悉后看 HashMap 就會(huì)快很多了。
? 基本原理：HashMap中的基本數(shù)據(jù)結(jié)構(gòu)是數(shù)組加鏈表。table 是一個(gè)固定的數(shù)組。 數(shù)組里面的每個(gè)坑里面填的是一個(gè)叫Entry類。 其實(shí)就是一個(gè)固定的Entry數(shù)組。如果同一個(gè)坑里面存在兩個(gè)不同的數(shù)據(jù)，那么兩個(gè)數(shù)據(jù)就以鏈表的形式連接起來。最新的在最前面，原因是認(rèn)為最新的容易經(jīng)常被訪問。

構(gòu)造函數(shù)

? 基本原理知道了。現(xiàn)在直接研究帶參數(shù)的構(gòu)造函數(shù)就可以了，其他的構(gòu)造函數(shù)就是調(diào)用該方法。

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 >= initialCapacityint capacity = 1;while (capacity < initialCapacity)capacity <<= 1;this.loadFactor = loadFactor;threshold = (int)(capacity * loadFactor);table = new Entry[capacity];init();}

? MAXIMUM_CAPACITY = 1 << 30 2的30次方1073741824，也就是HashMap中table數(shù)組的大小不能超過該數(shù)字。 從上面代碼可以看出來table的坑位只能是2的冪次方。如果你傳入的initialCapacity為7 那么其實(shí)table 的大小為8； 也就是table的大小為傳入進(jìn)來的initialCapacity的數(shù)值大于該大小的2的冪次方。threshold 為他的閾值也就是 HashMap 的真正大小不能超過該值，超過了就進(jìn)行擴(kuò)容操作。 如果table數(shù)組的大小為16時(shí)。用它默認(rèn)的擴(kuò)容因子0.75f。那么他的閾值就是12。 也就是 table數(shù)據(jù)，數(shù)組中的加上鏈表的不能超過12。
我們看看第二個(gè)構(gòu)造函數(shù)。參數(shù)為一個(gè)Map 我這里順便把HashMap中的嵌套類Entry類說一下。可以自己再源碼上觀看。

public HashMap(Map<? extends K, ? extends V> m) {// 對(duì)比該map的size大小，新的map最新的容量為16this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);// 創(chuàng)建所有mapputAllForCreate(m);}private void putAllForCreate(Map<? extends K, ? extends V> m) {// 對(duì)每一個(gè)Entry進(jìn)行迭代for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {Map.Entry<? extends K, ? extends V> e = i.next();//創(chuàng)建數(shù)據(jù)賦值putForCreate(e.getKey(), e.getValue());}}private void putForCreate(K key, V value) {int hash = (key == null) ? 0 : hash(key.hashCode());// 計(jì)算table中的位置int i = indexFor(hash, table.length);/*** Look for preexisting entry for key. This will never happen for* clone or deserialize. It will only happen for construction if the* input Map is a sorted map whose ordering is inconsistent w/ equals.*/for (Entry<K,V> e = table[i]; e != null; e = e.next) {Object k;// 相同的值覆蓋。if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k)))) {e.value = value;return;}}// 創(chuàng)建EntrycreateEntry(hash, key, value, i);}void createEntry(int hash, K key, V value, int bucketIndex) {Entry<K,V> e = table[bucketIndex];// 頭節(jié)點(diǎn)插入table[bucketIndex] = new Entry<K,V>(hash, key, value, e);size++;}// 嵌套類 和HashMap類沒關(guān)系 獨(dú)立存在 默認(rèn)權(quán)限 只能本包訪問 也就是Java.util下的包訪問 HashHap中并沒有提供 Map.Entry<K,V>這樣的返回對(duì)象出去。有的只是一個(gè) Set<Map.Entry<K,V>> //一個(gè)代理類。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 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();}/*** 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) {}}

put方法

? 為什么要從put方法研究起呢。因?yàn)镠ashMap中最常用得就是put方法。而且里面還涉及到擴(kuò)容操作。如果把這些看懂了還是會(huì)很舒服得。

public V put(K key, V value) {if (key == null)// 如果key為null的話 直接添加到table[0]的位置 for 循環(huán) table[0]上的元素。如果有元素的話 查看該元素的key是不是null 如果是的話 就更新value值，直到table[0]這個(gè)鏈表結(jié)束。 如果結(jié)束后還是沒有的話，就把為null的key 對(duì)應(yīng)的value 頭插法 插入頭部。 可以查看 putForNullKey(value) 方法。return putForNullKey(value);// 計(jì)算Hash值 int hash = hash(key.hashCode());// 取key的Hash值得 二進(jìn)制數(shù)得后幾位。 如果key得hash為1101011 。而table這個(gè)數(shù)組得大小一直都是2的冪次方。 indexFor()方法做的事 key的hash與table.length-1做&運(yùn)算。假如table數(shù)組的大小為16，也就是 11011011 & 1111 會(huì)等于 1011 。這個(gè)方法的意義也就是只要你得Hash值是隨機(jī)的，碰撞性低，那么你在table中位置也就是 碰撞低的。int i = indexFor(hash, table.length);// 查詢?cè)搕able[i] 位置上的鏈表。for (Entry<K,V> e = table[i]; e != null; e = e.next) {Object k;// 如果 key相等 那么就更新 否則 下一位。。。。 直至結(jié)束。if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {V oldValue = e.value;e.value = value;e.recordAccess(this);return oldValue;}}// 修改次數(shù)加一modCount++;// 頭插法 并看size是都大于閾值了，如果大于就要擴(kuò)容了。addEntry(hash, key, value, i);return null;}void addEntry(int hash, K key, V value, int bucketIndex) {Entry<K,V> e = table[bucketIndex];table[bucketIndex] = new Entry<K,V>(hash, key, value, e);if (size++ >= threshold)//擴(kuò)容操作 2倍擴(kuò)容resize(2 * table.length);}// 擴(kuò)容方法 參數(shù)為擴(kuò)容大小void resize(int newCapacity) {Entry[] oldTable = table;int oldCapacity = oldTable.length;if (oldCapacity == MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return;}// 創(chuàng)建一個(gè)新得數(shù)組 名字叫做newTable length為 newCapacityEntry[] newTable = new Entry[newCapacity];// 擴(kuò)容操作transfer(newTable);// 重新賦值 table = newTable;// 閾值threshold = (int)(newCapacity * loadFactor);}// 擴(kuò)容操作void transfer(Entry[] newTable) {// 將原先的table數(shù)組 賦值給 srcEntry[] src = table;int newCapacity = newTable.length;// 逐個(gè)操作 從 src[0] 位置上的Entry 開始for (int j = 0; j < src.length; j++) {// 將src[j]的值給 e變量。Entry<K,V> e = src[j];// 對(duì)這個(gè)e 鏈表進(jìn)行往下操作if (e != null) {// 清空src[j] = null;do {//e 的下面一位 其實(shí)就是 next 后移 （這里如果兩個(gè)線程同時(shí)在這里操作的話，A線程在這里執(zhí)行這條語句后掛起的話，B線程完成擴(kuò)容操作后，A線程再喚醒時(shí)，有可能發(fā)生循環(huán)鏈表。然后使用get方法的時(shí)候，導(dǎo)致死循環(huán)，cpu利用100%）Entry<K,V> next = e.next;// 對(duì)e 重新定位。int i = indexFor(e.hash, newCapacity);// 將e.next 從e 斷開 并把e.next的值 指到 newTable[i]的值e.next = newTable[i];// 將 e 賦值給 newTable[i] newTable[i] = e;// e 往后移e = next;} while (e != null);}}}

舒服了舒服了。 如果想看怎么發(fā)生死循環(huán)的可以看小灰的文章 高并發(fā)下的HashMap 。

get方法

get方法相對(duì)而言就比較簡(jiǎn)單了。

public V get(Object key) {if (key == null)// 直接查詢table[0] 上鏈表key為 null的值return getForNullKey();// 定位table上的位置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;}

remove方法

remove方法相對(duì)而言，只要你會(huì)鏈表的刪除操作，就很好理解了。如果有不明白的可以。將鏈表這個(gè)數(shù)據(jù)結(jié)構(gòu)好好學(xué)習(xí)一下。

public V remove(Object key) {// 移除元素方法Entry<K,V> e = removeEntryForKey(key);return (e == null ? null : e.value);}// 這里其實(shí)就是鏈表的刪除操作 。final Entry<K,V> removeEntryForKey(Object key) {int hash = (key == null) ? 0 : hash(key.hashCode());// 定位位置int i = indexFor(hash, table.length);// 將table[i] 這個(gè)鏈表賦值給prev Entry<K,V> prev = table[i];// prev 賦值給 eEntry<K,V> e = prev;while (e != null) {// 下面一位Entry<K,V> next = e.next;Object k;// key是否相等if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k)))) {modCount++;size--;// 如果要?jiǎng)h除的時(shí)table[i]的頭部數(shù)據(jù) if (prev == e)// table[i] 等于next 刪除頭部table[i] = next;else// 否則 刪除這個(gè) prev.next = next;e.recordRemoval(this);return e;}prev = e;e = next;}return e;}

總結(jié)

? HashMap中的學(xué)問，遠(yuǎn)不止這些。 其中還涉及到設(shè)計(jì)模式，迭代器等等。上面這些只是常用的。個(gè)人非常推薦把數(shù)組和鏈表這個(gè)兩個(gè)非常基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)好好練習(xí)一下。雖然說早就把JDK 1.6的HashMap 源碼看了一下，順便把 ConcurrentHashMap中的一些源碼也看了。但是寫下來的時(shí)候，再看一遍，印象果然深刻多了。先把1.6的看了，在看1.8的吧。

轉(zhuǎn)載于:https://www.cnblogs.com/Krloypower/p/10675686.html

總結(jié)

以上是生活随笔為你收集整理的JDK 1.6 HashMap 源码分析的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。