我們在面試中, 也會經常被問到HashMap相關的底層實作, 阿巴阿巴....
HashMap的底層實作
首先它是基于陣列(存盤物件的參考)加鏈表(存盤物件)實作的
當我們通過put()和get()方法儲存和獲取物件，當我們將鍵值對傳遞給put()方法時，它呼叫鍵物件的hashCode()方法來計算hashcode，讓后找到bucket位置來儲存值物件，當獲取物件時，通過鍵物件的equals()方法找到正確的鍵值對，然后回傳值物件，HashMap使用鏈表來解決碰撞問題，當發生碰撞了，物件將會儲存在鏈表的下一個節點中， HashMap在每個鏈表節點中儲存鍵值對物件
簡單的模擬實作put的底層實作 jdk1.8
put(k, v){
int code = k.hashcode(); //計算key的hashcode
int index = code % table.length; // 存放的陣列下表
table[index] = new Entry(k, v, null); // 對應的物件
}
// 第二次插入 HashMap使用鏈表來解決碰撞問題，當發生碰撞了，物件將會儲存在鏈表的下一個節點中，
table[index] = new Entry(k, v, table[index]);
// todo 底層實作 若key相同時 回傳并覆寫 否則插入鏈表的下一個節點
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); //這個方法在hashmap沒有作用, 是在linkedHashMap實作的
return oldValue;
}HashMap和Hashtable的區別
HashMap和Hashtable都實作了Map介面，但決定用哪一個之前先要弄清楚它們之間的分別，主要的區別有：執行緒安全性，同步(synchronization)，以及速度，
- HashMap幾乎可以等價于Hashtable，除了HashMap是非synchronized的，并可以接受null(HashMap可以接受為null的鍵值(key)和值(value)，而Hashtable則不行)，
- HashMap是非synchronized，而Hashtable是synchronized，這意味著Hashtable是執行緒安全的，多個執行緒可以共享一個Hashtable；而如果沒有正確的同步的話，多個執行緒是不能共享HashMap的，Java 5提供了ConcurrentHashMap，它是HashTable的替代，比HashTable的擴展性更好，
- 另一個區別是HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的，所以當有其它執行緒改變了HashMap的結構（增加或者移除元素），將會拋出ConcurrentModificationException，但迭代器本身的remove()方法移除元素則不會拋出ConcurrentModificationException例外，但這并不是一個一定發生的行為，要看JVM，這條同樣也是Enumeration和Iterator的區別，
- 由于Hashtable是執行緒安全的也是synchronized，所以在單執行緒環境下它比HashMap要慢，如果你不需要同步，只需要單一執行緒，那么使用HashMap性能要好過Hashtable，
- HashMap不能保證隨著時間的推移Map中的元素次序是不變的，
常見面試題
- HashMap的作業原理
HashMap是基于hashing的原理，我們使用put(key, value)存盤物件到HashMap中，使用get(key)從HashMap中獲取物件，當我們給put()方法傳遞鍵和值時，我們先對鍵呼叫hashCode()方法，回傳的hashCode用于找到bucket位置來儲存Entry物件，
- hashcode相同會發生什么
因為hashcode相同，所以它們的bucket位置相同，‘碰撞’會發生，因為HashMap使用鏈表存盤物件，這個Entry(包含有鍵值對的Map.Entry物件)會存盤在鏈表中
get時, key的hashcode相同時, 找到bucket位置之后，會呼叫keys.equals()方法去找到鏈表中正確的節點，最終找到要找的值物件
- 減少碰撞的發生
當時是選擇一些不可變的最為我們的key, 不可變性使得能夠快取不同鍵的hashcode，這將提高整個獲取物件的速度，使用String，Interger這樣的wrapper類作為鍵是非常好的選擇
- 如果HashMap的大小超過了負載因子(load factor)定義的容量，怎么辦
HashMap的默認構造會指定默認的負載因子大小為0.75，也就是說，當一個map填滿了75%的bucket時候，和其它集合類(如ArrayList等)一樣，將會創建原來HashMap大小的兩倍的bucket陣列，來重新調整map的大小，并將原來的物件放入新的bucket陣列中，這個程序叫作rehashing，因為它呼叫hash方法找到新的bucket位置
- CocurrentHashMap來代替Hashtable嗎
Hashtable是synchronized的，但是ConcurrentHashMap同步性能更好，因為它僅僅根據同步級別對map的一部分進行上鎖，ConcurrentHashMap當然可以代替HashTable，但是HashTable提供更強的執行緒安全性
- 指定hashmap的初始大小
原始碼分析
無論我們如何設定初始容量，HashMap的tableSizeFor 都會將我們改成2的冪次方，也就是說，HashMap 的容量百分之百是 2的冪次方，但是，請注意：如果我們預計插入7條資料，那么我們寫入7，7-1 = 6, 6經過tableSizeFor() 方法的一些列與運算, 會回傳8, HashMap 會設定為 8，雖然是2的冪次方，但是，請注意，當我們放入第7條資料的時候，就會引起擴容，造成性能損失，所以，知曉了原理，我們以后在設定容量的時候還是自己算一下，比如放7條資料，我們還是都是設定成16(默認)，這樣就不會擴容了，
計算公式：
“注意負載因子（即loader factor）默認為 0.75”
假如我們要插入7條資料，tableSizeFor(int cap)會將我們輸入的7運算成8，
我們使用 8 * 0.75 = 6 也就是說最大閾值為6條
當我們插入第七條的時候它就擴容了，所以我們最好在指定容量的時候多預算一些
持續更新中... 歡迎大家留言補充...
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/257399.html
標籤：其他
上一篇：解決Fiddler不能抓包問題