一、HashMap的底層實作
HashMap底層是基于陣列和鏈表實作的，其中最重要的引數：容量和負載因子，
容量的默認大小事16，負載因子是0.75，當HashMap的size>16*0.75的時候就會發生庫容（容量和負載因子都可以自由調整）
Hashmap實作了Map介面，允許放入null元素，出了該類未實作同步外，其余和HashTable大致相同，跟TreeMap不同，該容器不保證冤死順序，根據需要該容器可能對元素重新哈希，元素的順序也會被重新打散，因此不同時間迭代同一個HashMap的順序可能會不同，
二、HashMap的put(key,value)方法
首先會將傳入的可以、做hash運算計算出hashCode，然后根據陣列長度取模計算出在陣列中的index下表
由于在計算機中位運算比取模運算效率高，所以HashMsap規定陣列的長度為2n，這樣用2n-1做位運算與取模效果一致，并且效率要高出許多
由于陣列的長度有限，所以難免出現不同放入key通過運算得到的index相同，這種情況可以利用鏈表來解決，HashMap會在table[index]出形成鏈表，采用頭插法將資料插入鏈表中
三、HashMap的get(key)fangfa
get和put類似，也是講傳入的可以計算出index，如果該位置上是一個鏈表就需要比那里整個鏈表，通過key.equals(k)來找到對應的元素，
遍歷方式：
第一種
Iterator<Map.Entry<String, Integer>> entryIterator=map.entrySet().iterator();
while(entryIterator.hasNext()){
Map.Entry<String,Integer> next=entryIterator.next();
System.err.println("key="+next.getKey()+"value="https://www.cnblogs.com/houqx/p/+next.getValue());
}
第二種
Iterator iterator=map.keySet().iterator();
while(iterator.hasNext()){
String key=iterator.next();
System.err.println("key="+key+"value="https://www.cnblogs.com/houqx/p/+map.get(key));
}
第三種
map.forEach((key,value)->{
System.err.println("key="+key+"value="https://www.cnblogs.com/houqx/p/+value);
});
第一種可以把key value同時取出，第二種還得需要通過key去一次value，效率較低，第三種需要JDK1.8以上，通過外層遍歷table，內層遍歷鏈表或紅黑樹，
四、為什么多執行緒場景下不推薦使用HashMap
在并發環境下使用HashMap容易出現死回圈，并發場景下發生擴容，呼叫resize()方法里的rehash()時，容易出現環形鏈表，這樣當獲取一個不存在的key時，計算出的index正好是環形鏈表的下標時就會出現死回圈
所以，HashMap只能在單執行緒中使用，并且盡量的預設容量，盡可能的減少擴容發
在JDK1.8中對HashMap進行了優化：當hash碰撞之后寫入鏈表的長度超過閾值（默認為8），鏈表將會轉換成紅黑樹，假設hash沖突非常嚴重，一個陣列后面接了很長的鏈表，此時查詢的時間復雜度就是O(n)，如果是紅黑樹，時間復雜度就是O(logn)，大大提高了查詢的效率，多執行緒場景下推薦使用ConcurrentHashMap，
五、HashSet的底層實作
HashSet是對HashMap的簡單包裝，對HashSet的函式呼叫都會轉換成合適的HashMap方法，因此HashSet的實作非常簡單，
成員變數
首先了解下HashSet的成員變數
private transient HashMap<E,Object> map;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
發現主要有兩個變數：
map：用于存放最終資料
PRESENT：是所有寫入map的value值
建構式
public HashSet() {
map = new HashMap<>();
}
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
建構式很簡單，利用了HashMap初始化了map
add
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
比較關鍵的就是這個add()方法，可以看出他是將存放的物件當做了HashMap的鍵，value都是相同的PRESENT.由于HashMap的key是不能重復的，所以每當有重復的值寫入到HashSet中只能存放不重復的元素
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/117760.html
標籤：Java
上一篇：Java不會被淘汰的12個原因
下一篇：JVM科普