Map接口-實現類HashMap

一、什么是Map？

二、實現類HashMap

1.關鍵特點

無序、key唯一、value允許重復、key和value允許為null。

2.數據結構

2.1 JDK 1.7

2.2 JDK 1.8

2.3 關鍵參數

2.4 關鍵計算

3.擴容方式

3.1 初始化

3.2 擴容

4.常見方法

4.1 根據key存入value

4.2 根據key獲取value

4.3 判斷Map

4.4 根據key替換value

4.5 根據key刪除value

4.6 遍歷Map

5.HashMap（put）底層原理

一、什么是Map？

（1）Map是一種鍵值對集合，每一個元素都包含一個鍵對象(key) 和一個值對象(value)。

（2）Map集合中，鍵不允許重復，值可以重復。（比如身份證與姓名）

（3）鍵和值是一一對應的，通過鍵可以找到與之對應的唯一的值。

（4）key和value必須是引用數據類型。

二、實現類HashMap

1.關鍵特點

無序、key唯一、value允許重復、key和value允許為null。

2.數據結構

2.1 JDK 1.7

數組+單向鏈表

在鏈表中插入元素，采用【頭插法】

2.2 JDK 1.8

數組+單向鏈表+紅黑樹

在鏈表中插入元素時，采用【尾插法】

2.3 關鍵參數

（1）Node<K, V>[ ] table：

????????????????保存KV鍵值對的數組，每個KV鍵值對都被封裝成一個Node對象。

????????????????數組容量決定了HashMap對內存的占用大小。

（2）float loadFactor：

????????????????加載因子(填充因子)。

????????????????加載因子默認為0.75，代表HashMap對數組容量的使用率為75%，超過該使用率，則數組需要進行擴容。

????????????????加載因子決定了HashMap對數組的使用率，加載因子越高，則表示允許填滿的元素就越多，集合的空間利用率就越高，但是沖突的機會增加。反之，越小則沖突的機會就會越少，但是空間很多就浪費。

（3）int threshold：

????????????????擴容閾值。

????????????????用于判斷數組是否需要進行擴容。

????????????????擴容閾值threshold = 數組容量 × 加載因子。

（4）size : int?

????????????????KV鍵值對的數量。

2.4 關鍵計算

（1）hash()函數：

(h = key.hashCode()) ^ (h >>> 16)：在key原有哈希值的基礎上，與哈希值的高16位進行異或運算，計算出的哈希值更佳散列，不易出現哈希沖突。

（2）下標計算：JDK 1.7 ：hash % 數組長度。

? ? ? ? ? ? ? ? ? ? ? ? ? ? JDK 1.8：(數組長度 - 1) & hash。提高性能--數組長度必須為2的N次冪。

3.擴容方式

3.1 初始化

（1）public HashMap()：加載因子默認為為0.75。

（2）public HashMap(int initialCapacity, float loadFactor)：指定容量和加載因子。

3.2 擴容

（1）添加第一個KV鍵值對，數組如果為空，則默認擴容為16。

（2）加入元素時，如果鏈表長度大于閾值（默認為 8）并且數組長度小于64，會產生數組擴容；*2。

（3）添加元素后，當HashMap中的元素個數超過【數組大小 × 加載因子(LoadFactor)】時，原數組擴容2倍。例如：加載因子(LoadFactor)的默認值為0.75，數組容量默認為16，當HashMap中元素個數超過16 × 0.75=12的時候，數組的容量擴容為16×2 =32；

4.常見方法

4.1 根據key存入value

（1）V put(K key, V value)：存入【KV鍵值對】，如果key存在，則覆蓋【原value值】，保存后，返回【原value值】。

（2）void putAll(Map m)：將【指定map】中的所有KV鍵值對，存入【當前map】。

（3）V putIfAbsent(K key, V value)：如果key不存在，則保存value，并返回【null】；如果key已經存在，則不保存value，并返回【原value值】。

4.2 根據key獲取value

（1）V get(Object key)：根據key，返回【value值】；如果key不存在，則返回【null】。

（2）V getOrDefault(Object key, V defaultValue)：根據key，返回【value值】；如果key不存在，則返回【默認值】。

4.3 判斷Map

（1）boolean containsKey(Object key)：判斷key是否存在。

（2）boolean containsValue(Object value)：判斷value是否存在。

（3）boolean isEmpty()：判斷map中的【KV鍵值對】數量是否為0。

（4）int size()：獲取map中的【KV鍵值對】數量。

4.4 根據key替換value

（1）V replace(K key, V value)：根據key，替換value，并返回【原value值】；如果key不存在，則返回【null】。

（2）boolean replace(K key, V oldValue, V newValue)：根據key和value，替換value，修改成功，返回【true】；如果key和value不存在，則替換失敗，返回【false】。

4.5 根據key刪除value

（1）V remove(Object key)：根據key，刪除【KV鍵值對】，并返回【原value值】。

（2）boolean remove(Object key, Object value)：根據key和value，刪除【KV鍵值對】，則刪除成功，返回【true】；如果key和value不存在，則刪除失敗，返回【false】。

（3）clear（）：清除map中的鍵值對。

4.6 遍歷Map

（1）Set<K> keySet()：獲取所有key。

（2）Collection<V> values()：獲取所有value。

（3）Set<Map.Entry<K,V>> entrySet()：獲取所有【KV鍵值對】，每個【KV鍵值對】使用【Entry類型的對象】封裝。

public class Demo01 {public static void main(String[] args) {//HashMap 無序，且key是唯一的，value是可重復的HashMap<String,String> hashMap=new HashMap<>();hashMap.put("110","北京");hashMap.put("120","天津");hashMap.put("130","河北");hashMap.put("610","陜西");hashMap.put("610","甘肅");hashMap.put("620","甘肅");System.out.println(hashMap);}
}

public class Demo02 {public static void main(String[] args) {HashMap<String, String> hashMap = new HashMap<>();insertElement(hashMap);//selectElement(hashMap);deleteElement(hashMap);}public static void insertElement(HashMap<String, String> hashMap) {System.out.println("========進入到添加方法中========");//1.V put(K key, V value)存鍵值對，如果集合不存在此鍵，直接存，返回值為null//當存在此鍵時，返回值為上一次的鍵對應的value，用此value覆蓋String item1 = hashMap.put("110", "北京");String item2 = hashMap.put("110", "天津");hashMap.put("130", "河北");hashMap.put("610", "陜西");System.out.println("第一次存返回值:" + item1);System.out.println("第二次存返回值:" + item2);//void putAll(Map m)HashMap<String, String> hashMap1 = new HashMap<>();hashMap1.put("620", "甘肅");hashMap1.put("630", "寧夏");hashMap1.put("610", "內蒙");//將指定map中的所有KV鍵值對，存入到當前map；hashMap.putAll(hashMap1);System.out.println(hashMap);//V  putIfAbsent(K key,V value)如果存在此鍵，返回值為鍵對應的舊值，如果不存在則存返回nullString oldValue = hashMap.putIfAbsent("611", "西安");System.out.println("putIfAbsent再次存610的鍵:" + oldValue);System.out.println(hashMap);}public static void selectElement(HashMap<String, String> hashMap) {System.out.println("=======進入到查看方法中=======");System.out.println("目前map中的元素為:" + hashMap);//V get(Object key)根據key，返回value值，如果key不存在，則返回nullString value1 = hashMap.get("120");System.out.println("鍵120對應的值為" + value1);//V getOrDefault(Object key,V defaultValue)//根據key，返回value值，如果key不存咋，則返回默認值String value2 = hashMap.getOrDefault("120", "不知道");System.out.println("鍵120對應的值為:" + value2);//boolean containsKey(Object key)判斷key是否存在boolean b1 = hashMap.containsKey("611");System.out.println("鍵611是否存在:" + b1);//boolean containsValue(Object value)判斷value是否存在boolean b2 = hashMap.containsValue("寧夏");System.out.println("值寧夏是否存在:" + b2);//boolean isEmpty()判斷map中的【KV鍵值對】數量是否為0System.out.println("集合map是否為空:" + hashMap.isEmpty());//int size()獲取map中的【KV鍵值對】數量System.out.println("集合的size:" + hashMap.size());}public static void deleteElement(HashMap<String, String> hashMap){System.out.println("========進入到刪除和修改方法中========");System.out.println("目前map中的元素為:" + hashMap);//V replace(K key, V value)根據key，替換value，并返回【原value值】；如果key不存在，則返回【null】String value=hashMap.replace("110","北京");System.out.println(value);System.out.println("修改后的hashmap："+hashMap);//boolean replace(K key, V oldValue, V newValue)//根據key和value，替換value，修改成功，返回【true】；如果key和value不存在，則替換失敗，返回【false】；boolean b1=hashMap.replace("610","內蒙","陜西");System.out.println(b1);System.out.println("修改后的hashmap："+hashMap);//V remove(Object key)根據key，刪除【KV鍵值對】，并返回【原value值】String str=hashMap.remove("130");System.out.println(str);System.out.println("刪除后的hashmap："+hashMap);//boolean remove(Object key, Object value)//根據key和value，刪除【KV鍵值對】，則刪除成功，返回【true】；如果key和value不存在，則刪除失敗，返回【false】；boolean b2=hashMap.remove("630","陜西");System.out.println(b2);System.out.println("刪除后的hashmap："+hashMap);//clear（）hashMap.clear();System.out.println("清空后:"+hashMap);}
}

public class Demo03 {public static void main(String[] args) {HashMap<String,String> hashMap=new HashMap<>();hashMap.put("110","北京");hashMap.put("120","天津");hashMap.put("130","河北");hashMap.put("610","陜西");hashMap.put("620","甘肅");System.out.println(hashMap);//1.Set<K> keySet()獲取所有的鍵Set<String> keys = hashMap.keySet();for (String key : keys) {String value = hashMap.get(key);System.out.printf("鍵為：%s - 值為%s\n", key, value);}//2.獲取所有的value Collection<V> values()Collection<String> values = hashMap.values();System.out.println(values);//3.獲取所有的鍵值對集合對象Set<Map.Entry<String, String>> entries = hashMap.entrySet();for (Map.Entry<String, String> entry : entries) {System.out.println(entry.getKey() + "==" + entry.getValue());}}
}

5.HashMap（put）底層原理

/*** 數據結構: Node<K,V>[] table, 數組 + 鏈表 + 紅黑樹* put整理:* 1.通過i = (n - 1) & hash計算當前鍵值對要存放的下標位置, 此處元素是否為null,如果為null直接存儲* 2.如果不為null,判斷當前的下標元素key是否和要存儲的key完全一樣, key一樣, 則value進行覆蓋* 3.鍵如果不同, 則產生了hash沖突, 將當前要存放的鍵值對存放進來*    3.1判斷當前的節點是否是樹形節點, 如果是樹形節點, 以樹形存放方式操作*    3.2如果不是樹形節點, 就是鏈表: 找p.next == null的位置(找的過程中也會和鏈表的每個元素的key進行相等比較),*        去進行p.next的賦值操作*        鏈表元素個數的判斷>8 && 數組長度 <64  -- 擴容, 2倍擴容*        鏈表元素個數的判斷>8 && 數組長度 >64  會將鏈表轉換為紅黑樹**        存放完元素如果達到擴容閾值（容量 × 加載因子，默認 0.75）, 2倍擴容。* 擴容:* 無參構造初始化對象, 第一次添加元素時, 首次擴容到16