一缠借、 面試知識點
- 隨著18年以來現(xiàn)在互聯(lián)網(wǎng)對java面試題也是越問越深，其中hashmap更是java必問問題宜猜，那么我們今天就來總結(jié)一下hashmap 的底層原理和面試沉姨浚考知識點。
-
HashMap 是一種存儲高校但是不保證有序的容器宝恶，它的數(shù)據(jù)結(jié)構(gòu)為"數(shù)組+鏈表/紅黑樹"的結(jié)構(gòu)（當鏈表長度到8以后數(shù)據(jù)結(jié)構(gòu)改為紅黑樹）
image.png
-
底層實現(xiàn)了Map<k,v> 的接口并實現(xiàn)了淺拷貝和序列化符隙，HashMap 默認初始值大小為16 ，初始值大小必須為2的冪次垫毙，如果用戶輸入的不是2的冪霹疫，那么系統(tǒng)自動更新為輸入值附近的2的冪次，最大大小為2的30次冪综芥。HashMap的閾值默認為 0.75丽蝎，當存儲節(jié)點超過該值，對map進行擴容。
每次擴容為原來的1倍屠阻。
image.png -
HashMap 提供了四種構(gòu)造方法红省，分別是默認構(gòu)造方法；可以指定初始容量構(gòu)造方法国觉；可以指定初始值和閾值的構(gòu)造方法吧恃；以及基于一個Map的構(gòu)造方法。一般常用的都是給定初始容量大小的構(gòu)造方法
image.png - 在一次put(添加操作)的時候麻诀，HashMap 會先進行初始化痕寓，如果沒有先進行初始化操作，初始化過程會取比用戶指定容量大的最近2的冪次數(shù)作為數(shù)組的初始容量蝇闭，如果設(shè)置了擴容的閾值也一并更新呻率。初始化完成以后繼續(xù)put 方法
- 先判斷有沒有初始化
- 在判斷傳入的key是否為空 就存儲在table(0)位置
- key不為空就對key進行hash，hash的結(jié)果在 & 上數(shù)組的長度就得到了位置呻引。
- 如果存儲位置為空就創(chuàng)建新節(jié)點礼仗，不為空就說存在hash沖突了。
- 解決沖突HashMap會遍歷整個鏈表逻悠，如果有相同的value值就更新元践，否則創(chuàng)建節(jié)點添加到鏈表頭。
- 添加還要判斷存儲節(jié)點是否達到閾值蹂风，達到閾值要進行擴容卢厂。
- 擴容兩倍乾蓬，擴容的時候使用Arrays.copy() 進行擴容惠啄。
- 擴容過后新插入的節(jié)點也要重新進行hash 一遍才能插入。
// jdk8 源碼
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
- 取值的操作和添加差不多任内。
- 先判斷是否為空撵渡，為空就取table(0)去找
- 不為空也低先hash & 數(shù)組長度得到下標位置
- 在遍歷找到相同的找到相應的值。
- 以上這些是一些常用的知識點死嗦，但是如果你只是知道以上這些還是不夠的趋距，一般面試官還會問你HashMap 線程安全碼？ 當然大家都知道是不安全的越除，但是要是問你怎么解決呢节腐？ 如果你要是回答加鎖或者回答使用HashTable 基本上就掛了。HashMao是一個線程不安全的容器摘盆，在并發(fā)操作會出現(xiàn)丟失更新問題翼雀，嚴重會導致cpu宕機的，一般報錯為java.util.ConcurrentModificationException.那我們該怎么解決呢孩擂？
- 使用java類庫提供的collections工具包下的Collections.synchronizedMap(new HashMap()),返回一個線程安全的Map
- 使用并發(fā)包(java.util.concurrent)下的ConcurrentHashMap,ConcurrentHashMap采用分段式鎖機制實現(xiàn)線程安全狼渊。
- 能不能手寫一個HashMap 線程不安全的案例
private static void hashMapNotSafe() {
// 線程不安全版本
Map<String, String> hashMap = new HashMap<>();
//并發(fā)版本的hashMap。
// Map<String, String> hashMap = new ConcurrentHashMap<>() ;
for (int i = 0; i < 30; i++) {
new Thread(()-> {
hashMap.put(Thread.currentThread().getName(), UUID.randomUUID().toString().substring(0, 8));
System.out.println(hashMap);
}, String.valueOf(i)).start();
}
}
- java8和java7的區(qū)別
- Hash1.7 和1.8 最大的不同在于1.8 采用了“數(shù)組+鏈表+紅黑樹”的數(shù)據(jù)結(jié)構(gòu)类垦，在鏈表長度超過8 時狈邑，把鏈表轉(zhuǎn)化成紅黑樹來解決HashMap 因鏈表變長而查詢變慢的問題城须；
- 1.7 的底層節(jié)點為Entry，1.8 為node 米苹，但是本質(zhì)一樣糕伐，都是Map.Entry 的實現(xiàn)
- 還有就是在存取數(shù)據(jù)時添加了關(guān)于樹結(jié)構(gòu)的遍歷更新與添加操作，并采用了尾插法來避免環(huán)形鏈表的產(chǎn)生
二驱入、 考點分析
HashMap 作為最基礎(chǔ)的容器赤炒，常用來考1.7和1.8的區(qū)別，除了這個要想在面試中脫穎而出還要對HashMap的前因后果要多了解亏较。
- 考點一：為什么初始容量為2的冪等次莺褒？為什么負載因子為0.75f？為什么做那么多擾動處理雪情。
- 這些問題都要圍繞一個點回答：減少hash 沖突遵岩。
- 容量必須為2的冪次是為了增加取值的可能性。
- 2的n次冪轉(zhuǎn)換為二進制為1后面n個0巡通，在計算下標的是否為hash&(length-1),也就是&(n-1)個1.所有二進制為1的好處尘执？
- 0/1 & 1 都為它本身
- 0/1 & 0 都為 0
- 可以看出&1保證了取值的平均。如果某一位為0 宴凉，比如最后一位誊锭，那么它&出來下標就一定是個偶數(shù)，減少了HashMap 數(shù)組一半的取值弥锄，大大增加了沖突的可能丧靡。
- 2的n次冪轉(zhuǎn)換為二進制為1后面n個0巡通，在計算下標的是否為hash&(length-1),也就是&(n-1)個1.所有二進制為1的好處尘执？
- 負載因子為0.75f是空間與時間的均衡。
- 如果負載因子小籽暇，意味著閾值變小温治。比如容量為10 的HashMap，負載因子為0.5f戒悠，那么存儲5個就會擴容到20熬荆，出現(xiàn)哈希沖突的可能性變小，但是空間利用率不高绸狐。適用于有足夠內(nèi)存并要求查詢效率的場景卤恳。
- 相反如果閾值為1 ，那么容量為10寒矿，就必須存儲10個元素才進行擴容突琳，出現(xiàn)沖突的概率變大，極端情況下可能會從O(1)退化到O(n)劫窒。適用于內(nèi)存敏感但不要求要求查詢效率的場景
- hash()的意義在于使hash結(jié)果不同hash 算法的好壞直接印象hash結(jié)構(gòu)的效率本今。1.8 之所以把9 次擾動降到2 次，是出于計算效率的考慮。
- 考點二：& 字符串和%字符串 雖然效果一樣冠息，但是操作效果更高挪凑。
- 考點三：為什么int String 更適合做key?
- int 和 String 的好處在于hash 出來的值不會改變。如果是一個對象逛艰，那么他們可能會因為內(nèi)部引用的改變而hashCode 值的改變躏碳，會導致存儲重復的數(shù)據(jù)或找不到數(shù)據(jù)的情況。
三散怖、 面試時候由于HashMap 引導出來的其他問題菇绵？
- 不僅僅是HashMap 的問題，在面試的時候镇眷，面試官會引導出很多其他問題咬最，所以這個地方你在回答問題的時候要設(shè)計引導到你熟悉的內(nèi)容上
- 說說concurrentHashMap 和 HashMap 的區(qū)別以及底層的實現(xiàn)？
- 說說HashMap 如何實現(xiàn)有序(LinkHashMap 和TreeMap)以及他們的差別
