Map

# 02.Map

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

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

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

‍

# 简单复习下哈希表

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

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

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

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

‍

# `Map`常用方法

V put(K key, V value)：存放元素。
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)

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

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

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

public void (Map<String, String> map)

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

String a = map.get(get);

‍

# 遍历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必须保证：

作为key的对象必须正确覆写equals()方法，相等的两个key实例调用equals()必须返回true；
作为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

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

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

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

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

虽然指定容量是10000，但HashMap内部的数组长度总是2^n^，因此，实际数组长度被初始化为比10000大的16384（2^14^）。

‍

# 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<>的类型参数

‍

运行结果：

{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)

在GitHub上编辑此页

上次更新: 2023/2/13 11:41:44

← List Set→

Map