溫馨提示×
您好，登錄后才能下訂單哦！
點(diǎn)擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
Jdk 1.7
數(shù)據(jù)結(jié)構(gòu)
1.7版本的HashMap采用數(shù)組加鏈表的方式存儲數(shù)據(jù),數(shù)組是用來存儲數(shù)據(jù)的在數(shù)組的位置,鏈表則時用來存放數(shù)據(jù)的,由于根據(jù)hash可能發(fā)生碰撞,一個位置會出現(xiàn)多個數(shù)據(jù),所以采用鏈表結(jié)構(gòu)來存儲數(shù)據(jù),結(jié)構(gòu)如下圖所示.
基本成員變量
capacity 數(shù)組的長度
// 當(dāng)前數(shù)組的容量,始終保持2^n,可以擴(kuò)容,擴(kuò)容后是當(dāng)前線程的2倍
// 1 << 4 = 1 * 2^4 1的二進(jìn)制左移4位
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16capacity 的最大值 (擴(kuò)容時,如果已經(jīng)是最大值,會設(shè)置成Integer.MAX_VALUE)
// 如果傳入的值大于該值,也會替換為 1 << 30(2 ^ 30)
static final int MAXIMUM_CAPACITY = 1 << 30;factor 負(fù)載因子(用來算閾值)
// 負(fù)載因子 默認(rèn)值為 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;threshold 閾值(capacity * factor),擴(kuò)容時用來判斷有沒有大于等于這個值int threshold;
size
// map的容量
transient int size;Entry (存儲數(shù)據(jù)的地方)
static class Entry<K,V> implements Map.Entry<K,V> {
// 就是傳輸key
final K key;
// 就是value
V value;
// 用于指向單項鏈表的下一個Entry
Entry<K,V> next;
// 通過key計算的hash值
int hash;
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}構(gòu)造方法
有參構(gòu)造
public HashMap(int initialCapacity, float loadFactor) {
// 容量不能小于0
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
// 容量大于MAXIMUM_CAPACITY時,等于MAXIMUM_CAPACITY
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// loadFactor不能小于等于0
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
threshold = initialCapacity;
init();
}無參構(gòu)造
// 使用默認(rèn)的容量和負(fù)載因子
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}基本方法
Put方法 (具體流程看下面的執(zhí)行流程分析或者代碼注釋)
具體執(zhí)行流程:
(1) 判斷當(dāng)前table是否為EMPTY_TABLE={},證明沒有初始化,調(diào)用inflateTable初始化,具體詳見后面inflateTable()方法代碼分析.
(2) 判斷key是否為null,是null調(diào)用putForNullKey插入方法(證明1.7的HashMap允許key為null),具體詳見后面putForNullKey()方法代碼分析.
(3) 獲取當(dāng)前key的hash,然后算出hash在數(shù)組的位置i(hash & (tab.length - 1)).給大家解釋下為什么數(shù)組的長度必須是2的冥,是和算i的位置有關(guān)系,因為如果一個數(shù)是2的冥次方,假如這個數(shù)是n,那么 hash % n = hash & (n -1),這就是為什么i的位置一定會在數(shù)組長度范圍中,因為取得是余數(shù),還有就是位運(yùn)算比直接取余效率高.
(4) 判斷當(dāng)前位置上有沒有值table[i],如果有值,遍歷鏈表,找出相同的key和hash,然后替換value,返回舊的value(oldOvalue).
(5) 如果沒有找到相同的key和hash,那么就添加這個節(jié)點(diǎn)(Entry),方法addEntry().
(6) 在addEntry()方法里面判斷需不需擴(kuò)容,需要就擴(kuò)容,調(diào)用擴(kuò)容方法resize(),然后在調(diào)用 createEntry()方法添加節(jié)點(diǎn),size++.
// 插入
public V put(K key, V value) {
// 當(dāng)插入第一個元素時,需要初始化
if (table == EMPTY_TABLE) {
// 初始化
inflateTable(threshold);
}
// key為null是
if (key == null)
// 找出key為null,替換返回舊值
// 沒有則新添加一個key為null的Entry
return putForNullKey(value);
// 計算hash值
int hash = hash(key);
// 根據(jù)hash,找出table的位置
int i = indexFor(hash, table.length);
// 因為在table[i]中,可能存在多個元素(同一個hash),所以要基于鏈表實現(xiàn)
// 循環(huán)table[i]上的鏈表(不為空),存在就修改,返回舊值(oldValue)
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++;
// 為空或者不存在,則新添加(需要計算容量)
addEntry(hash, key, value, i);
return null;
}inflateTable初始化方法 (懶加載,只有第一次調(diào)用put方法時才初始化)
// 初始化table
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
// 計算出大于等于toSize最鄰近的2^n(所以capacity一定是2^n)
int capacity = roundUpToPowerOf2(toSize);
// 在此計算閾值 capacity * loadFactor
threshold = (int) Math.min(capacity * loadFactor,
MAXIMUM_CAPACITY + 1);
// 創(chuàng)建capacity大小的capacity數(shù)組就是hashmap的容器
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}putForNullKey方法(存儲key為null的數(shù)據(jù))
具體執(zhí)行流程:
(1) 遍歷table[0]處的鏈表(說明nullkey永遠(yuǎn)存在table[0]位置)
(2) 找到key==null 的數(shù)據(jù),替換value,返回舊的value
(3) 沒有找到,就在table[0]位置添加一個key為null的Entry,調(diào)用addEntry()方法.
private V putForNullKey(V value) {
// 遍歷table[0]的鏈表
// 找到key等于null的,把值覆蓋,返回舊值(oldValue)
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++;
// 沒有找到就添加一個key為null的Entry
addEntry(0, null, value, 0);
return null;
}addEntry方法(判斷是否需要擴(kuò)容,然后在添加節(jié)點(diǎn)Entry)
執(zhí)行流程:
(1) 判斷是否需要擴(kuò)容,size(每次添加一個entry size++)>=threshold(閾值)并且當(dāng)前這個key的hash算出的位置必須有元素才擴(kuò)容,具體詳解看代碼注釋.
(2) 如果滿足擴(kuò)容條件,調(diào)用擴(kuò)容方法resize(2 * table.length),table長度擴(kuò)大2倍,然后重新算當(dāng)前key的hash和位置bucketIndex.
(3) 調(diào)用createEntry()方法,添加節(jié)點(diǎn).
// 添加節(jié)點(diǎn)到鏈表
void addEntry(int hash, K key, V value, int bucketIndex) {
/*
* 擴(kuò)容機(jī)制必須滿足兩個條件
* (1) size大于等于了閾值
* (2) 到達(dá)閾值的這個值有沒有發(fā)生hash碰撞
* 所以閾值在默認(rèn)情況下是12 是一個重要節(jié)點(diǎn)
* 擴(kuò)容范圍是12-27
* 最小12進(jìn)行擴(kuò)容,最大27時必須進(jìn)行擴(kuò)容
* 分析最小12擴(kuò)容
* 當(dāng)size是12時,判斷有沒有hash碰撞,有擴(kuò)容,沒有繼續(xù)不擴(kuò)容.
* 分析最大27擴(kuò)容
* 當(dāng)12沒有進(jìn)行擴(kuò)容時,size大于閾值就一直滿足了
* 就只需要判斷接下來的hash有沒碰撞,有就擴(kuò)容,沒有就不擴(kuò)容
* 最大是一種極端情況,前面11個全部在一個table索引上,接下來
* 15個全部沒有碰撞,11+15=26,table所有索引全部有值,在插入一個
* 值必須碰撞就是26+1=27最大進(jìn)行擴(kuò)容
* */
if ((size >= threshold) && (null != table[bucketIndex])) {
// 擴(kuò)容(方法里面重點(diǎn)講)
resize(2 * table.length);
// 計算hash,null時為0
hash = (null != key) ? hash(key) : 0;
// 計算位置
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}createEntry方法(在傳入位置加入一個節(jié)點(diǎn))
// 創(chuàng)建一個新的Entry,放在鏈表的表頭,size++
void createEntry(int hash, K key, V value, int bucketIndex) {
// 這里可以理解為當(dāng)前的第一個節(jié)點(diǎn)
Entry<K,V> next = table[bucketIndex];
// 創(chuàng)建一個新的節(jié)點(diǎn),next節(jié)點(diǎn)是當(dāng)前的第一個節(jié)點(diǎn),然后設(shè)置到bucketIndex位置
table[bucketIndex] = new Entry<>(hash, key, value, next);
size++;
}resize方法(擴(kuò)容方法,擴(kuò)容成原來的2倍)
執(zhí)行流程:
(1) 計算oldTable的長度,如果oldTable的長度已經(jīng)是最大值了,那么就把閾值設(shè)置成Integer.MAX_VALUE,return.
(2) 根據(jù)新的容量創(chuàng)建table.
(3) 調(diào)用transfer方法轉(zhuǎn)移數(shù)據(jù).
(4) 將新table賦值給舊table,重新就算閾值.
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
// 如果當(dāng)前值已經(jīng)是最大值了(2^30),就設(shè)置閾值為Integer的最大值
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// 根據(jù)傳入Capacity重新創(chuàng)建新數(shù)組,擴(kuò)容完成
Entry[] newTable = new Entry[newCapacity];
// 把原來的數(shù)據(jù)遷移到新的table(newTable)
transfer(newTable, initHashSeedAsNeeded(newCapacity));
// 將table設(shè)為新table(newTable)
table = newTable;
// 設(shè)置新的閾值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}transfer方法(負(fù)載轉(zhuǎn)移數(shù)據(jù),把舊table的數(shù)據(jù)遷移到新table,至此擴(kuò)容完成)
注意:擴(kuò)容完成后鏈表的順序會反轉(zhuǎn),如下圖解釋.
// 擴(kuò)容之后遷移數(shù)據(jù)(重新計算hash,分配地址),很耗性能
// 順便提一下jdk7(get死循環(huán))就是擴(kuò)容時造成,造成環(huán)形鏈表
void transfer(Entry[] newTable, boolean rehash) {
// 新數(shù)組的容量
int newCapacity = newTable.length;
// 遍歷原table
for (Entry<K,V> e : table) {
// 輪詢e不等于null
while(null != e) {
// 保存下個元素
Entry<K,V> next = e.next;
if (rehash) {
// 計算出key的hash
e.hash = null == e.key ? 0 : hash(e.key);
}
// 計算出table的位置
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}get方法(通過key獲取數(shù)據(jù))
執(zhí)行流程:
(1) 判斷key是否為null,為null調(diào)用getForNullKey()方法
(2) 不為null,調(diào)用getEntry方法
// get方法
public V get(Object key) {
// key等于null
if (key == null)
return getForNullKey();
// 不為null是查找
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}getForNullKey()方法(遍歷table[0]位置數(shù)據(jù),找到key==null的返回)
private V getForNullKey() {
// 沒數(shù)據(jù)
if (size == 0) {
return null;
}
// 從table[0]處遍歷鏈表,找到key=null的返回
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}getEntry()方法(根據(jù)hash算出位置,遍歷當(dāng)前位置的數(shù)據(jù),找到key和hash相同的返回)
final Entry<K,V> getEntry(Object key) {
// 沒數(shù)據(jù)
if (size == 0) {
return null;
}
// 獲取hash
int hash = (key == null) ? 0 : hash(key);
// 獲取table的位置,找到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;
}remove()方法
final Entry<K,V> removeEntryForKey(Object key) {
// 沒數(shù)據(jù)
if (size == 0) {
return null;
}
// 獲取hash
int hash = (key == null) ? 0 : hash(key);
// 計算位置
int i = indexFor(hash, table.length);
// 獲取i位置的entry
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
// 遍歷鏈表
while (e != null) {
Entry<K,V> next = e.next;
Object k;
// 找到了hash和key相等的
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
// 容量減減
size--;
// 說明是第一個元素
// 把頭結(jié)點(diǎn)設(shè)置成他的下一個元素
if (prev == e)
table[i] = next;
// 刪除當(dāng)前e,把上一個元素的next指向當(dāng)前e.next
// 1 -2 -3-null 刪除2,把1的next指向2的next,就是1-3-null
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}1.7HashMap需要注意的是在擴(kuò)容時,不是到達(dá)閾值就會擴(kuò)容的,還要判斷當(dāng)前位置是否有值,來決定會否擴(kuò)容,還有就是擴(kuò)容的時候是遍歷了每個位置的鏈表,重新計算hash和位置,然后插入新的table,每條鏈的順序是和原來相反的,這樣如果數(shù)據(jù)量很大,其實很消耗性能.還有就是采用鏈表的數(shù)據(jù)結(jié)構(gòu)來存儲數(shù)據(jù),如果hash碰撞嚴(yán)重的話,這條鏈就會很長,這樣不管是get,或者put都需要遍歷鏈,這樣也遍歷也很慢,這是1.7HashMap個人覺得一些缺陷吧(因為看了1.8 HashMap 源碼淺析).
PS 1.7的HashMap在多線程下擴(kuò)容會導(dǎo)致環(huán)鏈,然后導(dǎo)致再次遍歷鏈表的時候回是死循環(huán),進(jìn)而cpu100%,所以多線程下就不要用HashMap.
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進(jìn)行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號
手機(jī)網(wǎng)站二維碼