Map集合

一、Map集合

1.1. 概述

​ 目前为止，所有的集合都是单列集合，这些集合在不同场景下有不同用途，一般对有序的存储需求使用List集合，对去重的需求使用Set集合；但是对于无序集合的查询操作比较麻烦：需要遍历集合，再比对；对于这种问题，需要一种查询（检索）更为高效的存储机制，在数据结构中一般查询速度比较快结构以：二叉树为首，另外二叉树中对查找方式最快又以：红黑树为主，因此Map集合其中有一个实现(HashMap)就使用到了该结构;

​ Map集合与Collection接口不同之处在于，这是一个双列集合（由键值对结构组成），在代码中表示一个Entry,如下图：

Map是双列集合的顶层接口，一般使用的时候都是选择使用其实现类，Map集合常用的实现类包含：

• java.util.HashMap
• java.util.TreeMap
• java.util.Hashtable
• java.util.LinkedHashMap
• java.util.concurrent.ConcurrentHashMap

Map集合特点：

1. 使用键值对结构存储元素
2. 通过键可以获取一个值（唯一）
3. 在集合中存储的键是唯一的（值可以重复）

Map集合常见方法：

• clear()：清除集合中所有元素
• put(k,v)：向集合中添加元素
• putAll(Map map)：将一个Map集合加入当前map集合
• containsKey(k)：判断当前Map中是否包含指定的键
• containsValue(v)：判断当前Map中是否包含指定的键
• get(k)：根据键获取值
• getOrDefault(k,d)：根据键获取值，如果键不存在则返回默认值
• isEmpty()：判断当前集合是否是空集合
• keySet()：返回当前Map集合中的键集
• entrySet()：返回当前Map集合的一个元素Map.Entry（包含了键值）
• remove(k)：根据键删除整个映射（k-v）
• remove(k,v)：根据键值删除匹配的映射
• size()：获取集合中元素的个数
• values()：返回当前Map集合的值集（Collection）

package com.softeem.teach.teach4;

import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

/**
 * @program: J2306
 * @description:
 * @author: Alex
 * @create: 2023-07-26 15:31
 **/

public class Demo1 {
    public static void main(String[] args) {
        //  k          v
        Map<Integer,String> map = new HashMap<>();
        // 1.put() 添加元素  分别放k  v            k=v
        map.put(1,"张三");
        map.put(2,"李四");
        map.put(3,"王五");

        // 如果k相同,则会覆盖之前的值
        System.out.println(map);

        // 2.clean() 清空所有元素
//        map.clear();
//        System.out.println(map);

        // 3.putAll() 添加另一个map中的所有元素
        Map<Integer,String> map2 = new HashMap<>();
        map2.put(4,"赵六");
        map2.put(5,"田七");

        map.putAll(map2);
        System.out.println(map);

        // 4.containsKey() 判断是否包含指定的key
        boolean b = map.containsKey(1);
        System.out.println(b);

        // 5,containsValue() 判断是否包含指定的value
        boolean b1 = map.containsValue("张三");
        System.out.println(b1);

        // 6.get() 根据key获取value  如果key不存在,则返回null
        String s = map.get(1);
        System.out.println(s);

        // 通过get方法进行遍历
        for (int i = 1; i < map.size(); i++) {
            String s1 = map.get(i);
            System.out.println(s1);
        }

        // 7.getOrDefault() 根据key获取value,如果key不存在,则返回默认值
        String s1 = map.getOrDefault(7, "默认");
        System.out.println(s1);

        // 8.isEmpty() 判断是否为空
        boolean empty = map.isEmpty();
        System.out.println(empty);

        // 9.keySet() 获取所有的key
        Set<Integer> integers = map.keySet();
        System.out.println(integers);

        // 10.entrySet() 获取所有的键值对 set类型的
        Set<Map.Entry<Integer, String>> entries = map.entrySet();
        System.out.println(entries);

        // 11.remove() 根据key删除元素
        map.remove(1);
        System.out.println(map);

        // 根据key和value删除元素
        map.remove(2,"李四1");
        System.out.println(map);

        // 12,size() 获取元素个数
        int size = map.size();
        System.out.println(size);

        // 13,values() 获取所有的value
        Collection<String> values = map.values();
        System.out.println(values);
    }
}

1.2 HashMap

1.2.1. HashMap基本使用(无序,k不能重复)

​ Map集合提供了最常见的实现为java.util.HashMap,该实现内部使用的是数组+链表+红黑树(jdk8新增)的实现，该实现允许空键值，只能有一个空键，元素的存储顺序与添加顺序无关，以对象的hash地址进行排序存储,HashMap是线程不安全实现。

HashMap实现了Map接口，因此其内部的方法都是从Map接口实现过来：

//创建Map集合使用HashMap实现
Map<String,Object> map = new HashMap<>();
//添加元素
map.put("a","admin");
map.put("c","clark");
map.put("b","bob");
map.put("m","miller");
map.put("k","kobe");
map.put(null,null);
map.put(null,null);

System.out.println(map);

//获取一个元素
System.out.println(map.get("c"));
//获取一个元素，不存在则返回默认值
System.out.println(map.getOrDefault("d","softeem"));

//获取map的键集
Set<String> keys = map.keySet();
//对键集遍历
for(String k:keys){
    //根据键获取值
    Object val = map.get(k);
    System.out.println(k+"--->"+val);
}
System.out.println("========================");
//获取Map集合中所有映射的set集合
Set<Map.Entry<String, Object>> set = map.entrySet();
for (Map.Entry<String, Object> e : set) {
    //获取映射中的键
    String key = e.getKey();
    //获取映射中的值
    Object value = e.getValue();
    System.out.println(key+"--->"+value);
}

//获取map集合的值集
Collection<Object> c = map.values();
for (Object o : c) {
    System.out.println(o);
}

Object r = map.remove(null);
System.out.println("移除元素："+r);

//清理Map集合
map.clear();
System.out.println(map);

//返回Map集合映射总个数（元素个数）
System.out.println(map.size());
//判断集合是否为空（元素个数是否为0）
System.out.println(map.isEmpty());
//完成一个简易的学生信息管理系统，要求从学生集合中能够快速的使用学号将学生对象获取？

1.2.2. HashMap的实现原理

通过阅读HashMap的源码：

/**
初始容量
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
集合中允许存储的元素最大个数
*/
static final int MAXIMUM_CAPACITY = 1 << 30;   // 1073741824

/**
初始加载因子，默认：0.75 （数组扩容的初始阈值，临界值）
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
  元素存储从链表转红黑树的阈值（当链表的长度到达8之后转为红黑树）
 */
static final int TREEIFY_THRESHOLD = 8;

/**
   树的深度小于6时转换为链表
 */
static final int UNTREEIFY_THRESHOLD = 6;

/**
 转为红黑树存储时数组的最小容量
*/
static final int MIN_TREEIFY_CAPACITY = 64;

• HashMap的默认容量16（Hash桶高度）
• 默认的加载因子时是 :0.75 （触发扩容临界比例）
• 当数组中元素的个数到达加载因子的临界值时会触发扩容（resize（））
• 当元素存储产生hash碰撞时会将原本数组转换为一个链表（单链表）
• 当链表的长度到达8并且数组长度到达64时，会将链表转换为红黑树（JDK1.8引入）
• 当对元素进行删除时，红黑树节点减少到6时会将树还原成链表结构
• JDK1.8之前链表的节点的插入使用头插法（从头部插入），1.8之后使用尾插法（尾部插入）

hash冲突解决方案:

1. 再Hash
2. 拉链法
3. 红黑树

1.3. TreeMap

​ Map接口针对一些排序的集合实现提供了TreeMap,TreeMap底层通过红黑树实现，并且其存储的元素要求键必须有自然排序规则（元素类型必须实现Comparable接口）或者在创建TreeMap对象时额外指定比较器Comparator;由于TreeMap的特性，因此其元素键不允许为null

TreeMap的使用和HashMap类似，但不同之处在于，需要存储的元素实现Comparable接口，或者提供比较器：

package com.softeem.teach.teach4;

import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;

/**
 * @program: J2306
 * @description: TreeMap和TreeSet除了添加元素的方式不同,其他的都是一样的
 * 都要实现Comparable接口,并重写compareTo方法
 * 或者在创建TreeMap的时候传入一个Comparator比较器
 * @author: Alex
 * @create: 2023-07-26 16:16
 **/

public class Demo3 {
    public static void main(String[] args) {
        // 这里的Student类实现Comparable接口,并重写compareTo方法,所以可以直接使用TreeMap
        Map<Student,Object> map = new TreeMap<>();
        map.put(new Student(10,"张三"),new Object());
        map.put(new Student(20,"李四"),new Object());
        map.put(new Student(30,"王五"),new Object());
        map.put(new Student(20,"赵六"),new Object());

        System.out.println(map);

        Map<Teacher,Object> map1 = new TreeMap<>(new Comparator<Teacher>() {
            @Override
            public int compare(Teacher o1, Teacher o2) {
                return o1.getAge()-o2.getAge();
            }
        });

        map1.put(new Teacher(10,"张三"),new Object());
        map1.put(new Teacher(20,"李四"),new Object());
        map1.put(new Teacher(30,"王五"),new Object());
        map1.put(new Teacher(20,"赵六"),new Object());

        System.out.println(map1);

    }
}

1.4. LinkedHashMap

同LinkedHashSet（基于LinkedHashMap的实现）类似，Map接口也提供了一个既能够去除重复，同时又能保证元素存储有序性的Map集合实现

Map<String,Object> map = new LinkedHashMap<>();
map.put("curry","curry");
map.put("kobe","kobe");
map.put("james","curry");
map.put("allen","curry");
map.put("kobe","kobe");
map.put("curry","curry");

System.out.println(map);

boolean b = map.containsKey("james");
System.out.println("集合中是否包含指定键的元素--->"+b);

boolean c = map.containsValue("curry");
System.out.println("集合中是否包含指定值的元素--->"+c);

1.5. ConcurrentHashMap

通常情况在对Map集合遍历时不能同时做更新（添加和删除）操作，否则将会导致ConcurrentModificationException出现，因为遍历同时更新集合可能造成遍历混乱；对于这种需求，JDK从1.5开始出现了并发编程包，提供了一个Map接口新实现：ConcurrentHashMap；

ConcurrentHashMap底层实现原理类似HashMap(数组+链表+红黑树)，但是是一种线程安全的实现,内部关键更新部位使用了同步块（对象锁）

Map<String,Object> map = new LinkedHashMap<>();
map.put("curry","curry");
map.put("kobe","kobe");
map.put("james","curry");
map.put("allen","curry");
map.put("kobe","kobe");
map.put("curry","curry");

Set<Map.Entry<String, Object>> set = map.entrySet();
for (Map.Entry<String, Object> e : set) {
    map.remove(e.getKey()); //java.util.concurrent.ConcurrentModificationException
}

//使用ConcurrentHashMap
Map<String,Object> map = new ConcurrentHashMap<>();
map.put("curry","curry");
map.put("kobe","kobe");
map.put("james","curry");
map.put("allen","curry");
map.put("kobe","kobe");

Set<String> keys = map.keySet();
for (String key : keys) {
    map.remove(key); //正常执行
}

System.out.println(map);

1.6. Hashtable

从JDK1.0开始java就已经提供了类似Map集合这样的双列集合：Dictionary(字典)，由于其是一个抽象类，因此，针对该类jdk提供了一个子类：Hashtable;从JDK1.2开始Hashtable被改造为从Map接口实现,Hashtable底层实现原理使用的数组结构，Hashtable是一个线程安全的Map接口实现：

Map集合常见面试题：

1. HashMap实现原理是什么?
2. HashMap和Hashtable区别是什么？
3. HashMap和TreeMap区别？