APP
一、HashMap底層實(shí)現(xiàn)
HashMap底層結(jié)構(gòu)：數(shù)組+鏈表+紅黑樹(shù)
Java中的HashMap是以鍵值對(duì)(key-value)的形式存儲(chǔ)元素的。HashMap需要一個(gè)hash函數(shù)，它使用hashCode()和equals()方法來(lái)向集合/從集合添加和檢索元素。當(dāng)調(diào)用put()方法的時(shí)候，HashMap會(huì)計(jì)算key的hash值，然后把鍵值對(duì)存儲(chǔ)在集合中合適的索引上。如果key已經(jīng)存在了，value會(huì)被更新成新值
HashMap的一些重要的特性是它的容量(capacity)，負(fù)載因子(load factor)和擴(kuò)容極限(threshold resizing)
二、初始化HashMap
源碼： 三種構(gòu)造函數(shù)
//initialCapacity：初始化大小，loadFactor:加載因子
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0) {
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
} else {
if (initialCapacity > 1073741824) {
initialCapacity = 1073741824;
}
if (loadFactor > 0.0F && !Float.isNaN(loadFactor)) {
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
} else {
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
}
}
}
public HashMap(int initialCapacity) {
this(initialCapacity, 0.75F);
}
public HashMap() {
this.loadFactor = 0.75F;
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = 0.75F;
this.putMapEntries(m, false);
}
?
默認(rèn)值大小
private static final long serialVersionUID = 362498820763181265L;
static final int DEFAULT_INITIAL_CAPACITY = 16;//HashMap的默認(rèn)容量，16;
static final int MAXIMUM_CAPACITY = 1073741824;//最大容量
static final float DEFAULT_LOAD_FACTOR = 0.75F;//默認(rèn)加載因子 0.75
static final int TREEIFY_THRESHOLD = 8;//Bucket中鏈表長(zhǎng)度大于該默認(rèn)值，轉(zhuǎn)化為紅黑樹(shù) 8
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
三、put操作
public V put(K key, V value) { if (table == EMPTY_TABLE) { inflateTable(threshold); } // 鍵為 null 單獨(dú)處理 if (key == null) return putForNullKey(value); int hash = hash(key); // 確定桶下標(biāo) int i = indexFor(hash, table.length); // 先找出是否已經(jīng)存在鍵為 key 的鍵值對(duì)，如果存在的話就更新這個(gè)鍵值對(duì)的值為 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++; // 插入新鍵值對(duì) addEntry(hash, key, value, i); return null; }
?
四、擴(kuò)容原理
//判斷增加元素后的容量是否大于老容量
if (++this.size > this.threshold) {
this.resize();
}
final HashMap.Node<K, V>[] resize() {
HashMap.Node<K, V>[] oldTab = this.table;
int oldCap = oldTab == null ? 0 : oldTab.length;
int oldThr = this.threshold;
int newThr = 0;//臨界值=capacity*loadfactor
int newCap;
if (oldCap > 0) {
//如果容量大于最大容量，將threshold改為2倍的容量-1
if (oldCap >= 1073741824) {
this.threshold = 2147483647;
return oldTab;
}
//如果新容量的2倍還是小于最大容量，或者容量小于16容量就翻二倍
if ((newCap = oldCap << 1) < 1073741824 && oldCap >= 16) {
newThr = oldThr << 1;
}
} else if (oldThr > 0) {
newCap = oldThr;
} else {
newCap = 16;
newThr = 12;
}return newTab;
}
?
總結(jié)：
HashMap的擴(kuò)容機(jī)制：當(dāng)`hashmap`被初始化創(chuàng)建的時(shí)候容量為16，由于初始化的加載因子的值為0.75，所以在集合大小為16*0.75=12的時(shí)候開(kāi)始進(jìn)行擴(kuò)容，擴(kuò)容的大小為當(dāng)前集合的大小的2倍，也就是32，下一次集合大小為32*0.75=24時(shí)開(kāi)始擴(kuò)容.....
在Java8中，如果一條鏈表的元素個(gè)數(shù)超過(guò)樹(shù)化閾值(默認(rèn)是8)，并且集合的大小>=閾值(默認(rèn)64)，就會(huì)進(jìn)行樹(shù)化（紅黑樹(shù)）
?
本文摘自 ：https://www.cnblogs.com/
