Map

介绍

Map是一种键值（Key - value）映射表的数据结构，作用是高效的通过key快速的查找value（1 ~ 的复杂度）
Map也是一个接口，最常见的实现类是HashMap。
Map中不存在重复的key，因为放入相同的key，只会把原有的key-value对应的value给替换掉。

遍历Map

对Map来说，要遍历key可以使用for each循环遍历Map实例的keySet()方法返回的Set集合，它包含不重复的key的集合：

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映射：

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和List不同的是，Map存储的是key-value的映射关系，并且，它不保证顺序。在遍历的时候，遍历的顺序既不一定是put()时放入的key的顺序，也不一定是key的排序顺序。使用Map时，任何依赖顺序的逻辑都是不可靠的。以HashMap为例，假设我们放入"A"，"B"，"C"这3个key，遍历的时候，每个key会保证被遍历一次且仅遍历一次，但顺序完全没有保证，甚至对于不同的JDK版本，相同的代码遍历的输出顺序都是不同的！
为什么Map可以快速的通过Key查找value是因为空间换时间，直接通过Key计算出索引，就可以通过索引直接拿到value。

编写equals和hashCode

因为在Map的内部，对key做比较是通过equals()实现的（也就是说，两个String类，可能地址不一样，但是内容一样，查找到的value就是一样的），这一点和List查找元素需要正确覆写equals()是一样的，即正确使用Map必须保证：作为key的对象必须正确覆写equals()方法。
因此我们自己编写的类作为Key是就得自己编写equals和hashCode这两个方法。
正确使用Map必须保证：

1. 作为key的对象必须正确覆写equals()方法，相等的两个key实例调用equals()必须返回true；
2. 作为key的对象还必须正确覆写hashCode()方法，且hashCode()方法要严格遵循以下规范：

• 如果两个对象相等，则两个对象的hashCode()必须相等；
• 如果两个对象不相等，则两个对象的hashCode()尽量不要相等。

即对应两个实例a和b：

• 如果a和b相等，那么a.equals(b)一定为true，则a.hashCode()必须等于b.hashCode()；
• 如果a和b不相等，那么a.equals(b)一定为false，则a.hashCode()和b.hashCode()尽量不要相等。

上述第一条规范是正确性，必须保证实现，否则HashMap不能正常工作。
而第二条如果尽量满足，则可以保证查询效率，因为不同的对象，如果返回相同的hashCode()，会造成Map内部存储冲突，使存取的效率下降。
编写equals可以看这篇文章，写法是一样的
编写hashCode，对于Person类来说：

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

有些引用类已经实现了hashCode()方法，我们直接使用就可以了，这里每次计算使用了31 * h，可以大致看成将h左移了5位，这样就可以将h均匀分布到整个int的范围内。
注意：上面的hahsCode()实现，只能适用于字段非null,如果引用字段为null，我们就要处理这种情况，这里不再实现。通过情况下我们在计算hashCode()的时候，经常借助Objects.hash()来计算：

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

拿到索引

为了能快速的拿到索引，通常情况下是对计算出来的hashCode()做取模运算，但是HashMap中，为了追求效益，直接将HashMap的默认容量改成了2（而不是之前的素数），这样拿到索引的时候就可以直接对hashCode()进行 & 运算，直接拿到对应的索引。
实际上HashMap初始化时默认的数组大小只有16，任何key，无论它的hashCode()有多大，都可以简单地通过：

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

频繁扩容对HashMap的性能影响很大。如果我们确定要使用一个容量为10000个key-value的HashMap，更好的方式是创建HashMap时就指定容量：

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

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

hash冲突

如何两个key的值hash值一样，于是在HashMap对应的索引就会转换成链表

EnumMap

因为HashMap是一种通过对key计算hashCode()，通过空间换时间的方式，直接定位到value所在的内部数组的索引，因此，查找效率非常高。
如果作为key的对象是enum类型，那么，还可以使用Java集合库提供的一种EnumMap，它在内部以一个非常紧凑的数组存储value，并且根据enum类型的key直接定位到内部数组的索引，并不需要计算hashCode()，不但效率最高，而且没有额外的空间浪费。
使用EnumMap的时候，根据面向抽象编程的原则，应持有Map接口。

TreeMap

有一种Map，它在内部会对Key进行排序，这种Map就是SortedMap。注意到SortedMap是接口，它的实现类是TreeMap。
作为SortedMap的Key必须实现Comparable接口，或者传入Comparator接口；
Comparator接口要求实现一个compare()比较方法，它负责比较传入的两个元素a和b，如果a<b，则返回负数，通常是-1，如果a==b，则返回0，如果a>b，则返回正数，通常是1。TreeMap内部根据比较结果对Key进行排序。

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

这种情况15行代码会返回null，因为在比较p1.score和p2.score相等的时候，它并没有返回0！如下修改：

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) {
                if (p1.score == p2.score) return 0;
                return p1.score > p2.score ? -1 : 1;
                //或者
                return Integer.compare(p1.score,p2.score);
            }
        });
        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);
    }
}

要严格按照compare()规范实现比较逻辑，否则，TreeMap将不能正常工作。