HashMap各個(gè)方法的源碼

put方法

首先分析第一個(gè)比較重要的方法 put 方法，源碼如下

public V put(K key, V value) {
if (key == null)
return putForNullKey(value);  //這里判斷key是否為空,若為空則調(diào)用putForNullKey處理null值
int hash = hash(key); //根據(jù)key的hashCode計(jì)算hash值
int i = indexFor(hash, table.length);//搜索該key的hash值在table中的索引,其中table是當(dāng)HashMap用于存放entry的一個(gè)數(shù)組
//這里循環(huán)遍歷table中對(duì)應(yīng)該索引的entry，若發(fā)現(xiàn)存在key與put進(jìn)來(lái)的key相同則覆蓋其value值
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++;
//將key value 添加到 索引i處
addEntry(hash, key, value, i);
return null;
}

分析上面的源碼，我們可以得到下面的結(jié)論:

當(dāng)我們?cè)噲D將一個(gè)key-value 調(diào)用put方法放入HashMap的時(shí)候，首先會(huì)調(diào)用key的hashCode方法算出該Entry存放的位置，若兩個(gè)key的hashCode相同則在table中的存儲(chǔ)位置相同，則先調(diào)用equals方法判斷兩個(gè)key是否相同，相同則覆蓋，不相同則產(chǎn)生一個(gè)Entry鏈表(因?yàn)閠able數(shù)組中一個(gè)索引位置只能放入一個(gè)Entry，所以當(dāng)有多個(gè)key的hashCode相同時(shí)，這些key就會(huì)以鏈表的形式存在，并且最后put進(jìn)來(lái)的key在鏈表的最前面)

構(gòu)造方法

然后則是HashMap的構(gòu)造方法，這里以 HashMap(int initialCapacity, float loadFactor)這個(gè)構(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)
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();
}

從上面的源碼可以看出 ，初始容量不能為負(fù)數(shù)，若初始容量大于最大容量，則讓它等于最大容量，負(fù)載因子必須大于0，并且傳入的initialCapacity不是HashMap的容量大小，

實(shí)際容量大小的計(jì)算規(guī)則是大于傳入的initialCapacity的最小的2的n次方，比如傳入的initialCapacity是5 那么實(shí)際容量則是8 因?yàn)?的3次方大于5。

get方法

下面再分析一下HashMap的存儲(chǔ)性能，下面的 get方法的源碼

public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
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;
}

再次強(qiáng)調(diào)一下table的概念，table就是當(dāng)我們初始化一個(gè)HashMap時(shí)，會(huì)自動(dòng)創(chuàng)建一個(gè)長(zhǎng)度為capacity的Entry數(shù)組，我們把這個(gè)數(shù)組存放元素的位置叫“桶”，并且每個(gè)桶只存儲(chǔ)一個(gè)Entry元素(也就是我們的鍵值對(duì))，并且當(dāng)我們put一個(gè)鍵值對(duì)時(shí)，先計(jì)算key的hashCode來(lái)判斷這個(gè)鍵值對(duì)會(huì)放入哪一個(gè)桶，所以若多個(gè)key的hashCode相同時(shí)，他們都要被放入一個(gè)桶里面，但是一個(gè)桶里面只能放入一個(gè)Entry(鍵值對(duì))，要解決這個(gè)問(wèn)題先看下面的代碼

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

這是Entry的構(gòu)造方法，我們可以看出Entry對(duì)象包含一個(gè)Entry的引用，用來(lái)指向下一個(gè)Entry，這樣就解決了hashCode相同，存放沖突的問(wèn)題，所以當(dāng)有多個(gè)key的hashCode相同時(shí)，就會(huì)形成一個(gè)Entry鏈，我們從get方法可以看出當(dāng)系統(tǒng)通過(guò)key的hashCode找到了對(duì)應(yīng)的桶的時(shí)候，會(huì)遍歷這個(gè)Entry鏈，來(lái)找到我們要取的value的key

這個(gè)時(shí)候，若剛好這個(gè)Entry在鏈表的末端(也就是我們最開(kāi)始put進(jìn)去的Entry)那么當(dāng)這個(gè)鏈表太長(zhǎng)了，勢(shì)必會(huì)影響我們的查詢(xún)性能，這個(gè)時(shí)候就引出了loadFactor(負(fù)載因子的說(shuō)法)，HashMap的默認(rèn)附在因子是0.75

我對(duì)負(fù)載因子的理解就是，表示HashMap在什么時(shí)候擴(kuò)容，也就是說(shuō)若我們初始的HashMap容量是16 負(fù)載因子是0.75

那么當(dāng)有12個(gè)“桶”有了Entry時(shí)，HashMap就會(huì)擴(kuò)容，并且擴(kuò)大的容量是原來(lái)容量的2倍，為什么是12呢？因?yàn)?.75x16=12。

并且負(fù)載因子是可以更改的，修改它的前提是如果內(nèi)存比較緊張就可以適當(dāng)?shù)脑黾迂?fù)載因子

若空間，內(nèi)存比較充足，更關(guān)注查詢(xún)效率則減少負(fù)載因子。為什么會(huì)這樣呢？因?yàn)槿糌?fù)載因子減少了，比如說(shuō)減少到了0.5，默認(rèn)HashMap容量大小還是16

那么當(dāng)我有8個(gè)"桶"中存放了Entry數(shù)組時(shí)我就會(huì)擴(kuò)容了，該桶里的Entry鏈相比于之前就不會(huì)那么長(zhǎng)，從而提升了查詢(xún)性能。

到此這篇關(guān)于深入理解HashMap各個(gè)方法的源碼的文章就介紹到這了,更多相關(guān)HashMap方法的源碼內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論