一、HashMap成員變量
/** 初始容量,預設16 =2^4*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/** 最大初始容量,2^30 */
static final int MAXIMUM_CAPACITY = 1 << 30;
/** 負載因子,預設0.75,負載因子越小,hash沖突機率越低 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/** 初始化一個Entry的空數組 */
static final Entry<?,?>[] EMPTY_TABLE = {};
/** 将初始化好的空數組指派給table,table數組是HashMap實際存儲資料的地方,并不在EMPTY_TABLE數組中 */
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
/** HashMap實際存儲的元素個數 */
transient int size;
/** 臨界值(HashMap 實際能存儲的大小),公式為(threshold = capacity * loadFactor) */
int threshold;
/** 負載因子 */
final float loadFactor;
/** HashMap的結構被修改的次數,用于疊代器 */
transient int modCount;
二、構造方法
HashMap實作了Map接口,繼承AbstractMap。其中Map接口定義了鍵映射到值的規則,而AbstractMap類提供 Map 接口的骨幹實作。
/**
* 構造一個空的HashMap,預設容器初始化大小為16,預設負載因子0.75
*/
public HashMap() {
//this(預設初始容量(16),預設負載因子(0.75));
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity) {
//this(定的初始容量,預設負載因子(0.75));
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
// 判斷設定的容量和負載因子合不合理
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
初始容量不能 > 最大容量值,HashMap的最大容量值為2^30
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// 負載因子不能 < 0
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// 設定負載因子,臨界值此時為容量大小,後面第一次put時由inflateTable(int toSize)方法計算設定
this.loadFactor = loadFactor;
threshold = initialCapacity;
init();
}
三、Entry
每次初始化HashMap都會構造一個table數組,而table數組的元素為Entry節點。
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
}
HashMap也可以說是一個數組連結清單,HashMap裡面有一個非常重要的内部靜态類——Entry,這個Entry非常重要,它裡面包含了鍵key,值value,下一個節點next,以及hash值,Entry是HashMap非常重要的一個基礎Bean,因為所有的内容都存在Entry裡面,HashMap的本質可以了解為 Entry[ ] 數組。
四、put()方法
public V put(K key, V value) {
if (table == EMPTY_TABLE) { //是否初始化
inflateTable(threshold);
}
//當key為null,調用putForNullKey方法,儲存null與table第一個` 位置中,這是HashMap允許為null的原因
if (key == null)
return putForNullKey(value);
//計算key的hash值
int hash = hash(key.hashCode()); ------(1)
//計算key hash 值在 table 數組中的位置
int i = indexFor(hash, table.length); ------(2)
//從i出開始疊代 e,找到 key 儲存的位置
for (Entry<K, V> e = table[i]; e != null; e = e.next) {
Object k;
//判斷該條鍊上是否有hash值相同的(key相同)
//若存在相同,則直接覆寫value,傳回舊value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value; //舊值 = 新值
e.value = value;
e.recordAccess(this);
return oldValue; //傳回舊值
}
}
//修改次數增加1
modCount++;
//将key、value添加至i位置處
addEntry(hash, key, value, i);
return null;
}
putForNullKey()方法:
private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}
直接去周遊table[0] Entry連結清單,找出e.key==null的Entry或者沒有找到周遊結束
如果找到了e.key等于null的值就儲存null值對應的原值oldValue,然後覆寫原值,并傳回oldValue
如果在table[0]Entry連結清單中沒有找到就調用addEntry方法添加一個key為null的Entry
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);
}
resize()方法
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
createEntry()方法
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
添加到方法的具體操作,在添加之前先進行容量的判斷,如果目前容量達到了門檻值,并且需要存儲到Entry[]數組中,先進性擴容操作,空充的容量為table長度的2倍。重新計算hash值,和數組存儲的位置,擴容後的連結清單順序與擴容前的連結清單順序相反。然後将新添加的Entry實體存放到目前Entry[]位置連結清單的頭部。在1.8之前,新插入的元素都是放在了連結清單的頭部位置,但是這種操作在高并發的環境下容易導緻死鎖,是以1.8之後,新插入的元素都放在了連結清單的尾部。
五、get()/put()方法
詳情點選下方
HashMap之get()方法詳細解析
HashMap之put()方法詳細解析