HashMap jkd1.7解讀
一.思路
我們都知道hashmap是一個(gè)查詢快速乔妈，的一個(gè)內(nèi)存容器，
設(shè)置思想：數(shù)組+鏈表
我用一個(gè)數(shù)組
[{1},{2},{3}]
-
那么我如何隨機(jī)的讓一個(gè)map來(lái)分散的插入數(shù)組中氓皱，
? 我們需要用key來(lái)計(jì)算一個(gè)隨機(jī)數(shù)：int code = key.hashcode(),這個(gè)我們都知道路召，那么這個(gè)生成的數(shù)字很大贮懈，我們想要生成一個(gè)索引的方法，很簡(jiǎn)單就是去摸：int index = code %entry[].length
最后entry【index】 = enrye<key优训，value>
-
接著我們來(lái)思考下一個(gè)問(wèn)題：如果數(shù)組對(duì)應(yīng)的索引上面有元素朵你，我們?cè)撛趺崔k？
那么就是使用我們的鏈表
- 什么是鏈表揣非，最簡(jiǎn)單的就是我的linkedlist抡医，我的對(duì)象了存儲(chǔ)了下一個(gè)節(jié)點(diǎn)的地址或者引用，那么hashmap中的entry對(duì)象就是這樣的一個(gè)對(duì)象早敬，一旦有新的值插入map忌傻，計(jì)算出的位置上已經(jīng)有元素了，那么就這樣的一個(gè)操作搞监，想將我們這個(gè)元素new entry（）水孩，在放在table上table【index】= new entry,還要把已經(jīng)擁有的這個(gè)鏈表上的第一個(gè)元素的整體向下移動(dòng)
- table[index] = new entry(index,code,table[i]=next)
二.put方法
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
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;
}
1.inflateTable(threshold);初始話,初始化什么呢
private void inflateTable(int toSize) { // Find a power of 2 >= toSize int capacity = roundUpToPowerOf2(toSize); threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); table = new Entry[capacity]; initHashSeedAsNeeded(capacity); }
Find a power of 2 >= toSize的意思是找打,一個(gè)比toSize大的2的冪次方的數(shù)
那么來(lái)看roundUpToPowerOf2(toSize);方法
private static int roundUpToPowerOf2(int number) { // assert number >= 0 : "number must be non-negative"; return number >= MAXIMUM_CAPACITY ? MAXIMUM_CAPACITY : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1; }
這個(gè)方法最主要是看
Integer.highestOneBit((number - 1) << 1)
那么我們通過(guò)自己的測(cè)驗(yàn),可以得出highestOneBit(int i)方法時(shí)幫我們找到比i小的二的冪次方的數(shù),那么如何做的呢,繼續(xù)往下看
public static int highestOneBit(int i) {
// HD, Figure 3-1
i |= (i >> 1);
i |= (i >> 2);
i |= (i >> 4);
i |= (i >> 8);
i |= (i >> 16);
return i - (i >>> 1);
}
我們看到了是通過(guò)位運(yùn)算來(lái)計(jì)算的,然后通過(guò)方法名字我們大概可以知道,這個(gè)方法時(shí)拿到我們這個(gè)數(shù)字的最高位是一對(duì)應(yīng)的那個(gè)數(shù)字,重點(diǎn)來(lái)了,最高位為1,其他為0(負(fù)數(shù)除外),這個(gè)數(shù)字正好是二的冪次方,這個(gè)算法的思路大概就是把最高位的數(shù)字1,慢慢的向右移,然后在或運(yùn)算,
- i |= (i >> 1);這個(gè)方法10:0000 1010,想右移一位 0000 0101,在做或運(yùn)算,0000 1111 ,看這個(gè)就把高位的1(因?yàn)樽罡呶坏囊欢ㄊ且粋€(gè)1),然后使得最高位的后一位保證變?yōu)?,
- 因?yàn)槲覀冎乐纈nt是32位的數(shù)字,所有需要繼續(xù)移動(dòng),那么最高位是1,后一位也是1,所有第二部是在替換后面的2位為1,以此類推
- 最后沒(méi)一定可以得到一個(gè)從源數(shù)據(jù)的的最高位開(kāi)始后面全部為1的數(shù)據(jù),那么將這個(gè)數(shù)向后移動(dòng)一位,我們一定可以得到一個(gè)除最高位為1外,其他為全部為0的而精致數(shù)(裝換過(guò)來(lái),也就是一個(gè)二的冪次方的數(shù))
那么我們現(xiàn)在需要的是講個(gè)數(shù)字變大,但是又不能打過(guò)下個(gè)2的冪次方的數(shù),及8<10<16,那么我們的變大需要變成的這個(gè)x的范圍是 16<x<32,所有我們需要向左移動(dòng)一位,這個(gè)就可以得到了.
Integer.highestOneBit((number - 1) << 1)
至于這個(gè)-1是用來(lái)處理特殊數(shù)據(jù)的,比如說(shuō)8,16這些
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize);
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}
在回頭來(lái)看這個(gè)方法，我們的capacity是那倒一個(gè)二的冪次的數(shù)組琐驴，
現(xiàn)在的第二個(gè)問(wèn)題俘种？？绝淡？宙刘？
為什么是比這個(gè)數(shù)字大的二的冪次方的數(shù)字（碰撞數(shù)小牢酵？悬包？）
繼續(xù)看，拿到這個(gè)數(shù)字是想做什么馍乙，算出一個(gè)hashmap的最大容量書和這個(gè)數(shù)字與擴(kuò)容因子（loadFactor）的積
布近，其實(shí)就是這個(gè)數(shù)字，去付給這個(gè)Entry[]數(shù)組的初始化大小丝格，然后進(jìn)入了initHashSeedAsNeeded(capacity)方法撑瞧，我們?cè)賮?lái)看
final boolean initHashSeedAsNeeded(int capacity) {
boolean currentAltHashing = hashSeed != 0;
boolean useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean switching = currentAltHashing ^ useAltHashing;
if (switching) {
hashSeed = useAltHashing
? sun.misc.Hashing.randomHashSeed(this)
: 0;
}
return switching;
}
currentAltHashing一般都是false，因?yàn)閔ashSeed（hash種子铁追？不懂）季蚂，本來(lái)就是0茫船，
useAltHashing：sun.misc.VM.isBooted()虛擬機(jī)是否啟動(dòng)琅束，應(yīng)該為true，那就看看后面這個(gè)判斷是什么
capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD
try {
threshold = (null != altThreshold)
? Integer.parseInt(altThreshold)
: ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;
// disable alternative hashing if -1
if (threshold == -1) {
threshold = Integer.MAX_VALUE;
}
if (threshold < 0) {
throw new IllegalArgumentException("value must be positive integer.");
}
} catch(IllegalArgumentException failed) {
throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
}
ALTERNATIVE_HASHING_THRESHOLD = threshold;
在這段代碼里算谈，我們知道了涩禀，
ALTERNATIVE_HASHING_THRESHOLD：這個(gè)就interger的最大的只，所以capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD這個(gè)為false然眼，
boolean switching = currentAltHashing ^ useAltHashing;這個(gè) 一個(gè)為false艾船，另一個(gè)也是false，，異或運(yùn)算屿岂，然后返回switching = false践宴，這里就是給這hashseed復(fù)制，也是hash算法的東西爷怀，到這里為止阻肩，我們算是吧一個(gè)Entry[]對(duì)象的初始化出來(lái)了，那么我們hashmap是：數(shù)組+鏈表
其中一部分出來(lái)了运授，但是到目前為止烤惊，還沒(méi)將我們傳入的key和value記錄下來(lái)，接著看put方法
if (key == null) return putForNullKey(value);
/**
將key為null的值方法數(shù)值的開(kāi)頭吁朦，由此我們自己可以知道柒室，這個(gè)地方只能存放一個(gè)值，并不能存放一個(gè)鏈表
*/
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;
}
接這個(gè)看下一個(gè)方法
int hash = hash(key);
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
//獲取hashcode
h ^= k.hashCode();
//將高位的數(shù)字放下來(lái)逗宜，減少碰撞性
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
//計(jì)算一個(gè)索引出來(lái)雄右，因?yàn)閿?shù)字是有長(zhǎng)度的，要根據(jù)hashcode去算計(jì)一個(gè)散列的索引到對(duì)應(yīng)的數(shù)字上去
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);
}
//便利有沒(méi)有相同值纺讲，有的話做一個(gè)返回邏輯
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;
}
}
最后一步不脯，將我們大key，value放到我們數(shù)組或者是鏈表上
void addEntry(int hash, K key, V value, int bucketIndex) {
//是否需要擴(kuò)容threshold = maxsize*loadFactor刻诊，
if ((size >= threshold) && (null != table[bucketIndex])) {
//擴(kuò)容的方法
resize(2 * table.length);
//根據(jù)新的數(shù)組重新hash防楷，重新計(jì)算數(shù)組
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
//這是添加元素entry對(duì)象
createEntry(hash, key, value, bucketIndex);
}
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
//達(dá)到最大值就不擴(kuò)容了
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
//根據(jù)當(dāng)前的大小重新創(chuàng)建數(shù)組
Entry[] newTable = new Entry[newCapacity];
//將舊 的方法復(fù)制到新的上面來(lái)
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
//上面我們講過(guò)了 boolean rehash為false
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;
//所以我們重新計(jì)算hash這一步，一般來(lái)說(shuō)是不會(huì)進(jìn)行的
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;
}
}
}
這個(gè)方法在單線程的情況下是沒(méi)有任何問(wèn)題则涯，但是在多線程的情況下就會(huì)出現(xiàn)：死循環(huán)
到這里我們基本上已經(jīng)閱讀完成
