Map
Map 提供 key 到 value 的映射，保存 key -> value 形式的对象，Map 中 key 不允许重复，每个 key 最多只能对应一个 value。Map 接口提供3种集合的视图，Map 的内容可以被当作一组 key 集合，一组 value 集合，或者一组 key - value 映射。
Map 接口 的常见子类：HashMap, Hashtable, TreeMap
HashMap
HashMap 是基于哈希表的 Map 接口的实现，以 key - value 的形式存在。key 和 value 允许为 null， 不保证有序(比如插入的顺序)，也不保证顺序不随时间变化。在 HashMap 中，key - value 总是会当做一个整体来处理，系统会根据 hash 算法来计算 key - value 的存储位置，我们总是可以通过 key 快速地存取 value。
在之前的版本中，HashMap 采用数组+链表实现，即使用链表处理冲突，同一 hash 值的链表都存储在一个链表里。但是当链表中的元素较多，即 hash 值相等的元素较多时，通过 key 值依次查找的效率较低。而 JDK1.8 中，HashMap 采用数组+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大提到了查询效率。
HashMap 遍历方式
entrySet, keySet
public static void demo() {
Map<String, String> map = new HashMap<>();
for (int i = 0; i < 1000000; i++) {
map.put("smile" + i, "smile" + i);
}
long start = System.currentTimeMillis();
for (Map.Entry<String, String> entry : map.entrySet()) {
String key = entry.getKey();
String value = entry.getValue();
}
long entrySet = System.currentTimeMillis();
System.out.println("entrySet" + "-" + (entrySet - start) + "毫秒");
for (String entry : map.keySet()) {
String key = entry;
String value = map.get(key);
}
System.out.println("keySet" + "-" + (System.currentTimeMillis() - entrySet) + "毫秒");
}
- 同时遍历 key 和 value 时，keySet 与 entrySet 方法的性能差异取决于 key 的具体情况，如复杂度（复杂对象）、离散度、冲突率等。换言之，取决于 HashMap 查找 value 的开销。entrySet 一次性取出所有 key 和 value 的操作是有性能开销的，当这个损失小于 HashMap 查找 value 的开销时，entrySet 的性能优势就会体现出来。例如当 key 是最简单的数值或字符串时，keySet 可能会更高效，耗时比 entrySet 少很多，但总体来说还是推荐使用 entrySet 。因为当 key 很简单时，其性能或许会略低于keySet，但却是可控的，而随着 key 的复杂化，entrySet 的优势将会明显体现出来。当然，我们可以根据实际情况进行选择；
- 只遍历 key 时，keySet 方法更为合适，因为 entrySet 将无用的 value 也给取出来了，浪费了性能和空间；
- 只遍历 value 时，使用 values 方法是最佳选择，entrySet 会略好于 keySet 方法。
HashMap 空间
在HashMap中有两个很重要的参数，容量 (Capacity) 和负载因子 (Load factor)
- Initial capacity The capacity is the number of buckets in the hash table, The initial capacity is simply the capacity at the time the hash table is created.
- Load factor The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased.
简单的说，Capacity 就是 bucket 的大小，Load factor 就是bucket 填满程度的最大比例。如果对迭代性能要求很高的话不要把 capacity 设置过大，也不要把 load factor 设置过小。当 bucket 中的 entries 的数目大于 capacity * load factor 时就需要调整bucket 的大小为当前的2倍。所以如果我们已经预知 HashMap 中元素的个数，那么预设元素的个数能够有效的提高 HashMap 的性能。
HashMap 同步性
HashMap 是非同步的（unsynchronized），因此 HashMap 中的对象并不是线程安全的。
Hashtable
和 HashMap 一样，Hashtable 也是一个散列表，它存储的内容是键值对。
public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable
从中可以看出 HashTable 继承 Dictionary 类，实现 Map 接口。其中 Dictionary 类是任何可将键映射到相应值的类（如 Hashtable）的抽象父类。每个键和每个值都是一个对象。在任何一个 Dictionary 对象中，每个键至多与一个值相关联。
Map 是”key-value 键值对”接口。
Hashtable 遍历方式
public static void demo() {
Hashtable<String, String> map = new Hashtable<>();
for (int i = 0; i < 1000000; i++) {
map.put("smile" + i, "smile" + i);
}
long start = System.currentTimeMillis();
for (Map.Entry<String, String> entry : map.entrySet()) {
String key = entry.getKey();
String value = entry.getValue();
}
long entrySet = System.currentTimeMillis();
System.out.println("entrySet" + "-" + (entrySet - start) + "毫秒");
for (String entry : map.values()) {
String key = entry;
String value = map.get(key);
}
long keySet = System.currentTimeMillis();
System.out.println("keySet" + "-" + (keySet - entrySet) + "毫秒");
Enumeration<String> en = map.keys();
while (en.hasMoreElements()){
String key = en.nextElement();
String value = map.get(key);
}
System.out.println("Enumeration" + "-" + (System.currentTimeMillis() - entrySet) + "毫秒");
Enumeration<String> enValue = map.elements();
while (en.hasMoreElements()){
String value = enValue.nextElement();
}
}
比较
HashTable 和 HashMap 存在很多的相同点，但是他们还是有几个比较重要的不同点。
HashTable 基于 Dictionary 类，而 HashMap 是基于 AbstractMap。Dictionary 是任何可将键映射到相应值的类的抽象父类，而 AbstractMap 是基于 Map 接口的实现，它以最大限度地减少实现此接口所需的工作。
HashMap 可以允许存在一个为 null 的 key 和任意个为 null 的 value，但是 HashTable 中的 key 和 value 都不允许为 null。
Hashtable 的方法是同步的，而 HashMap 的方法不是。所以有人一般都建议如果是涉及到多线程同步时采用 HashTable，没有涉及就采用 HashMap，但是在 Collections 类中存在一个静态方法： synchronizedMap()，该方法创建了一个线程安全的 Map 对象，并把它作为一个封装的对象来返回。
TreeMap
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
TreeMap 继承 AbstractMap，实现 NavigableMap、Cloneable、Serializable 三个接口。其中 AbstractMap 表明 TreeMap 为一个 Map 即支持 key-value 的集合，NavigableMap（更多）则意味着它支持一系列的导航方法，具备针对给定搜索目标返回最接近匹配项的导航方法 。而接口 NavigableMap 继承自 SortedMap。SortedMap 是 Map 的子接口，使用它可以确保图中的条目是排好序的。
TreeMap 基于红黑树数据结构的实现，键值可以使用 Comparable 或 Comparator 接口来排序。
TreeMap 遍历方式
public static void demo() {
Map<String, String> map = new TreeMap<>();
for (int i = 0; i < 1000000; i++) {
map.put("smile" + i, "smile" + i);
}
long start = System.currentTimeMillis();
for (Map.Entry<String, String> entry : map.entrySet()) {
String key = entry.getKey();
String value = entry.getValue();
}
long entrySet = System.currentTimeMillis();
System.out.println("entrySet" + "-" + (entrySet - start) + "毫秒");
for (String entry : map.values()) {
String key = entry;
String value = map.get(key);
}
long keySet = System.currentTimeMillis();
System.out.println("keySet" + "-" + (keySet - entrySet) + "毫秒");
}
07-31 08:43:39.233 644-644/com.smile.kotlindemo I/System.out: entrySet-47毫秒
07-31 08:43:40.080 644-644/com.smile.kotlindemo I/System.out: keySet-847毫秒
- 同时遍历 key 和 value 时，与 HashMap 不同，entrySet 的性能远远高于 keySet。这是由 TreeMap 的查询效率决定的，也就是说，TreeMap 查找 value 的开销较大，明显高于 entrySet 一次性取出所有 key 和 value 的开销。因此，遍历 TreeMap 时强烈推荐使用 entrySet 方法。
- 只遍历 key 时，keySet 方法更为合适，因为 entrySet 将无用的 value 也给取出来了，浪费了性能和空间。
- 只遍历 value 时，使用 values 方法是最佳选择，entrySet 也明显优于 keySet 方法。
Set
Set 接口扩展自 Collection，它与 List 的不同之处在于，规定 Set 的实例不包含重复的元素。在一个规则集内，一定不存在两个相等的元素。AbstractSet 是一个实现 Set 接口的抽象类，Set 接口有三个具体实现类，分别是散列集 HashSet、链式散列集LinkedHashSet 和树形集 TreeSet。
HashSet
HashSet 实现了 Set 接口，它不允许集合中有重复的值，当我们提到 HashSet 时，第一件事情就是在将对象存储在 HashSet 之前，要先确保对象重写 equals() 和 hashCode() 方法，这样才能比较对象的值是否相等，以确保 set 中没有储存相等的对象。如果我们没有重写这两个方法，将会使用这个方法的默认实现。
Set 在输出时元素是无序的。
LinkedHashSet
LinkedHashSet 是用一个链表实现来扩展 HashSet 类，它支持对规则集内的元素排序。HashSet 中的元素是没有被排序的，而LinkedHashSet 中的元素可以按照它们插入规则集的顺序提取。
TreeSet
与 HashSet 是基于 HashMap 实现一样，TreeSet 同样是基于 TreeMap 实现的，它的作用是提供有序的 Set 集合。
TreeSet 扩展自 AbstractSet，并实现了 NavigableSet ，AbstractSet 扩展自 AbstractCollection，树形集是一个有序的 Set ，其底层是一颗树，这样就能从 Set 里面提取一个有序序列了。在实例化 TreeSet 时，我们可以给 TreeSet 指定一个比较器 Comparator 来指定树形集中的元素顺序。
