Java基础（旧文档导入） - Map - 《程序人生》

map简介
遍历Map
hashMap原理和前提：equals和hashCode
- hashcode
使用EnumMap
TreeMap
Properties

map简介

Map是一种键-值映射表，当我们调用put(K key, V value)方法时，就把key和value做了映射并放入Map。当我们调用V get(K key)时，就可以通过key获取到对应的value。如果key不存在，则返回null。和List类似，Map也是一个接口，最常用的实现类是HashMap。
如果只是想查询某个key是否存在，可以调用boolean containsKey(K key)方法。
注意：如果放入重复的key-value并不会有问题，但是一个key只能关联一个value，在输入一个重复的key-value时，原来的旧value会被替换掉，并作为put()方法的返回对象，如果不存在重复的key-value(即put一个新的值键对)返回null。
虽然不能有多个重复key，但是value是可以重复的。

遍历Map

若要遍历key可以使用foreach去遍历Map实例的KeySet()方法返回的Set集合。
若要遍历key和value可以使用foreach去遍历Map实例的entrySet()方法返回的集合，他包含每一个key-value映射。
注意在遍历时，和List不同，不能保证顺序。

`hashMap`原理和前提：`equals`和`hashCode`

Map能够根据key直接拿到value，原因是因为它内部通过空间换时间的方法，用一个大数组存储所有的value,并根据key直接计算出value应该存储在那个索引。

如果key的值为"a"，计算得到的索引总是1，因此返回value为Person("Xiao Ming")，如果key的值为"b"，计算得到的索引总是5，因此返回value为Person("Xiao Hong")，这样，就不必遍历整个数组，即可直接读取key对应的value。
在判断传入的key是否是Map中的key时，一般以两个key的内容相等作为正确的判断，而不一定是同一个对象，这就要我们提前写好equals()方法来判断内容是否相同。
在Map的内部，对key做比较是通过equals()实现的，这一点和List查找元素需要正确覆写equals()是一样的，即正确使用Map必须保证：作为key的对象必须正确覆写equals()方法。
我们经常使用String作为key，因为String已经正确覆写了equals()方法。但如果我们放入的key是一个自己写的类，就必须保证正确覆写了equals()方法。
HashMap为什么能通过key直接计算出value存储的索引。相同的key对象（使用equals()判断时返回true）必须要计算出相同的索引，否则，相同的key每次取出的value就不一定对。

`hashcode`

通过key计算索引的方式就是调用key对象的hashCode()方法，它返回一个int整数。HashMap正是通过这个方法直接定位key对应的value的索引，继而直接返回value。
因此，正确使用Map必须保证：

作为key的对象必须正确覆写equals()方法，相等的两个key实例调用equals()必须返回true；
作为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()，即上述3个字段分别相同的实例，hashCode()返回的int必须相同：

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

注意到String类已经正确实现了hashCode()方法，我们在计算Person的hashCode()时，反复使用31*h，这样做的目的是为了尽量把不同的Person实例的hashCode()均匀分布到整个int范围。
既然HashMap内部使用了数组，通过计算key的hashCode()直接定位value所在的索引，那么第一个问题来了：hashCode()返回的int范围高达±21亿，先不考虑负数，HashMap内部使用的数组得有多大？
实际上HashMap初始化时默认的数组大小只有16，任何key，无论它的hashCode()有多大，都可以简单地通过：

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

把索引确定在0～15，即永远不会超出数组范围，上述算法只是一种最简单的实现。
第二个问题：如果添加超过16个key-value到HashMap，数组不够用了怎么办？
添加超过一定数量的key-value时，HashMap会在内部自动扩容，每次扩容一倍，即长度为16的数组扩展为长度32，相应地，需要重新确定hashCode()计算的索引位置。例如，对长度为32的数组计算hashCode()对应的索引，计算方式要改为：

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

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

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

虽然指定容量是10000，但HashMap内部的数组长度总是2n，因此，实际数组长度被初始化为比10000大的16384（214）。
最后一个问题：如果不同的两个key，例如"a"和"b"，它们的hashCode()恰好是相同的（这种情况是完全可能的，因为不相等的两个实例，只要求hashCode()尽量不相等），那么，当我们放入：

map.put("a", new Person("Xiao Ming"));
map.put("b", new Person("Xiao Hong"));

时，由于计算出的数组索引相同，后面放入的"Xiao Hong"会不会把"Xiao Ming"覆盖了？
当然不会！使用Map的时候，只要key不相同，它们映射的value就互不干扰。但是，在HashMap内部，确实可能存在不同的key，映射到相同的hashCode()，即相同的数组索引上，肿么办？
我们就假设"a"和"b"这两个key最终计算出的索引都是5，那么，在HashMap的数组中，实际存储的不是一个Person实例，而是一个List，它包含两个Entry，一个是"a"的映射，一个是"b"的映射：

┌───┐
0 │   │
  ├───┤
1 │   │
  ├───┤
2 │   │
  ├───┤
3 │   │
  ├───┤
4 │   │
  ├───┤
5 │ ●─┼───> List<Entry<String, Person>>
  ├───┤
6 │   │
  ├───┤
7 │   │
  └───┘

在查找的时候，例如：

Person p = map.get("a");

HashMap内部通过"a"找到的实际上是List>，它还需要遍历这个List，并找到一个Entry，它的key字段是"a"，才能返回对应的Person实例。
我们把不同的key具有相同的hashCode()的情况称之为哈希冲突。在冲突的时候，一种最简单的解决办法是用List存储hashCode()相同的key-value。显然，如果冲突的概率越大，这个List就越长，Map的get()方法效率就越低，这就是为什么要尽量满足条件二：
如果两个对象不相等，则两个对象的hashCode()尽量不要相等。
hashCode()方法编写得越好，HashMap工作的效率就越高。

使用`EnumMap`

HashMap是一种通过key计算hashcode，通过空间换时间的方式，定位到value所在的内部数组的索引。
如果key是作为enum类型，则可以使用Java集合库中提供的一种EnumMap，它在内部以一个非常紧凑的数组存储value，并根据enum类型的key直接定位到内部数组的索引，不需要计算hashCode()，并且没有额外的空间浪费。
我们以DayOfWeek这个枚举类型为例，为它做一个“翻译”功能：

public class Main {
    public static void main(String[] args) {
        Map<DayOfWeek, String> map = new EnumMap<>(DayOfWeek.class);
        map.put(DayOfWeek.MONDAY, "星期一");
        map.put(DayOfWeek.TUESDAY, "星期二");
        map.put(DayOfWeek.WEDNESDAY, "星期三");
        map.put(DayOfWeek.THURSDAY, "星期四");
        map.put(DayOfWeek.FRIDAY, "星期五");
        map.put(DayOfWeek.SATURDAY, "星期六");
        map.put(DayOfWeek.SUNDAY, "星期日");
        System.out.println(map);
        System.out.println(map.get(DayOfWeek.MONDAY));
    }
}

`TreeMap`

还有一种map在内部会对Key进行排序，那就是SortedMap。而SortedMap是接口，它的实现类为TreeMap

SortedMap保证遍历时以Key的顺序来进行排序。例如，放入的Key是"apple"、"pear"、"orange"，遍历的顺序一定是"apple"、"orange"、"pear"，因为String默认按字母排序。
TreeMap在实现排序的前提是放入的Key必须实现Comparable接口，String、Integer这些Java类已经实现了Comparable接口，因此可以直接作为Key使用。
若Key的class没有实现Comparable接口，则必须在创建TreeMap时同时制定一个Comparator :

Map<Person, Integer> map = new TreeMap<>(new Comparator<Person>() {
            public int compare(Person p1, Person p2) {
                return p1.name.compareTo(p2.name);
            }
        });

Properties

在编写应用程序时，经常要读写配置文件。配置文件的特点是，它的Key-Value一般都是String类型的，对此我们可以使用Map<String,String>来表示。因为配置文件十分常用，Java提供了一个Properties来表示一组配置。Properties内部本质上是一个Hashtable，但我们只需要用到Properties自身关于读写配置的接口。

读取配置文件

用Properties读取配置文件非常简单。Java默认配置文件以.properties为扩展名，每行以key=value表示，以#课开头的是注释。以下是一个典型的配置文件：

# setting.properties
last_open_file=/data/hello.txt
auto_save_interval=60

可以从文件系统读取这个.properties文件：

String f = "setting.properties";
Properties props = new Properties();
props.load(new java.io.FileInputStream(f));
String filepath = props.getProperty("last_open_file");
String interval = props.getProperty("auto_save_interval", "120");

如果有多个.properties文件，可以反复调用load()读取，后读取的key-value会覆盖已读取的key-value:

Properties props = new Properties();
props.load(getClass().getResourceAsStream("/common/setting.properties"));
props.load(new FileInputStream("C:\\conf\\setting.properties"));

写入配置文件

如果通过setProperty()修改了Properties实例，可以把配置写入文件，以便下次启动时获得最新配置。写入配置文件使用store()方法：

Properties props = new Properties();
props.setProperty("url", "http://www.liaoxuefeng.com");
props.setProperty("language", "Java");
props.store(new FileOutputStream("C:\\conf\\setting.properties"), "这是写入的properties注释");

编码问题

早期版本的Java规定.properties文件编码是ASCII编码（ISO8859-1），如果涉及到中文就必须用name=\u4e2d\u6587来表示，非常别扭。从JDK9开始，Java的.properties文件可以使用UTF-8编码了。
不过，需要注意的是，由于load(InputStream)默认总是以ASCII编码读取字节流，所以会导致读到乱码。我们需要用另一个重载方法load(Reader)读取：

Properties props = new Properties();
props.load(new FileReader("settings.properties", StandardCharsets.UTF_8));

就可以正常读取中文。InputStream和Reader的区别是一个是字节流，一个是字符流。字符流在内存中已经以char类型表示了，不涉及编码问题。

Map