从 01 开始 从 01 开始
首页
  • 📚 计算机基础

    • 计算机简史
    • 数字电路
    • 计算机组成原理
    • 操作系统
    • Linux
    • 计算机网络
    • 数据库
    • 编程工具
    • 装机
  • 🎨 前端

    • Node
  • JavaSE
  • Java 高级
  • JavaEE

    • 构建、依赖管理
    • Ant
    • Maven
    • 日志框架
    • Junit
    • JDBC
    • XML-JSON
  • JavaWeb

    • 服务器软件
    • 环境管理和配置管理-科普篇
    • Servlet
  • Spring

    • Spring基础
  • 主流框架

    • Redis
    • Mybatis
    • Lucene
    • Elasticsearch
    • RabbitMQ
    • MyCat
    • Lombok
  • SpringMVC

    • SpringMVC 基础
  • SpringBoot

    • SpringBoot 基础
  • Windows 使用技巧
  • 手机
  • 最全面的输入法教程
  • 最全面的浏览器教程
  • Office
  • 图片类工具
  • 效率类工具
  • RSS
  • 码字工具
  • 各大平台
  • 校招
  • 五险一金等
  • 职场规划
  • 关于离职
  • 杂谈
  • 📖 读书

    • 读书工具
    • 读书笔记
  • 🌍 英语

    • 从零开始学英语
    • 英语兔的相关视频
    • Larry 想做技术大佬的相关视频
  • 🏛️ 政治

    • 反腐
    • GFW
    • 404 内容
    • 审查与自我审查
    • 互联网
    • 战争
  • 💰 经济

    • 关于税
    • 理财
  • 💪 健身

    • 睡眠
    • 皮肤
    • 口腔健康
    • 学会呼吸
    • 健身日志
  • 🏠 其他

    • 驾驶技能
    • 租房与买房
    • 厨艺
  • 电影

    • 电影推荐
  • 电视剧
  • 漫画

    • 漫画软件
    • 漫画推荐
  • 游戏

    • Steam
    • 三国杀
    • 求生之路
  • 小说
  • 关于本站
  • 关于博主
  • 打赏
  • 网站动态
  • 友人帐
  • 从零开始搭建博客
  • 搭建邮件服务器
  • 本站分享
  • 🌈 生活

    • 2022
    • 2023
    • 2024
    • 2025
  • 📇 文章索引

    • 文章分类
    • 文章归档

晓林

程序猿,自由职业者,博主,英语爱好者,健身达人
首页
  • 📚 计算机基础

    • 计算机简史
    • 数字电路
    • 计算机组成原理
    • 操作系统
    • Linux
    • 计算机网络
    • 数据库
    • 编程工具
    • 装机
  • 🎨 前端

    • Node
  • JavaSE
  • Java 高级
  • JavaEE

    • 构建、依赖管理
    • Ant
    • Maven
    • 日志框架
    • Junit
    • JDBC
    • XML-JSON
  • JavaWeb

    • 服务器软件
    • 环境管理和配置管理-科普篇
    • Servlet
  • Spring

    • Spring基础
  • 主流框架

    • Redis
    • Mybatis
    • Lucene
    • Elasticsearch
    • RabbitMQ
    • MyCat
    • Lombok
  • SpringMVC

    • SpringMVC 基础
  • SpringBoot

    • SpringBoot 基础
  • Windows 使用技巧
  • 手机
  • 最全面的输入法教程
  • 最全面的浏览器教程
  • Office
  • 图片类工具
  • 效率类工具
  • RSS
  • 码字工具
  • 各大平台
  • 校招
  • 五险一金等
  • 职场规划
  • 关于离职
  • 杂谈
  • 📖 读书

    • 读书工具
    • 读书笔记
  • 🌍 英语

    • 从零开始学英语
    • 英语兔的相关视频
    • Larry 想做技术大佬的相关视频
  • 🏛️ 政治

    • 反腐
    • GFW
    • 404 内容
    • 审查与自我审查
    • 互联网
    • 战争
  • 💰 经济

    • 关于税
    • 理财
  • 💪 健身

    • 睡眠
    • 皮肤
    • 口腔健康
    • 学会呼吸
    • 健身日志
  • 🏠 其他

    • 驾驶技能
    • 租房与买房
    • 厨艺
  • 电影

    • 电影推荐
  • 电视剧
  • 漫画

    • 漫画软件
    • 漫画推荐
  • 游戏

    • Steam
    • 三国杀
    • 求生之路
  • 小说
  • 关于本站
  • 关于博主
  • 打赏
  • 网站动态
  • 友人帐
  • 从零开始搭建博客
  • 搭建邮件服务器
  • 本站分享
  • 🌈 生活

    • 2022
    • 2023
    • 2024
    • 2025
  • 📇 文章索引

    • 文章分类
    • 文章归档
  • JavaSE

  • JavaSenior

    • 反射

    • 注解

    • 集合类

      • 集合介绍
      • List
      • Map
        • 简单复习下哈希表
        • Map常用方法
        • 遍历 Map
        • equals 和 hashcode
        • 自动扩容
        • EnumMap
        • TreeMap
        • 参考
      • Set
      • Queue
      • Stack
      • Collections
    • 线程

  • JavaEE

  • JavaWeb

  • Spring

  • 主流框架

  • SpringMVC

  • SpringBoot

  • Java
  • JavaSenior
  • 集合类
2022-12-31
目录

Map

# Map

在工作中,我们经常需要通过某个值去查询符合条件的对象,用 List 来实现存在效率非常低的问题,因为平均需要扫描一半的元素才能确定。

而 Map 这种键值(key-value)映射表的数据结构,作用就是能高效通过 key 快速查找 value(元素)。

Map 也是一个接口,最常用的实现类是 HashMap(数据结构里的哈希表)。

# 简单复习下哈希表

哈希表查找的速度非常快,其原理就是根据空间来换时间。

直接定义一个很大的数组,当要存放某个 value 的时候,就会根据 key 值计算出一个索引值,这个索引值就是该 value 在数组的下标,然后讲 value 放到 数组[索引] 处。

当要查找某个元素的时候,就直接根据 key 计算出索引,然后去 数组[索引] 处取出就可以。

计算索引值的方法就叫哈希算法,这里还可能会遇到冲突的问题:多个 key 值的索引值一致。解决冲突的办法有很多,HashMap 是用链地址法来处理冲突。

# Map常用方法

  • V put(K key, V value):存放元素。
  • V get(Object key):获取元素。如果 key 不存在,返回 null。
  • remove(Object key):移出元素
  • containsValue(Object value):查询某个 Value 是否存在
  • boolean containsKey(K key):查询某个 key 是否存在
  • int size():元素个数

入门案例:

    Map<Integer,String> myWives = new HashMap<>();
    myWives.put(1, "爱莉希雅");
    myWives.put(2, "布洛尼娅");
    myWives.put(3, "梅比乌斯");

    String alxy = myWives.get(1);
    System.out.println(alxy); // 莉希雅

    myWives.put(4, null);
    myWives.remove(4);
    System.out.println(myWives.containsKey(1)); //true
    System.out.println(myWives.containsValue("爱莉希雅"));  //true
    System.out.println(myWives.size()); //3
1
2
3
4
5
6
7
8
9
10
11
12
13

特别注意:

  • Map 中不存在重复的 key,因为放入相同的 key,只会把原有的 key-value 对应的 value 给替换掉。如果放入的 key已存在,put方法会返回被删除的旧的 value,否则返回 null。
  • key不能重复,但 value是可以重复。

关于 get 方法的细节:

举个例子,给某个方法参数里传了一个 Map<String, String>, 但是方法参数里没有写是什么类型:

public void (Map map)
1

那么在获取元素的时候,默认是 Object 类型,得强转后才能得到 String:

String a = (String)map.get(get);
1

而如果方法的参数写完整了:

public void (Map<String, String> map)
1

那么在获取元素的时候就不用强转

String a = map.get(get);
1

# 遍历 Map

有两种方式遍历:

  • 使用 for each 循环遍历 Map 实例的 keySet() 方法返回的 Set 集合,它包含不重复的 key 的集合
  • 使用 for each 循环遍历 Map 对象的 entrySet() 集合,它包含每一个 key-value 映射
Map<Integer,String> myWives = new HashMap<>();
myWives.put(1, "爱莉希雅");
myWives.put(2, "布洛尼娅");
myWives.put(3, "梅比乌斯");

for (int key : myWives.keySet()) {
  String value = myWives.get(key);
  System.out.println(key + " = " + value);
}

for(Map.Entry<Integer, String> entry : myWives.entrySet()){
  int key = entry.getKey();
  String value = entry.getValue();
  System.out.println(key + " = " + value);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

特别注意:Map 存储的是 key-value 的映射关系,并且不保证顺序。在遍历的时候,遍历的顺序既不一定是 put() 时放入的 key 的顺序,也不一定是 key 的排序顺序。

# equals 和 hashcode

和 List 查找元素需要正确覆写 equals() 是一样的,正确使用 Map 必须保证:作为 key 的对象必须正确覆写 equals() 方法。对于放入 HashMap 的 value 对象,则没有任何要求。

我们经常使用 String 作为 key,因为 String 已经正确覆写了 equals() 方法。但如果我们放入的 key 是一个自己写的类,就必须保证正确覆写了 equals() 方法。

我们来看个案例:

import java.util.HashMap;

public class LearnMap3 {
  public static void main(String[] args) {
    Wife wife1 = new Wife("爱丽希雅");
    Wife wife2 = new Wife("爱丽希雅");
    HashMap<Wife, String> myWives = new HashMap<>();
    myWives.put(wife1, "My fisrt wife is 爱丽希雅!");
    System.out.println(myWives.get(wife2)); //null
  }
}

class Wife{
  private String name;

  public String getName() {
    return name;
  }

  public void setName(String name) {
    this.name = name;
  }

  public Wife(String name){
    this.name = name;
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

实际上,很多 Hash 相关的集合类,都是通过 key 对象的 hashCode() 来计算哈希值,然后根据哈希值存放。如果我们没有重写 hashCode() 方法,那么默认就是调用 Object 类的 hashCode(),其默认返回的是对象的哈希地址,这也是为什么上述代码会返回 null 的原因:两者的 hashCode 不同。

因此,正确使用 Map 必须保证:

  1. 作为 key 的对象必须正确覆写 equals() 方法,相等的两个 key 实例调用 equals() 必须返回 true;
  2. 作为 key 的对象还必须正确覆写 hashCode() 方法,且 hashCode() 方法要严格遵循以下规范:
  • 如果两个对象相等,则两个对象的 hashCode() 必须相等;
  • 如果两个对象不相等,则两个对象的 hashCode() 尽量不要相等。

上述第一条规范是正确性,必须保证实现,否则 HashMap 不能正常工作。

而第二条如果尽量满足,则可以保证查询效率,因为不同的对象,如果返回相同的 hashCode(),会造成 Map 内部存储冲突,使存取的效率下降。

我们可以借助 Objects.hash() 来计算哈希值。

int hashCode() {
    return Objects.hash(name);//可以传入多个字段
}
1
2
3

# 自动扩容

HashMap 初始化时默认的数组大小只有 16,任何 key,无论它的 hashCode() 有多大,都可以简单地通过:

int index = key.hashCode() & 0xf; // 0xf = 15
1

把索引确定在 0~15,即永远不会超出数组范围,上述算法只是一种最简单的实现。

添加超过一定数量的 key-value 时,HashMap 会在内部自动扩容,每次扩容一倍,即长度为 16 的数组扩展为长度 32,相应地,需要重新确定 hashCode() 计算的索引位置。

由于扩容会导致重新分布已有的 key-value,所以,频繁扩容对 HashMap 的性能影响很大。如果我们确定要使用一个容量为 10000 个 key-value 的 HashMap,更好的方式是创建 HashMap 时就指定容量:

Map<String, Integer> map = new HashMap<>(10000);
1

虽然指定容量是 10000,但 HashMap 内部的数组长度总是 2n,因此,实际数组长度被初始化为比 10000 大的 16384(214)。

# EnumMap

如果作为 key 的对象是 enum 类型,那么,还可以使用 Java 集合库提供的一种 EnumMap,它在内部以一个非常紧凑的数组存储 value,并且根据 enum 类型的 key 直接定位到内部数组的索引,并不需要计算 hashCode(),不但效率最高,而且没有额外的空间浪费。

我们以之前讲过的时间枚举类为例

    Map<DayOfWeek, String> dMap = new EnumMap<>(DayOfWeek.class);
    dMap.put(DayOfWeek.MONDAY, "星期一");
    dMap.put(DayOfWeek.THURSDAY, "星期二");
    dMap.put(DayOfWeek.WEDNESDAY, "星期三");
    dMap.put(DayOfWeek.THURSDAY, "星期四");
    dMap.put(DayOfWeek.FRIDAY, "星期五");
    dMap.put(DayOfWeek.SATURDAY, "星期六");
    dMap.put(DayOfWeek.SUNDAY, "星期日");

    System.out.println(dMap);
    System.out.println(dMap.get(DayOfWeek.MONDAY));
1
2
3
4
5
6
7
8
9
10
11

需要注意的是:创建 EnumMap 需要传入 class 对象,否则会报错

错误: 无法推断EnumMap<>的类型参数
1

运行结果:

{MONDAY=星期一, WEDNESDAY=星期三, THURSDAY=星期四, FRIDAY=星期五, SATURDAY=星期六, SUNDAY=星期日}  
星期一
1
2

# TreeMap

之前我们说过 HashMap,由于它的实现原理就决定了其内部的 key 是无序的,遍历的时候需要注意。

但有一种 Map,它在内部会对 Key 进行排序,这种 Map 就是 SortedMap。SortedMap 是接口,实现类是 TreeMap。

       ┌───┐
       │Map│
       └───┘
         ▲
    ┌────┴─────┐
    │          │
┌───────┐ ┌─────────┐
│HashMap│ │SortedMap│
└───────┘ └─────────┘
               ▲
               │
          ┌─────────┐
          │ TreeMap │
          └─────────┘
1
2
3
4
5
6
7
8
9
10
11
12
13
14

SortedMap 保证遍历时以 Key 的顺序来进行排序,其依靠的是 Comparable 接口。所以,作为 Key 的类型要么实现 Comparable 接口,要么在创建 TreeMap 时同时指定一个自定义排序算法。否则,会报错的,例如:

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

public class LearnTreeMap {
  public static void main(String[] args) {
    Map<Wife, String> myWives = new TreeMap<>();
    Wife wife1 = new Wife("爱丽希雅");
    Wife wife2 = new Wife("爱丽希雅");
    myWives.put(wife1, "My fisrt wife is 爱丽希雅!");
    myWives.put(wife2, "My second wife is 爱丽希雅!");
  }
}


class Wife{
  private String name;

  public String getName() {
    return name;
  }

  public void setName(String name) {
    this.name = name;
  }

  public Wife(String name){
    this.name = name;
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
javac LearnTreeMap.java  -encoding utf8
java LearnTreeMap
Exception in thread "main" java.lang.ClassCastException: Wife cannot be cast to java.lang.Comparable
        at java.util.TreeMap.compare(TreeMap.java:1294)
        at java.util.TreeMap.put(TreeMap.java:538)
        at LearnTreeMap.main(LearnTreeMap.java:9)
1
2
3
4
5
6

自定义排序算法的演示:

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

public class LearnTreeMap {
  public static void main(String[] args) {
    Map<Wife, String> myWives = new TreeMap<>(new Comparator<Wife>() {
      public int compare(Wife w1, Wife w2){
        return w1.getName().compareTo(w2.getName());
      }
    });
    Wife wife1 = new Wife("ai li xi ya");
    Wife wife2 = new Wife("bu luo ni ya");
    Wife wife3 = new Wife("mei bi wu si");
    myWives.put(wife3, "My fisrt wife is 梅比乌斯!");
    myWives.put(wife2, "My second wife is 布洛尼娅!");
    myWives.put(wife1, "My third wife is 爱丽希雅!");

    for (Wife wifeKey : myWives.keySet()) {
      System.out.println(wifeKey);
    }
  }
}


class Wife{
  private String name;

  public String getName() {
    return name;
  }

  public void setName(String name) {
    this.name = name;
  }

  public Wife(String name){
    this.name = name;
  }

  public String toString(){
    return "{Wife: " + name + "}";
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

输出结果:

{Wife: ai li xi ya}
{Wife: bu luo ni ya}
{Wife: mei bi wu si}
1
2
3

其他注意事项:

  • TreeMap 不使用 equals() 和 hashCode()。

# 参考

为什么要重写 hashcode 和 equals 方法?初级程序员在面试中很少能说清楚。 - hsm_computer - 博客园 (opens new window)

为了彻底搞懂 hashCode,我连 JDK 的源码都没放过 - 知乎 (opens new window)

编写 equals 和 hashCode - 廖雪峰的官方网站 (opens new window)

深入理解 hashcode 和 hash 算法 - 简书 (opens new window)

HashMap 面试必问的数据结构相关知识总结 - 菜鸟小于 - 博客园 (opens new window)

上次更新: 2024/10/1 18:45:09
List
Set

← List Set→

最近更新
01
吐槽一下《僵尸校园》
05-15
02
2025 年 4 月记
04-30
03
山西大同 “订婚强奸案” 将会给整个社会带来的影响有多严重? - 知乎 转载
04-26
更多文章>
Theme by Vdoing | Copyright © 2022-2025 | 粤 ICP 备 2022067627 号 -1 | 粤公网安备 44011302003646 号 | 点击查看十年之约
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式