Map

高效通过key快速查找value（元素）

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Student s = new Student("Xiao Ming", 99);
        Map<String, Student> map = new HashMap<>();
        map.put("Xiao Ming", s); // 将"Xiao Ming"和Student实例映射并关联
        Student target = map.get("Xiao Ming"); // 通过key查找并返回映射的Student实例
        System.out.println(target == s); // true，同一个实例
        System.out.println(target.score); // 99
        Student another = map.get("Bob"); // 通过另一个key查找
        System.out.println(another); // 未找到返回null
    }
}

class Student {
    public String name;
    public int score;
    public Student(String name, int score) {
        this.name = name;
        this.score = score;
    }
}

Map<K, V>是一种键-值映射表

• put(K key, V value)
• V get(K key)
• boolean containsKey(K key)：查询某个key是否存在

如果key不存在，则返回null，和List类似，Map也是接口，最常用的实现类是HashMap

如果对同一个key调用两次put方法，分别放入不同的value

Map<String, Integer> map = new HashMap<>();
map.put("xiao", 20);
System.out.println(map.put("xiao", 22));
System.out.println(map.get("xiao"));

实际上put()方法的签名是V put(K key, V value)，如果放入的key已经存在，put()方法会返回删除的旧的value，否则返回null

遍历

要遍历key可以使用for each循环遍历Map实例的keySet()方法返回的Set集合

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("apple", 123);
        map.put("pear", 456);
        map.put("banana", 789);
        for (String key : map.keySet()) {
            Integer value = map.get(key);
            System.out.println(key + " = " + value);
        }
    }
}

同时遍历key和value可以使用for each循环遍历Map对象的entrySet()集合，它包含每一个key-value映射

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("apple", 123);
        map.put("pear", 456);
        map.put("banana", 789);
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            String key = entry.getKey();
            Integer value = entry.getValue();
            System.out.println(key + " = " + value);
        }
    }
}

遍历Map时，输出的key不是有序的

HashCode

HashMap之所以能根据key直接拿到value，原因时它内部通过空间换时间的方法，用一个大数组存储所有的value，并根据key直接计算出value应该存在哪个索引

equals

当我们放入Map的key是字符串"a"，但是，当我们获取value时，传入的变量不一定就是放入的那个key对象

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        String key1 = "a";
        Map<String, Integer> map = new HashMap<>();
        map.put(key1, 123);

        String key2 = new String("a");
        map.get(key2); // 123

        System.out.println(key1 == key2); // false
        System.out.println(key1.equals(key2)); // true
    }
}

在Map的内部，对key的比较是通过equals()实现的，和List查找元素要正确覆写equals()是一样的

而String已经正确覆写了equals()

通过key计算索引的方式就是调用key对象的hashCode()方法，它返回一个int整数，HashMap就是通过这个方法直接定位key对应的value的索引，继而直接返回value

因此正确使用Map必须保证：

• 正确覆写equals()
• 正确覆写hashCode()

public class Person {
    String firstName;
    String lastName;
    int age;

    @Override
    int hashCode() {
        int h = 0;
        h = 31 * h + firstName.hashCode();
        h = 31 * h + lastName.hashCode();
        h = 31 * h + age;
        return h;
    }
}

但是如果firstName或lastName为null，可能会抛出NullPointerException，所以经常借助Objects.hash()

int hashCode() {
    return Objects.hash(firstName, lastName, age);
}

延伸

hashCode()返回的int范围高达21亿，那么内部的数组得有多大

实际上HashMap初始化时默认的数组大小只有16，无论它的hashCode有多大，都可以通过&

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

把索引确定在0~15

添加的key-value超过大小时，HashMap会在内部自动扩容，改变计算方式

int index = key.hashCode() & 0x1f; // 0x1f = 31

由于扩容会导致重新分布已有的key-value，所以频繁扩容对HashMap的性能影响很大

hashCode()编写的越好，HashMap的工作效率越高

EnumMap

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

Map<DayOfWeek, String> map = new EnumMap<>(DayOfWeek.class);
map.put(DayOfWeek.TUESDAY, "Tuesday");
System.out.println(map);
System.out.println(map.get(DayOfWeek.TUESDAY));

TreeMap

HashMap内部是无序的，而SortedMap在内部会对Key排序，注意到SortedMap是接口，它的实现类是TreeMap

SortedMap保证遍历时以Key的顺序来进行排序

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> map = new TreeMap<>();
        map.put("orange", 1);
        map.put("apple", 2);
        map.put("pear", 3);
        for (String key : map.keySet()) {
            System.out.println(key);
        }
        // apple, orange, pear
    }
}

使用TreeMap时，放入的Key必须实现Comparable接口，String、Integer这些类已经实现了Comparable接口，因此可以直接作为Key使用

如果没实现Comparable接口，那么在创建TreeMap时同时指定一个自定义排序算法

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Map<Person, Integer> map = new TreeMap<>(new Comparator<Person>() {
            public int compare(Person p1, Person p2) {
                return p1.name.compareTo(p2.name);
            }
        });
        map.put(new Person("Tom"), 1);
        map.put(new Person("Bob"), 2);
        map.put(new Person("Lily"), 3);
        for (Person key : map.keySet()) {
            System.out.println(key);
        }
        // {Person: Bob}, {Person: Lily}, {Person: Tom}
        System.out.println(map.get(new Person("Bob"))); // 2
    }
}

class Person {
    public String name;
    Person(String name) {
        this.name = name;
    }
    public String toString() {
        return "{Person: " + name + "}";
    }
}

Comparator接口要求实现一个比较算法，负责比较传入的两个元素

另外，注意到Person类并没有覆写equals()和hashCode()，因为TreeMap不使用这两个

看一个复杂的例子，定义Student类，并用分数score进行排序

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Map<Student, Integer> map = new TreeMap<>(new Comparator<Student>() {
            public int compare(Student p1, Student p2) {
                return p1.score > p2.score ? -1 : 1;
            }
        });
        map.put(new Student("Tom", 77), 1);
        map.put(new Student("Bob", 66), 2);
        map.put(new Student("Lily", 99), 3);
        for (Student key : map.keySet()) {
            System.out.println(key);
        }
        System.out.println(map.get(new Student("Bob", 66))); // null?
    }
}

class Student {
    public String name;
    public int score;
    Student(String name, int score) {
        this.name = name;
        this.score = score;
    }
    public String toString() {
        return String.format("{%s: score=%d}", name, score);
    }
}

在查找时出现了null，在比较的时候，我们只返回了-1、1，并没有判断相等的情况，也就是没有返回0，所以TreeMap工作出问题了。于是代码修改如下

public int compare(Student p1, Student p2) {
    if (p1.score == p2.score) {
        return 0;
    }
    return p1.score > p2.score ? -1 : 1;
}

或者借助Integer.compare(int, int)也可以返回正确的比较结果