Java7 HashMap
HashMap 是最簡(jiǎn)單的衡瓶，一來(lái)我們非常熟悉究飞，二來(lái)就是它不支持并發(fā)操作留特，所以源碼也非常簡(jiǎn)單。
首先挨下，我們用下面這張圖來(lái)介紹 HashMap 的結(jié)構(gòu)熔恢。
1
這個(gè)僅僅是示意圖，因?yàn)闆]有考慮到數(shù)組要擴(kuò)容的情況臭笆，具體的后面再說(shuō)叙淌。
大方向上，HashMap 里面是一個(gè)數(shù)組愁铺，然后數(shù)組中每個(gè)元素是一個(gè)單向鏈表鹰霍。
上圖中，每個(gè)綠色的實(shí)體是嵌套類 Entry 的實(shí)例茵乱，Entry 包含四個(gè)屬性：key, value, hash 值和用于單向鏈表的 next茂洒。
capacity：當(dāng)前數(shù)組容量，始終保持 2^n瓶竭，可以擴(kuò)容督勺，擴(kuò)容后數(shù)組大小為當(dāng)前的 2 倍。
loadFactor：負(fù)載因子斤贰，默認(rèn)為 0.75智哀。
threshold：擴(kuò)容的閾值，等于 capacity * loadFactor
put 過(guò)程分析
還是比較簡(jiǎn)單的荧恍，跟著代碼走一遍吧瓷叫。
publicVput(K key, Vvalue){// 當(dāng)插入第一個(gè)元素的時(shí)候，需要先初始化數(shù)組大小if(table == EMPTY_TABLE) {? ? ? ? inflateTable(threshold);? ? }// 如果 key 為 null送巡，感興趣的可以往里看摹菠，最終會(huì)將這個(gè) entry 放到 table[0] 中if(key ==null)returnputForNullKey(value);// 1. 求 key 的 hash 值inthash = hash(key);// 2. 找到對(duì)應(yīng)的數(shù)組下標(biāo)inti = indexFor(hash, table.length);// 3. 遍歷一下對(duì)應(yīng)下標(biāo)處的鏈表，看是否有重復(fù)的 key 已經(jīng)存在骗爆，//? ? 如果有次氨，直接覆蓋，put 方法返回舊值就結(jié)束了for(Entry 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);returnoldValue;? ? ? ? }? ? }? ? modCount++;// 4. 不存在重復(fù)的 key摘投，將此 entry 添加到鏈表中糟需，細(xì)節(jié)后面說(shuō)addEntry(hash, key,value, i);returnnull;}
數(shù)組初始化
在第一個(gè)元素插入 HashMap 的時(shí)候做一次數(shù)組的初始化，就是先確定初始的數(shù)組大小谷朝，并計(jì)算數(shù)組擴(kuò)容的閾值洲押。
privatevoidinflateTable(inttoSize){// 保證數(shù)組大小一定是 2 的 n 次方。// 比如這樣初始化：new HashMap(20)圆凰，那么處理成初始數(shù)組大小是 32intcapacity = roundUpToPowerOf2(toSize);// 計(jì)算擴(kuò)容閾值：capacity * loadFactorthreshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY +1);// 算是初始化數(shù)組吧table =newEntry[capacity];? ? initHashSeedAsNeeded(capacity);//ignore}
這里有一個(gè)將數(shù)組大小保持為 2 的 n 次方的做法杈帐，Java7 和 Java8 的 HashMap 和 ConcurrentHashMap 都有相應(yīng)的要求，只不過(guò)實(shí)現(xiàn)的代碼稍微有些不同，后面再看到的時(shí)候就知道了挑童。
計(jì)算具體數(shù)組位置
這個(gè)簡(jiǎn)單累铅，我們自己也能 YY 一個(gè)：使用 key 的 hash 值對(duì)數(shù)組長(zhǎng)度進(jìn)行取模就可以了。
staticintindexFor(inthash,intlength){// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";returnhash & (length-1);}
這個(gè)方法很簡(jiǎn)單站叼，簡(jiǎn)單說(shuō)就是取 hash 值的低 n 位娃兽。如在數(shù)組長(zhǎng)度為 32 的時(shí)候，其實(shí)取的就是 key 的 hash 值的低 5 位尽楔，作為它在數(shù)組中的下標(biāo)位置投储。
添加節(jié)點(diǎn)到鏈表中
找到數(shù)組下標(biāo)后，會(huì)先進(jìn)行 key 判重阔馋，如果沒有重復(fù)玛荞，就準(zhǔn)備將新值放入到鏈表的表頭。
voidaddEntry(inthash, K key, Vvalue,intbucketIndex){// 如果當(dāng)前 HashMap 大小已經(jīng)達(dá)到了閾值呕寝，并且新值要插入的數(shù)組位置已經(jīng)有元素了勋眯，那么要擴(kuò)容if((size >= threshold) && (null!= table[bucketIndex])) {// 擴(kuò)容，后面會(huì)介紹一下resize(2* table.length);// 擴(kuò)容以后下梢，重新計(jì)算 hash 值hash = (null!= key) ? hash(key) :0;// 重新計(jì)算擴(kuò)容后的新的下標(biāo)bucketIndex = indexFor(hash, table.length);? ? }// 往下看createEntry(hash, key,value, bucketIndex);}// 這個(gè)很簡(jiǎn)單客蹋，其實(shí)就是將新值放到鏈表的表頭，然后 size++voidcreateEntry(inthash, K key, Vvalue,intbucketIndex){? ? Entry e = table[bucketIndex];? ? table[bucketIndex] =newEntry<>(hash, key,value, e);? ? size++;}
這個(gè)方法的主要邏輯就是先判斷是否需要擴(kuò)容孽江，需要的話先擴(kuò)容嚼酝，然后再將這個(gè)新的數(shù)據(jù)插入到擴(kuò)容后的數(shù)組的相應(yīng)位置處的鏈表的表頭。
數(shù)組擴(kuò)容
前面我們看到竟坛，在插入新值的時(shí)候，如果當(dāng)前的 size 已經(jīng)達(dá)到了閾值钧舌，并且要插入的數(shù)組位置上已經(jīng)有元素担汤，那么就會(huì)觸發(fā)擴(kuò)容，擴(kuò)容后洼冻，數(shù)組大小為原來(lái)的 2 倍崭歧。
voidresize(intnewCapacity) {? ? Entry[] oldTable =table;intoldCapacity = oldTable.length;if(oldCapacity == MAXIMUM_CAPACITY) {? ? ? ? threshold = Integer.MAX_VALUE;return;? ? }// 新的數(shù)組Entry[] newTable =newEntry[newCapacity];// 將原來(lái)數(shù)組中的值遷移到新的更大的數(shù)組中transfer(newTable, initHashSeedAsNeeded(newCapacity));table= newTable;? ? threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY +1);}
擴(kuò)容就是用一個(gè)新的大數(shù)組替換原來(lái)的小數(shù)組，并將原來(lái)數(shù)組中的值遷移到新的數(shù)組中撞牢。
由于是雙倍擴(kuò)容率碾，遷移過(guò)程中，會(huì)將原來(lái) table[i] 中的鏈表的所有節(jié)點(diǎn)屋彪，分拆到新的數(shù)組的 newTable[i] 和 newTable[i + oldLength] 位置上所宰。如原來(lái)數(shù)組長(zhǎng)度是 16，那么擴(kuò)容后畜挥，原來(lái) table[0] 處的鏈表中的所有元素會(huì)被分配到新數(shù)組中 newTable[0] 和 newTable[16] 這兩個(gè)位置仔粥。代碼比較簡(jiǎn)單，這里就不展開了。
get 過(guò)程分析
相對(duì)于 put 過(guò)程躯泰，get 過(guò)程是非常簡(jiǎn)單的谭羔。
根據(jù) key 計(jì)算 hash 值。
找到相應(yīng)的數(shù)組下標(biāo)：hash & (length - 1)麦向。
遍歷該數(shù)組位置處的鏈表瘟裸，直到找到相等(==或equals)的 key。
publicVget(Object key) {// 之前說(shuō)過(guò)诵竭，key 為 null 的話话告，會(huì)被放到 table[0]，所以只要遍歷下 table[0] 處的鏈表就可以了if(key ==null)returngetForNullKey();// Entry entry = getEntry(key);returnnull== entry ?null: entry.getValue();}
getEntry(key):
finalEntry getEntry(Object key) {if(size ==0) {returnnull;? ? }inthash = (key ==null) ?0: hash(key);// 確定數(shù)組下標(biāo)秀撇，然后從頭開始遍歷鏈表超棺，直到找到為止for(Entry 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))))returne;? ? }returnnull;}
出處：https://www.javadoop.com/post/hashmap#Java7%20HashMap
每日一題
??如下代碼：?
public class Foo {?
public static void main(String[] args) {?
try {?
return;?
} finally {?
System.out.println( "Finally" );?
}?
}?
}?
輸出結(jié)果是什么???????A?
A. Finally?
B.?
編譯失敗?
C.?代碼正常運(yùn)行但沒有任何輸出?.?
D.?
運(yùn)行時(shí)拋出異常
??Overload和?Override?的區(qū)別。?Overloaded?的方法是否可以改變返回值的類型??
方法的重寫?Overriding?和重載?Overloading?是?Java?多態(tài)性的不同表現(xiàn)呵燕。重寫?Overriding?是父類與子類之間多態(tài)性的一種表現(xiàn)棠绘，重載?Overloading?是一個(gè)類中多態(tài)性的一種表現(xiàn)。如果在子類中定義某方法與其父類有相同的名稱和參數(shù)再扭，我們說(shuō)該方法被重寫?(Overriding)?氧苍。子類的對(duì)象使用這個(gè)方法時(shí)，將調(diào)用子類中的定義泛范，對(duì)它而言让虐，父類中的定義如同被“屏蔽”了。如果在一個(gè)類中定義了多個(gè)同名的方法罢荡，它們或有不同的參數(shù)個(gè)數(shù)或有不同的參數(shù)類型赡突，則稱為方法的重載?(Overloading)?。?Overloaded?的方法是可以改變返回值的類型区赵。
??設(shè)計(jì)?4?個(gè)線程惭缰，其中兩個(gè)線程每次對(duì)?j?增加?1?，另外兩個(gè)線程對(duì)?j?每次減少?1?笼才。寫出程序漱受。
注：?因?yàn)檫@?4?個(gè)線程共享?J?，所以線程類要寫到內(nèi)部類中骡送。
加線程：?每次對(duì)?j?加一昂羡。
減線程：?每次對(duì)?j?減一。?public class TestThreads
{
private int j=1;
//?加線程
private class Inc implements Runnable
{
public void run()
{
for(int i = 0;i < 10;i++)
{
inc();
}
}
}
//?減線程
private class Dec implements Runnable
{
public void run()
{
for(int i = 0;i < 10;i++)
{
dec();
}
}
}
//?加?1
private synchronized void inc()
{
j++;
System.out.println(?Thread.currentThread().getName()?+"-inc:"+j);
}
//?減?1
private synchronized void dec()
{
j--;
System.out.println(?Thread.currentThread().getName()?+"-dec:"+j);
}
//?測(cè)試程序
public static void main(String[] args)
{
TestThreads test = new TestThreads();
//?創(chuàng)建兩個(gè)線程類
Thread thread = null;
Inc inc = test.new Inc();
Dec dec = test.new Dec();
//?啟動(dòng)?4?個(gè)線程
for(int i = 0;i < 2;i++)
{
thread = new Thread(inc);
thread.start();
thread = new Thread(dec);
thread.start();
}
}
}
