参考：廖雪峰Java教程；Java从入门到精通第5版；

Map接口

Map是一种键值对映射表的数据结构，能够高效的通过key快速查找value（元素），Map中不能包含相同的key，每个key只能映射一个value，key还决定了存储对象在映射中的位置，这个位置是针对key对象，使用一种散列技术进行处理，产生一个散列码的整数值，这个散列码通常用作一个偏移量，对应分配给映射的内存区域的起始位置，从而确定存储对象在映射中的存储位置；

Map接口的实现类

HashMap：基于哈希表的Map接口的实现，通过哈希码对其内部的映射关系进行快速查找，添加和删除映射关系效率高，但不保证映射的顺序，允许使用null值和null键，内部使用了数组，通过计算key的hashCode()直接定位value所在的索引，推荐使用；

EnumMap：如果key的对象是枚举类型，推荐使用，其内部是一个非常紧凑的数组存储value，根据key直接定位到内部数组的索引，不需要计算hashCode()，效率最高，没有额外的空间浪费；

TreeMap：实现了Map接口和java.util.SortedMap接口，映射关系存在一定的顺序，但不允许键对象是null，使用TreeMap时，放入的key必须实现Comparable接口，String，Integer这些类已经实现了Comparable接口，因此可以直接作为key使用，作为value的对象则没有要求；如果作为key的class没有实现Comparable接口，那么必须在创建TreeMap的同时制定一个自定义排序算法。

Map遍历

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

//通过put方法存入数据
map.put("chi",29);
map.put("wang", 30);
map.put("zhang", 27);

//通过get方法获得数据，为什么结果都是29，因为String默认实现的equals()方法，在Map内部，对key做比较是通过equals()方法实现的
Integer n1 = map.get("chi");
Integer n2 = map.get(new String("chi"));
System.out.println(n1);//29
System.out.println(n2);//29

//Map遍历,使用for each循环遍历

for(String key : map.keySet()) {
	Integer value = map.get(key);
	System.out.println(key+" = "+value);
}

for(Map.Entry<String, Integer> entry : map.entrySet()) {
	String key = entry.getKey();
	Integer value = entry.getValue();
	System.out.println(key+" = "+value);
}

//使用迭代器分别遍历key元素和value元素
Set<String> set = map.keySet();
Iterator<String> its = set.iterator();
while(its.hasNext()) {
	System.out.println(its.next());
}
Collection<Integer> coll = map.values();
Iterator<Integer> iti = coll.iterator();
while(iti.hasNext()) {
	System.out.println(iti.next());
}

编写equals()和hashCode()方法

要正确使用HashMap，作为key的类必须正确覆写equals()和hashCode()方法，覆写规则：

• equals()返回true,hashCode()返回值必须相等
• equals()返回false,hashCode()返回值尽量不要相等

class Person{
	String name;
	String id;
	int age;
	
	Person(String name, String id, int age){
		this.name = name;
		this.id = id;
		this.age = age;
	}
	
    //引用类型使用Objects.equals()方法比较，基本类型使用==比较
	public boolean equals(Object o) {
		if(o instanceof Person) {
			Person p = (Person) o;
			return Objects.equals(this.name, p.name) && Objects.equals(this.id, p.id) && this.age == p.age;
		}else {
			return false;
		}
	}
	
    //equals()用于比较的每一个字段，都必须在hashCode()中用于计算，equals()中没有使用的字段，决不能放入hashCode()进行计算
	public int hashCode() {
		return Objects.hash(name,id,age);
	}
}

import java.time.DayOfWeek;
import java.util.EnumMap;
import java.util.Map;

public class MapStudy {

	public static void main(String[] args) {
		// TODO 自动生成的方法存根
		Map<DayOfWeek, String> map = new EnumMap<>(DayOfWeek.class);
		map.put(DayOfWeek.MONDAY, "星期1");
		map.put(DayOfWeek.TUESDAY, "星期2");
		map.put(DayOfWeek.WEDNESDAY, "星期3");
		map.put(DayOfWeek.THURSDAY, "星期4");
		map.put(DayOfWeek.FRIDAY, "星期5");
		map.put(DayOfWeek.SATURDAY, "星期6");
		map.put(DayOfWeek.SUNDAY, "星期日");
		System.out.println(map);
		System.out.println(map.get(DayOfWeek.MONDAY));
	}
}

import java.util.Map;
import java.util.TreeMap;
import java.util.Comparator;

public class MapStudy {

	public static void main(String[] args) {
		// TODO 自动生成的方法存根
		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);
		}
		System.out.println(map.get(new Person("Tom")));
	}
}

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

/*执行结果：
{Person:Bob}
{Person:Lily}
{Person:Tom}
1
*/

注意到，Person类并未覆写equals()和hashCode()方法，因为TreeMap不使用equals()和hashCode()。

TreeMap在比较两个key是否相等时，依赖key的compareTo()方法，或者Comparator.compare()方法，两个key相等时，必须返回0；

HashMap的容量

HashCode()范围的int范围高达±21亿，那么HashMap内部的数组有多大？

实际上HashMap初始化时默认的数组大小只有16，任何key，无论它的hashCode()有多大，都可以简单的通过：

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

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

如果添加超过16个key-value到HashMap，HashMap内部会自动扩容，每次扩容一倍，即长度为16的数组扩展为长度32，相应地需要重新确定hashCode()计算索引位置，但是如果频繁的扩容，对HashMap的性能影响很大；

那么可以在创建HashMap的时候就制定容量：

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

虽然指定容量是10000，但是HashMap内部的数组长度总是2ⁿ，实际数组的长度被初始化为16384，即2^14；

如果两个key计算的索引一样，那么在HashMap的数组中，实际存储的不是一个对象实例，而是一个List，它包含两个entry，分别是两个不同的映射，这种情况称为哈希冲突，最简单的解决办法就是用List存储hashCode()相同的key-value；