《从0到1常用Map集合核心摘要 + 不深不浅底层核心》

《从0到1常用Map集合核心摘要+不深不浅底层核心》

前置知识

什么是键值对

​ 键值对是一种数据结构，键是唯一标识，值是对应数据，用来快速查找信息。例：

{"name": "Alice"}，键是name，值是Alice。

​ 这听起来有些抽象, 为什么不能值就是数据呢? 还要多一个键

​ 实际上, 键可能只是一个用于 ‘描述/标识’ 值的信息, 它的值可能是一个对象, 或一 个数组, 甚至更多复杂的东西,

​ 但是无论有多复杂, 都可以通过一个 键 找到
​ 而你的键, 可能连 5 个字母都没有

​ 补充：并且直接存储值时，每个值的含义会很模糊。键则提供信息，比如
​ name: "Alice" 更直观，而不是单独存 "Alice"。

map 集合是干嘛用的?

​ map集合就是用来存储一组或多组键值对的, 为了方便我们使用键值对, 其中封装了很多 方法, 供我们操作键值对

所有Map集合的接口 “Map”

• 一个接口, 其中包含的所有实现类都是 同一套数据结构(键值对)

介绍

• Map 集合是一种双列集合, 每个元素包含两个数据, 一个是键一个是值

  • 特点

    • 键唯一 每个键唯一, 值可重复
    • 易查 通过键定位值, 提高访问效率及便利性
    • 灵活 通过泛型可存储各类数据, 无论是键或值

  • 每个元素的格式

    • key = value : 键值对

    • key (键) : 非重

    • value (值) : 可重

    • 关联性 : 键绑值, 哪怕不同键同值, 地址也不一样

    • 一键多值 : 结合使用双列集合和单列集合, 来完成一键多值

  • 键值对

    • 一个整体, 在 JAVA 中使用 Entry 对象来表示

    • 使用场景 :
      购物车 -> 选择商品 -> 结算 …

             *每个店铺对应一个商品,  有时候一个有时候多个,  每个商品使用一个商品封装成一个对象来进行维护,  多个商品应当使用多个商品对象的单列集合装起来,  这样一个结算订单就有了多个商品*
      

    • 总结 : 遇到键对值 (一个对多个), 就使用双列集合

常用公共方法、实现关系

V put(K key,V value) : // 添加键值对, 返回被覆盖的值 (没有覆盖则null)
V remove(Object key) : // 根据键删除键值对, 返回被删除的键对应的值

boolean containsKey(Object key) : //判断集合指定键, 返回是或否
boolean containsValue(Object value) : //判断集合指定值, 返回是或否
     
void Clear() : // 清空所有的键值对
boolean isEmpty() : //判断集合是否为空
int size() : //集合的长度 (键值对个数)

常用双列集合

TreeMap (红黑树)
​ HashMap (哈希表)
​ LinkedHashMap (哈希表 + 双向链表)

使用介绍

HashMap 的底层逻辑

• put 方法 : 双列集合中的添加
  • put 方法执行中, 键和值会封装为一个 Entry(键值对) 对象
  • 但实际在计算应存入索引时, 是拿着键进行计算的, 和值没有关系
    (先调用对象计算原始哈希值, 再使用原始哈希值做一次哈希扰动, 然后再使用扰动过的哈希值做一次异或操作进行二次哈希, 最后再取余底层数组长度(16))…

方法演示

添加 : put(K key, V value)

/*  Map是接口, 接口不能直接用, 所以通过多态一个子类或实现类  */
Map<String, String> map = new HashMap<>(); 

// 对HashMap 进行操作
map.put("张三","北京"); //put: 添加一个键值对 一是键二是值
map.put("李四","北京"); // 键重复时警告, 右边重复则没事, 说明键的不可重, 值的可重
map.put("王五","北京");

//  北京 -> 仅一个
//  张三, 李四, 王五 -> 对应多个
System.out.println(map);// 打印成乱序, 是因为底层是哈希表

// **put方法的返回值 被替换掉的旧值
String str = map.put("lala", "北京");
String str2 = map.put("lala", "喵");
System.out.println(str);
// 返回被覆盖掉的旧值, 没有重复就直接存
System.out.println(str2);
// -- 该返回值一般不接收 --

put方法的细节 (修改)( 条件 : 如果出现重键, 保留新键替换旧键 )

删除 : remove(Object key)

/* Remove 根据键删除 */
Map<String,String> map = new HashMap<>();
map.put("张三","南宁");
map.put("李四","上海");
map.put("王五","南宁");
System.out.println(map);

map.remove("张三");
System.out.println(map);

//返回值
String accept = map.remove("王五");
System.out.println(accept); // 返回为被删除键对应的值 - > 南宁

• 清空, 非空, 大小, 内容
• clear()、IsEmpty()、Size()、2个Contain() 一个比键一个比值

Map<String,String> map = new HashMap<>();
map.put("牛","马");
map.put("羊","马");
map.put("猪","马");
map.put("屎","马");

System.out.println(map);
/*  判断是否存在指定数据  */
System.out.println(map.containsKey("牛"));  ->  true
System.out.println(map.containsValue("王"));  - > false
System.out.println("-------------------------------------------");

/*  清空,判断内容是否存在,判断非空 */
map.clear();
System.out.println(map);  ->  []
System.out.println(map.isEmpty());  ->  true
System.out.println(map.size());  ->  0

泛型为自定义类时

//    HashMap : 虽然说是键唯一,  但是底层依赖于哈希算法和内容比较
//    所以自定义类依然要重写 '两个哈希方法'
HashMap<Person,String> hm = new HashMap<>();
hm.put(new Person("张三",24),"上海");
hm.put(new Person("李四",23),"广东南宁");
hm.put(new Person("李四",23),"上海哈尔滨");
hm.put(new Person("王五",21),"上海");
hm.put(new Person("牛六",22),"上海");
System.out.println(hm);
// 没有重写两个哈希方法就会导致没有去重

System.out.println(hm);
//HashMap底层也是哈希表结构,自定义类不重写 'hashCode和equal' 就无法去重, 而我们经常用的Bean类就重写过 这两个方法

排序 : 使用TreeMap集合

//TreeMap : 键排序
TreeMap<Person,String> hm = new TreeMap<>();
hm.put(new Person("张三",24),"上海");
hm.put(new Person("李四",23),"广东南宁");
hm.put(new Person("李四",23),"上海哈尔滨");
hm.put(new Person("王五",21),"上海");
hm.put(new Person("牛六",22),"上海");
System.out.println(hm);
//类型转换异常, 不能转换为 Java.lang.Comparable,
//如果键是自定义类（如 Person），没有实现 Comparable 接口，就无法比较两个键，导致报错：
// ClassCastException: Person cannot be cast to java.lang.Comparable。

//总结 : 键排序 (实现Comparable接口, 重写comparable方法)

注意事项 : ** TreeMap 之所以可以在 HashCode 存储无序特性下进行排序, 实际上是因为他实现了Comparable 自然排序接口, 使用了 CompareTo 方法, 所以当我们使用 TreeMap 并指定泛型为自定义类时, 就需要重写 compareTo 方法**, 并且自定义类下要重写 hashCode() 和 equals(), 确保键的唯一性

LinkedHashMap 和 HashMap ↑一样的操作

// LinkedHashMap : 键唯一, 且可以保证存取顺序
LinkedHashMap<Person,String> hm = new LinkedHashMap<>();
hm.put(new Person("张三",23),"上海");
hm.put(new Person("李四",25),"南宁");
hm.put(new Person("王五",29),"此时");
System.out.println(hm);

下面统一讲

Map 集合中的三种遍历方式

• 摘要

  1. 通过键找值
     V get(Object key) 根据键查找对应的值
     Set keySet() 获取 Map 集合中所有的值

     – 配合使用 : 通过 Set 拿到每一个键, 再通过get 拿到每一个值 –

  2. 通过键值对对象获取键和值

  3. 通过forEach遍历

• 遍历方式演示

  • 第一种遍历 (keySet,get)

  | 第一种方式:  结合两种方法 |
  //V get(Object key) : 根据键找对应的值
  //Set<K> keSet() : 获取 Map 集合中所有的键
  
  HashMap<String,String> hs = new HashMap<>();
  hs.put("张三","北京");
  hs.put("李四","上海");
  hs.put("王五","牛牛");
  
  // 获取到所有的键
  Set<String> set = hs.keySet();
  System.out.println(hs);
  
  //遍历的set集合
  for(String key:set){ // 获取泛型为String类型的键
      //调用get方法
      String content = hs.get(key);//根据键拿对应的值
      System.out.println("键: "+key+" 值: "+content);
  }
  

  • 第二种遍历 (封装为Entry)

  // 第二种
  // 通过键值对对象获取键和值  Map.Entry(内部类)
  // 遍历要使用到的方法名 :
  // getKey() : 获取键
  // getValue() : 获取值
  // Set<Map.Entry<K,V>> entrySet() : 获取集合中所有的键值对对象 (接收getKey和getValue)
  // 配合使用, 获取键, 获取值, 根据键和值获取对象
  
  HashMap<String,String> hs = new HashMap<>();
  hs.put("张三","北京");
  hs.put("李四","上海");
  hs.put("王五","牛牛");
  
  // 1. 获取所有的键值对对象
  Set<Map.Entry<String,String>> entrySet = hs.entrySet();
  // 格式剖析 : Set接口指定泛型, Map 中的内部类 Entry 也要指定泛型,键和值都是String 没了
  
  // 2. 遍历set集合获取每一个键值对对象
  for(Map.Entry<String,String> keyV : entrySet){
      // 3. 通过键值对对象, 获取键和值
      System.out.println(keyV.getKey() + " | " + keyV.getValue());
  }
  
  /*
          总结 :
          1.调用 entrySet方法获取所有的键值对对象 (得到的是Set集合)
          2.遍历 Set 集合, 获取每一个键值对对象
          3. 通过键值对对象的 getKey() getValue() 获取键和值
   */
  

  • 第三种遍历方式 (forEach)

  // Map 集合中的三种遍历方式
  // 通过foreach 方法便利
  /* default void forEach(
          BiConsumer<? super K,? super V> action
     )
     -- 遍历 Map 集合 ,获取键和值
  */
  HashMap<String,String> hs = new HashMap<>();
  hs.put("张三","北京");
  hs.put("李四","上海");
  hs.put("王五","牛牛");
  
  /*  一个函数式接口  */
  hs.forEach(new BiConsumer<String, String>() {
      @Override
      public void accept(String s1, String s2) {
          System.out.println(s1 + " | " + s2);
      }
  });
  

Map 集合练习

/*
    Map 集合练习 (单列集合结合双列集合)
    定义一个Map集合, 键用表示身份名称, 值表示市
    添加完毕后, 遍历结果:
    格式如下:
    江苏省 = 南京市, 扬州市, 苏州市, 无锡市, 常州市
    湖北省 = 武汉市, 孝感市, 十堰市, 宜昌市, 鄂州市
    四川省 = 成都市, 绵阳市, 自贡市, 攀枝花市, 泸州市
 */
| 思路 : 单列集合做值, 双列集合做键 |

ArrayList<String> list = new ArrayList<>();
HashMap<String,ArrayList<String>> map = new HashMap<>();
Collections.addAll(list,"南京市","扬州市","苏州市","无锡市","常州市");

| 结合 |
map.put("江苏省",list);

ArrayList<String> list2 = new ArrayList<>();
Collections.addAll(list2,"武汉市","孝感市","十堰市","宜昌市","鄂州市");
map.put("湖北省",list2);


ArrayList<String> list3 = new ArrayList<>();
Collections.addAll(list3,"成都市","绵阳市","自贡市","攀枝花市","泸州市");
map.put("四川省",list3);

map.forEach((k, v) -> System.out.println(k+" = "+v));
// 第二种遍历方式回温
System.out.println("-----------------------------------");

| 封装为键值对对象 |
Set<Map.Entry<String, ArrayList<String>>> entries = map.entrySet();

| 遍历 |
for (Map.Entry<String, ArrayList<String>> entry : entries) {
    System.out.println(entry.getKey() + " = " + entry.getValue());
}

有意思的底层

以下是对 Map 接口详解的进一步拓展，包含数据结构、底层实现和内存优化等方面的深入分析。

Map 的底层数据结构

HashMap 的底层结构

1. 数组 + 链表 + 红黑树：

   • HashMap 的底层是一个数组（哈希桶），每个桶存储一个链表或红黑树。
   • 当发生哈希冲突（即多个键映射到相同的桶时），HashMap 会将这些键值对组织成一个链表存储。
   • 如果链表长度超过一定阈值（默认 8），链表会被转换为红黑树，提升查找效率。
   • 如果桶内元素数量小于阈值（默认 6），红黑树会退化为链表。

2. 哈希计算逻辑：

   • 键的哈希值由 hashCode 方法计算，通过扰动函数进一步优化，使其分布更均匀。
   • 通过 (n - 1) & hash 确定哈希桶的索引（n 是数组长度）。
   • 这种位运算比取模操作更高效。

3. 动态扩容：

   • 当 HashMap 的元素数量超过数组容量的 75%（默认负载因子 0.75），数组会扩容为原大小的两倍，并重新计算所有键的哈希位置。

TreeMap 的底层结构

1. 红黑树：

   • TreeMap 基于红黑树实现，是一种自平衡二叉搜索树。
   • 插入键时，TreeMap 会根据键的自然顺序（或自定义比较规则）排列节点。
   • 查找、插入和删除的时间复杂度为 O(log n)。

2. 排序功能：

   • 键需实现 Comparable 接口，或在 TreeMap 构造时传入一个自定义 Comparator。

3. LinkedHashMap 的底层结构

• 哈希表 + 双向链表：

  • LinkedHashMap 是 HashMap 的子类，保留了键值对插入的顺序。

  • 通过双向链表维护插入顺序或访问顺序（可配置）。

  • 适用于需要有序遍历的场景，如缓存实现。

Map 的性能优化

1. 选择合适的实现类

• 如果不关心顺序，优先使用 HashMap，其增删改查操作最为高效（均摊复杂度为 O(1)）。
• 如果需要按插入顺序或访问顺序遍历键值对，选择 LinkedHashMap。
• 如果需要键自动排序，选择 TreeMap。

总结与比较