注：本文源碼版本為JDK1.7.0_79
如有理解不到位的地方搂誉，歡迎大家多多指正
1.定義
??顧名思義，HashMap就是以鍵值對(duì)(key-value)的方式進(jìn)行數(shù)據(jù)存儲(chǔ)静檬，并以hash散列的方式進(jìn)行數(shù)據(jù)分布炭懊。HashMap繼承AbstractMap，并實(shí)現(xiàn)了Map拂檩、Cloneable侮腹、Serializable接口。如下所示：
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
2.成員變量
| 變量名 | 含義 | 默認(rèn)值 |
|---|---|---|
| size | HashMap中數(shù)據(jù)的個(gè)數(shù) | 0 |
| loadfactor | 負(fù)載因子稻励，衡量散列表空間的使用程度 | 0.75f |
| threshold | 表示當(dāng)HashMap的size大于threshold時(shí)會(huì)執(zhí)行resize操作 | capacity*loadFactor |
| modcount | 記錄map的修改次數(shù)父阻，在迭代器中使用，具體見(jiàn)后面分析 | 0 |
| capacity | 容量望抽，即為HashMap中數(shù)組的長(zhǎng)度,table.length | 無(wú)直接此變量加矛，數(shù)組的默認(rèn)長(zhǎng)度為16 |
附上源碼：
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* An empty table instance to share when the table is not inflated.
*/
static final Entry<?,?>[] EMPTY_TABLE = {};
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE; //Entry類(lèi)型的數(shù)組，hashMap的內(nèi)部數(shù)據(jù)結(jié)構(gòu)
/**
* The number of key-value mappings contained in this map.
*/
transient int size;
/**
* The next size value at which to resize (capacity * load factor).
*/
// If table == EMPTY_TABLE then this is the initial capacity at which the
// table will be created when inflated.
int threshold;
/**
* The load factor for the hash table.
*/
final float loadFactor;
/**
* The number of times this HashMap has been structurally modfied
* Structural modifications are those that change the number of mappings in
* the HashMap or otherwise modify its internal structure (e.g.,
* rehash). This field is used to make iterators on Collection-views of
* the HashMap fail-fast. (See ConcurrentModificationException).
*/
transient int modCount;
// These methods are used when serializing HashSets
int capacity() { return table.length; }
float loadFactor() { return loadFactor; }
3.數(shù)據(jù)結(jié)構(gòu)
??由上面的源碼我們得知煤篙，HashMap的內(nèi)部結(jié)構(gòu)為一個(gè)Entry類(lèi)型的數(shù)組斟览，它的數(shù)據(jù)結(jié)構(gòu)如下圖所示：
HashMap數(shù)據(jù)結(jié)構(gòu) 圖片來(lái)自網(wǎng)絡(luò)
Entry數(shù)據(jù)結(jié)構(gòu)如下：
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
....
}
4.構(gòu)造函數(shù)
HashMap提供了3個(gè)構(gòu)造函數(shù)，如下：
| 方法 | 釋義 |
|---|---|
| HashMap() | 無(wú)參構(gòu)造辑奈，默認(rèn)容量(capacity)為16,默認(rèn)負(fù)載因子為0.75f |
| HashMap(int initialCapacity) | 初始化數(shù)組長(zhǎng)度,默認(rèn)負(fù)載因子為0.75f |
| HashMap(int initialCapacity, float loadFactor) | 初始化數(shù)組長(zhǎng)度和負(fù)載因子 |
注意：調(diào)用HashMap的構(gòu)造函數(shù)時(shí)苛茂，并沒(méi)有去初始化內(nèi)部結(jié)構(gòu)table的大小，只是給成員變量賦值了鸠窗。
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();
}
5.方法解讀
5.1 put()方法
public V put(K key, V value) {
if (table == EMPTY_TABLE) { //構(gòu)造函數(shù)的時(shí)候妓羊，并沒(méi)有去操作table，故第一次put的時(shí)候稍计，table就為默認(rèn)值EMPTY_TABLE
inflateTable(threshold); //初始化table侍瑟，初始化的table長(zhǎng)度一定時(shí)2的冪次。
}
if (key == null) //判斷插入的值是否為null丙猬，如果為null的化涨颜，則調(diào)用插入key為null的方法
return putForNullKey(value);
int hash = hash(key); //獲取key的hash值，如果key對(duì)應(yīng)的類(lèi)類(lèi)型重寫(xiě)了hashCode()方法茧球，則會(huì)調(diào)用
int i = indexFor(hash, table.length); //獲取這個(gè)key位于那個(gè)hash桶(即數(shù)組的坐標(biāo))
for (Entry<K,V> e = table[i]; e != null; e = e.next) { //如果有存在相同key的庭瑰，則將其value覆蓋。
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++; //變更次數(shù)加1
addEntry(hash, key, value, i); //添加數(shù)據(jù)到Entry[]中
return null;
}
- 構(gòu)造函數(shù)部分抢埋，我們講到調(diào)用構(gòu)造函數(shù)的時(shí)候弹灭，并沒(méi)有去操作內(nèi)部的Entry數(shù)組督暂。從put方法里，我們看到了是在第一次put數(shù)據(jù)的時(shí)候才去new Entry[] table穷吮。
- 我們可以看到逻翁，如果map中存在相同key值的時(shí)候，對(duì)應(yīng)的value會(huì)被覆蓋捡鱼。由此可得出HashMap可允許有且僅有一個(gè)key為null八回。
- 不可忽視的一點(diǎn)：獲取數(shù)組下標(biāo)：int i = indexFor(hash, table.length);
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的底層數(shù)組長(zhǎng)度總是2的n次方，h&(length - 1)就相當(dāng)于對(duì)length取模驾诈，而且速度比直接取牟纾快得多，這是HashMap在速度上的一個(gè)優(yōu)化乍迄。綜合起來(lái)數(shù)據(jù)分布也相對(duì)更均勻管引。更多了解，請(qǐng)參考：http://www.cnblogs.com/chenssy/p/3521565.html
- 需要擴(kuò)展的一點(diǎn)：代碼中會(huì)調(diào)用key.hashCode()和key.equals(k)闯两；類(lèi)的hashCode()方法和equal()方法褥伴，在map的使用中有很重要的作用，所以常說(shuō)如果重寫(xiě)equal方法的時(shí)候漾狼，必須重寫(xiě)hashCode方法噩翠。大家可以參考http://www.reibang.com/p/75d9c2c3d0c1
添加元素方法addEntry()
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);
}
??我們先看下createEntry方法，如下邦投。可以看到createEntry就是采用鏈表的頭插法新增一個(gè)Entry擅笔。
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex]; //獲取當(dāng)前hash桶中得值
table[bucketIndex] = new Entry<>(hash, key, value, e); //new 一個(gè)key-value對(duì)應(yīng)得Entry數(shù)組志衣，并將new的Entry的next指向原來(lái)hash桶的值，并賦值給hash桶
size++;
}
??我們?cè)賮?lái)看看resize的部分猛们，當(dāng)map中存儲(chǔ)的數(shù)據(jù)大于等于map設(shè)定的閥值念脯，且當(dāng)前hash桶中也有值時(shí)，就會(huì)進(jìn)行擴(kuò)容弯淘。擴(kuò)容每次都是以2倍的長(zhǎng)度擴(kuò)展的绿店。
void resize(int newCapacity) { //傳入新的數(shù)組容量
Entry[] oldTable = table; //引用老的數(shù)組
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) { //判斷原數(shù)組容量是否已經(jīng)超過(guò)了最大值
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity]; //初始化一個(gè)新的數(shù)組
transfer(newTable, initHashSeedAsNeeded(newCapacity)); //將原數(shù)組的數(shù)據(jù)移動(dòng)到新數(shù)組中
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); //更新map的存儲(chǔ)閥值
}
移動(dòng)數(shù)據(jù)方法：transfer()
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
閱讀后，我們發(fā)現(xiàn)庐橙，如果移動(dòng)后還是在一個(gè)hash桶中假勿，順序相對(duì)于之前是顛倒的。
5.2 get()方法
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
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;
}
get方法比較簡(jiǎn)單态鳖，首先根據(jù)key找到對(duì)應(yīng)的hash桶转培，然后在遍歷查找。
5.3 remove()方法
final Entry<K,V> removeEntryForKey(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
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--;
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}
remove方法的本質(zhì)就是浆竭，找到hash桶之后浸须，使用單向鏈表的刪除方法惨寿。
6.modcount分析
??簡(jiǎn)言之就是，用來(lái)實(shí)現(xiàn)“fail-fast”機(jī)制的（也就是快速失斏局稀）裂垦。所謂快速失敗就是在并發(fā)集合中，其進(jìn)行迭代操作時(shí)肌索，若有其他線程對(duì)其進(jìn)行結(jié)構(gòu)性的修改蕉拢，這時(shí)迭代器會(huì)立馬感知到，并且立即拋出ConcurrentModificationException異常驶社，而不是等到迭代完成之后才告訴你（你已經(jīng)出錯(cuò)了）企量。
7.HashMap存在的問(wèn)題？
- 線程安全問(wèn)題：多線程情況下亡电，在擴(kuò)容的時(shí)候届巩，可能會(huì)形成循環(huán)鏈表，可參考：
https://www.cnblogs.com/RGogoing/p/5285361.html
http://blog.csdn.net/aichuanwendang/article/details/53317351
