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

特别注意：

• 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);
}

特别注意：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;
  }
}

实际上，很多 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);//可以传入多个字段
}

自动扩容

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ⁿ，因此，实际数组长度被初始化为比 10000 大的 16384（2¹⁴）。

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

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

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

运行结果：

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

TreeMap

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

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

       ┌───┐
       │Map│
       └───┘
         ▲
    ┌────┴─────┐
    │          │
┌───────┐ ┌─────────┐
│HashMap│ │SortedMap│
└───────┘ └─────────┘
               ▲
               │
          ┌─────────┐
          │ TreeMap │
          └─────────┘

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;
  }
}

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)

自定义排序算法的演示：

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 + "}";
  }
}

输出结果：

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

其他注意事项：

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