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