HashMap的內(nèi)部數(shù)據(jù)結(jié)構(gòu)
HashMap 在1.7之前的數(shù)據(jù)結(jié)構(gòu)為 數(shù)組 + 鏈表，如圖所示：
HashMap 概念講解：
size 表示HashMap中存放KV的數(shù)量（為鏈表和樹(shù)中的KV的總和）
capacity 譯為容量。capacity就是指HashMap中桶的數(shù)量（Table的長(zhǎng)度）。默認(rèn)值為16。容量都是2的冪。
loadFactor 譯為裝載因子。裝載因子用來(lái)衡量HashMap滿的程度。loadFactor的默認(rèn)值為0.75f。計(jì)算HashMap的實(shí)時(shí)裝載因子的方法為：size/capacity。
threshold 譯為閾值 threshold=capacity*loadFactor
HashMap數(shù)組：transient Entry[] table
數(shù)組默認(rèn)長(zhǎng)度：static final int DEFAULT_INITIAL_CAPACITY = 1 << 4
數(shù)組最大長(zhǎng)度：static final int MAXIMUM_CAPACITY = 1 << 30
默認(rèn)加載因子：static final float DEFAULT_LOAD_FACTOR = 0.75f
1.8 之后數(shù)據(jù)結(jié)構(gòu)改為 數(shù)組 + 鏈表 + 紅黑樹(shù)，如圖所示：
HashMap的數(shù)據(jù)插入原理
jdk1.7 的插入原理如下：
java 1.8的插入原理如下：
**hash沖突你還知道哪些解決辦法 **
比較出名的有四種(1)開(kāi)放定址法(2)鏈地址法(3)再哈希法(4)公共溢出區(qū)域法
- 開(kāi)放定址法
線性探測(cè)法、 平方探測(cè)法、 雙散列函數(shù)探查法
- 鏈地址法
HashMap 1.7 采用這種方法
- 再哈希法
就是同時(shí)構(gòu)造多個(gè)不同的哈希函數(shù)：
Hi = RHi(key) i= 1,2,3 ... k;
當(dāng)H1 = RH1(key) 發(fā)生沖突時(shí)，再用H2 = RH2(key) 進(jìn)行計(jì)算，直到?jīng)_突不再產(chǎn)生，這種方法不易產(chǎn)生聚集，但是增加了計(jì)算時(shí)間。
- 公共溢出區(qū)域法
將哈希表分為公共表和溢出表，當(dāng)溢出發(fā)生時(shí)，將所有溢出數(shù)據(jù)統(tǒng)一放到溢出區(qū)。
HashMap的哈希函數(shù)怎么設(shè)計(jì)的嗎？
以下為jdk1.8里的hash方法。1.7的就不看了。 (現(xiàn)在問(wèn)的也少了)
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
hash函數(shù)是先拿到通過(guò)key 的hashcode，是32位的int值，然后讓hashcode的高16位和低16位進(jìn)行異或操作。
為什么采用hashcode的高16位和低16位異或能降低hash碰撞？hash函數(shù)能不能直接用key的hashcode？
這個(gè)也叫擾動(dòng)函數(shù)， HashMap 這么設(shè)計(jì)有兩點(diǎn)原因：
- 一定要盡可能降低hash碰撞，越分散越好；
- 算法一定要盡可能高效，因?yàn)檫@是高頻操作, 因此采用位運(yùn)算；
key.hashCode()函數(shù)調(diào)用的是key鍵值類型自帶的哈希函數(shù)（Object.hashCode() 是一個(gè)native的方法），返回int型散列值。 int值范圍為-21474836482147483647[-2^312^31-1]，前后加起來(lái)大概40億的映射空間。只要哈希函數(shù)映射得比較均勻松散，一般應(yīng)用是很難出現(xiàn)碰撞的。但問(wèn)題是一個(gè)40億長(zhǎng)度的數(shù)組，內(nèi)存是放不下的。如果HashMap數(shù)組的初始大小才16，用之前需要對(duì)數(shù)組的長(zhǎng)度取模運(yùn)算（ hash%length ），余數(shù)就是數(shù)組下標(biāo)。
但是，大家都知道這種運(yùn)算不如位移運(yùn)算快。因此，源碼中做了優(yōu)化hash&(length-1)。也就是說(shuō)hash%length==hash&(length-1)
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
與1.7 對(duì)應(yīng)的函數(shù)是：
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);
}
這也正好解釋了為什么HashMap的數(shù)組長(zhǎng)度要取2的整數(shù)冪。因?yàn)檫@樣（數(shù)組長(zhǎng)度-1）正好相當(dāng)于一個(gè)“低位掩碼”。 &操作的結(jié)果就是散列值的高位全部歸零，只保留低位值，用來(lái)做數(shù)組下標(biāo)訪問(wèn)。以初始長(zhǎng)度16為例，16-1=15。2進(jìn)制表示是00000000 00000000 00001111。和某散列值做&操作如下，結(jié)果就是截取了最低的四位值。
10100101 11000100 00100101
& 00000000 00000000 00001111
----------------------------------
00000000 00000000 00000101 //高位全部歸零，只保留末四位
但這時(shí)候問(wèn)題就來(lái)了，這樣就算我的散列值分布再松散，要是只取最后幾位的話，碰撞也會(huì)很嚴(yán)重。如果散列本身做得不好，分布上成等差數(shù)列，如果正好讓最后幾個(gè)低位呈現(xiàn)規(guī)律性重復(fù)，那么碰撞次數(shù)就多了起來(lái)。
"asdfggggasdfasdf"的hashcode值為 11011010011011100011011001011100 如下所示 (HashMap() default length is 16 )：
? h = h.hashCode(): 1101 1010 0110 1110 0011 0110 0101 1100
(h >>> 16) 無(wú)符號(hào)右移16位： 0000 0000 0000 0000 1101 1010 0110 1110 0011 0110 0101 1100
? hash= h^(h >>> 16): 1101 1010 0110 1110 1110 1100 0011 0010
? 2^4 - 1=15 (length-1): 0000 0000 0000 0000 0000 0000 0000 1111
? (n - 1) & hash : 0000 0000 0000 0000 0000 0000 0000 0010
? index = 2 : 0010
右位移16位，正好是32bit的一半，自己的高半?yún)^(qū)和低半?yún)^(qū)做異或，就是為了混合原始哈希碼的高位和低位，以此來(lái)加大低位的隨機(jī)性。而且混合后的低位摻雜了高位的部分特征，這樣高位的信息也被變相保留下來(lái)。
最后我們來(lái)看一下Peter Lawley的一篇專欄文章《An introduction to optimising a hashing strategy》里的的一個(gè)實(shí)驗(yàn)：他隨機(jī)選取了352個(gè)字符串，在他們散列值完全沒(méi)有沖突的前提下，對(duì)它們做低位掩碼，取數(shù)組下標(biāo)。
結(jié)果顯示，當(dāng)HashMap數(shù)組長(zhǎng)度為512的時(shí)候，也就是用掩碼取低9位的時(shí)候，在沒(méi)有擾動(dòng)函數(shù)的情況下，發(fā)生了103次碰撞，接近30%。而在使用了擾動(dòng)函數(shù)之后只有92次碰撞。碰撞減少了將近10%?？磥?lái)擾動(dòng)函數(shù)確實(shí)還是有功效的。
另外Java1.8相比1.7做了調(diào)整，1.7做了四次移位和四次異或，但明顯Java 8覺(jué)得擾動(dòng)做一次就夠了，做4次的話，多了可能邊際效用也不大，所謂為了效率考慮就改成一次了。
下面是1.7的hash代碼：
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
String中hashcode的實(shí)現(xiàn)?
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
String類中的hashCode計(jì)算方法還是比較簡(jiǎn)單的，就是以31為權(quán)，每一位為字符的ASCII值進(jìn)行運(yùn)算，用自然溢出來(lái)等效取模。
哈希計(jì)算公式可以計(jì)為s[0]31^(n-1) + s[1]31^(n-2) + … + s[n-1]
那為什么以31為質(zhì)數(shù)呢?
主要是因?yàn)?1是一個(gè)奇質(zhì)數(shù)，所以31i=32i-i=(i<<5)-i，這種位移與減法結(jié)合的計(jì)算相比一般的運(yùn)算快很多。
**為什么在解決hash沖突的時(shí)候，不直接用紅黑樹(shù)?而選擇先用鏈表，再轉(zhuǎn)紅黑樹(shù)? **
因?yàn)榧t黑樹(shù)需要進(jìn)行左旋，右旋，變色這些操作來(lái)保持平衡，而單鏈表不需要。
當(dāng)元素小于8個(gè)當(dāng)時(shí)候，此時(shí)做查詢操作，鏈表結(jié)構(gòu)已經(jīng)能保證查詢性能。當(dāng)元素大于8個(gè)的時(shí)候，此時(shí)需要紅黑樹(shù)來(lái)加快查詢速度，但是新增節(jié)點(diǎn)的效率變慢了。
因此，如果一開(kāi)始就用紅黑樹(shù)結(jié)構(gòu)，元素太少，新增效率又比較慢，無(wú)疑這是浪費(fèi)性能的。
**那為什么閥值是8呢? **
不知道。。。。。。。
當(dāng)鏈表轉(zhuǎn)為紅黑樹(shù)后，什么時(shí)候退化為鏈表?
為6的時(shí)候退轉(zhuǎn)為鏈表。中間有個(gè)差值7可以防止鏈表和樹(shù)之間頻繁的轉(zhuǎn)換。假設(shè)一下，如果設(shè)計(jì)成鏈表個(gè)數(shù)超過(guò)8則鏈表轉(zhuǎn)換成樹(shù)結(jié)構(gòu)，鏈表個(gè)數(shù)小于8則樹(shù)結(jié)構(gòu)轉(zhuǎn)換成鏈表，如果一個(gè)HashMap不停的插入、刪除元素，鏈表個(gè)數(shù)在8左右徘徊，就會(huì)頻繁的發(fā)生樹(shù)轉(zhuǎn)鏈表、鏈表轉(zhuǎn)樹(shù)，效率會(huì)很低。
**健可以為Null值么? **
必須可以，key為null的時(shí)候，hash算法最后的值以0來(lái)計(jì)算，也就是放在數(shù)組的第一個(gè)位置。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
你一般用什么作為HashMap的key?
一般用Integer、String這種不可變類當(dāng)HashMap當(dāng)key，而且String最為常用。
因?yàn)樽址遣豢勺兊?，所以在它?chuàng)建的時(shí)候hashcode就被緩存了，不需要重新計(jì)算。這就使得字符串很適合作為Map中的鍵，字符串的處理速度要快過(guò)其它的鍵對(duì)象。這就是HashMap中的鍵往往都使用字符串。
因?yàn)楂@取對(duì)象的時(shí)候要用到equals()和hashCode()方法，那么鍵對(duì)象正確的重寫這兩個(gè)方法是非常重要的,這些類已經(jīng)很規(guī)范的覆寫了hashCode()以及equals()方法。
用可變類當(dāng)HashMap的key有什么問(wèn)題?
hashcode可能發(fā)生改變，導(dǎo)致put進(jìn)去的值，無(wú)法get出，如下所示 :
@Test
public void testHashMapGet(){
HashMap<List<String>, Object> changeMap = new HashMap<>();
List<String> list = new ArrayList<>();
list.add("hello");
Object objectValue = new Object();
changeMap.put(list, objectValue);
Assert.assertNotNull(changeMap.get(list)); // true
list.add("hello world");//hashcode發(fā)生了改變
Assert.assertNotNull(changeMap.get(list)); // false
}
HashMap在并發(fā)編程環(huán)境下有什么問(wèn)題啊?
1.7 的時(shí)候，HashMap 在多并發(fā)環(huán)境下，有可能遇到如下問(wèn)題：
- 多線程擴(kuò)容，引起的死循環(huán)問(wèn)題
- 多線程put的時(shí)候可能導(dǎo)致元素丟失
- put非null元素后get出來(lái)的卻是null
知道jdk1.8中hashmap改了啥么?
- 由數(shù)組+鏈表的結(jié)構(gòu)改為數(shù)組+鏈表+紅黑樹(shù)。
- 優(yōu)化了高位運(yùn)算的hash算法：h^(h>>>16)
- 擴(kuò)容后，元素要么是在原位置，要么是在原位置再移動(dòng)2次冪的位置，且鏈表順序不變。
最后一條是重點(diǎn)，因?yàn)樽詈笠粭l的變動(dòng)，hashmap在1.8中，不會(huì)在出現(xiàn)死循環(huán)問(wèn)題。
平常怎么解決這個(gè)線程不安全的問(wèn)題
Java中有HashTable、Collections.synchronizedMap、以及ConcurrentHashMap可以實(shí)現(xiàn)線程安全的Map。
HashTable是直接在操作方法上加synchronized關(guān)鍵字，鎖住整個(gè)數(shù)組，粒度比較大，Collections.synchronizedMap是使用Collections集合工具的內(nèi)部類，通過(guò)傳入Map封裝出一個(gè)SynchronizedMap對(duì)象，內(nèi)部定義了一個(gè)對(duì)象鎖，方法內(nèi)通過(guò)對(duì)象鎖實(shí)現(xiàn)；ConcurrentHashMap使用分段鎖，降低了鎖粒度，讓并發(fā)度大大提高。
那你知道ConcurrentHashMap的分段鎖的實(shí)現(xiàn)原理嗎
ConcurrentHashMap成員變量使用volatile 修飾，免除了指令重排序，同時(shí)保證內(nèi)存可見(jiàn)性，另外使用CAS操作和synchronized結(jié)合實(shí)現(xiàn)賦值操作，多線程操作只會(huì)鎖住當(dāng)前操作索引的節(jié)點(diǎn)。
如下圖，線程A鎖住A節(jié)點(diǎn)所在鏈表，線程B鎖住B節(jié)點(diǎn)所在鏈表，操作互不干涉。
HashMap內(nèi)部節(jié)點(diǎn)是有序的嗎？
是無(wú)序的，根據(jù)hash值隨機(jī)插入
那有沒(méi)有有序的Map？
LinkedHashMap 和 TreeMap
LinkedHashMap怎么實(shí)現(xiàn)有序的？
LinkedHashMap內(nèi)部維護(hù)了一個(gè)單鏈表，有頭尾節(jié)點(diǎn)，同時(shí)LinkedHashMap節(jié)點(diǎn)Entry內(nèi)部除了繼承HashMap的Node屬性，還有before 和 after用于標(biāo)識(shí)前置節(jié)點(diǎn)和后置節(jié)點(diǎn)。可以實(shí)現(xiàn)按插入的順序或訪問(wèn)順序排序。
/**
* The head (eldest) of the doubly linked list.
*/
transient LinkedHashMap.Entry<K,V> head;
/**
* The tail (youngest) of the doubly linked list.
*/
transient LinkedHashMap.Entry<K,V> tail;
/**
* The iteration ordering method for this linked hash map: <tt>true</tt>
* for access-order, <tt>false</tt> for insertion-order.
*
* @serial
*/
final boolean accessOrder;
// internal utilities
// link at the end of list
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
/**
* HashMap.Node subclass for normal LinkedHashMap entries.
*/
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
@Test
public void testLinkedHashMap(){
Map<String, String> map = new LinkedHashMap<String, String>();
map.put("11111", "Bern");
map.put("222", "的");
map.put("3333", "簡(jiǎn)書(shū)");
map.forEach((k,v)->System.out.println("Item: [" + k + "] value: [" + v + "]"));
}
@Test
public void testHashMap(){
Map<String, String> map = new HashMap<String, String>();
map.put("11111", "Bern");
map.put("222", "的");
map.put("3333", "簡(jiǎn)書(shū)");
map.forEach((k,v)->System.out.println("Item: [" + k + "] value: [" + v + "]"));
}
//testLinkedHashMap output
Item: [11111] value: [Bern]
Item: [222] value: [的]
Item: [3333] value: [簡(jiǎn)書(shū)]
//testHashMap output
Item: [222] value: [的]
Item: [3333] value: [簡(jiǎn)書(shū)]
Item: [11111] value: [Bern]
TreeMap怎么實(shí)現(xiàn)有序的？
TreeMap是按照Key的自然順序或者Comprator的順序進(jìn)行排序，內(nèi)部是通過(guò)紅黑樹(shù)來(lái)實(shí)現(xiàn)。所以要么key所屬的類實(shí)現(xiàn)Comparable接口，或者自定義一個(gè)實(shí)現(xiàn)了Comparator接口的比較器，傳給TreeMap用戶key的比較。
前面提到j(luò)dk1.7在并發(fā)編程環(huán)境下會(huì)出現(xiàn)死循環(huán)，能具體講講嗎？
有點(diǎn)口渴，我們下一章節(jié)詳細(xì)介紹。
