对于Java的集合认知一直以来都不够清晰，现在特地对Map做一次总结，以加深印象。
Map接口位于java.util包下，该包下一共提供了如下具体的实现类(基于JDK1.8)，java.util包中开放的实现类如下图所示：
涉及的接口和抽象类有如下几个：
| 名称 | 说明 |
|---|---|
| Map | 提供存放键值对的对象，要求key不能重复，包含get、put等方法 |
| SortedMap | 提供有序的Map |
| NavigableMap | 在 SortedMap 基础上，支持快速搜索符合条件的最近的元素 |
| ConcurrentMap | 提供线程安全和原子性的Map |
| ConcurrentNavigableMap | 继承自NavigableMap和ConcurrentMap，提供线程安全的同时，支持快速搜索 |
| AbstractMap | 提供Map接口的框架实现 |
AbstractMap
如果想要开发自定义的Map，建议扩展AbstractMap，其中提供了一些默认实现。除了 Hashtable 和 Properties，其它实现类都继承自AbstractMap。
实现类供有10个，整理如下：
| 名称 | 数据结构 | 初始化容量 | 扩容方式 | 适用场景 |
|---|---|---|---|---|
| HashMap | 数组 + 链表 + 红黑树 | 16 | 个数超过负载因子(默认0.75)指定值时，扩容2倍 | 不保证读取顺序与写入数据一致 |
| LinkedHashMap | 双向链表 +（数组 + 链表 + 红黑树） | 同HashMap | 同HashMap | 继承自HashMap，保证读取顺序与写入数据一致 |
| IdentityHashMap | 数组 | 16 | 超出容量时，扩容2倍 | 不使用equals比较key，直接使用==比较key，因此不存在哈希冲突的问题，key和value相邻存储，存储16个元素时数组长度为32 |
| TreeMap | 红黑树 | 0 | 无 | 自动以key做自然排序，要求key必须实现Comparable接口 |
| WeakHashMap | 数组 + 单向链表 | 16 | 个数超过负载因子(默认0.75)指定值时，扩容2倍 | 当某个”弱键”不再正常使用时，会从WeakHashMap中被自动移除 |
| ConcurrentHashMap | 同HashMap | 同HashMap | 同HashMap | 并发场景下的Map |
| ConcurrentSkipListMap | 跳表 | 0 | 无 | 并发场景下的有序Map |
| EnumMap | 数组 | 与Enum个数相同 | 无 | 当key是枚举类型时，可以使用EnumMap，操作效率更高 |
| Hashtable | 数组 + 链表 | 11 | 个数超过负载因子(默认0.75)指定值时，扩容2倍+1 | 线程安全的Map，目前已废弃 |
| Properties | 同Hashtable | 同Hashtable | 同Hashtable | 继承自Hashtable，用于加载属性配置文件 |
尝试按照日常的使用频率，做如下分类：
| 名称 | 使用频率 |
|---|---|
| HashMap、ConcurrentHashMap | 高 |
| LinkedHashMap、TreeMap | 中 |
| IdentityHashMap、WeakHashMap、ConcurrentSkipListMap、EnumMap | 低 |
| Hashtable、Properties | 极低 |
HashMap无疑是最热门的类，本文将继续详细介绍这个类。
1. hash相关的概念
为了更好的理解HashMap和ConcurrentHashMap，这里先介绍下hash相关的概念。
哈希(hash)
Hash，一般翻译做散列、杂凑，或音译为哈希，是把任意长度的输入通过散列算法变换成固定长度的输出，转换过程称为散列函数或哈希函数，转换结果就是散列值，也叫hash code或index。
哈希表(hash table)
哈希表（hash table，也叫散列表），是根据键（key）直接访问访问在内存储存位置的数据结构。 哈希表本质是一个数组，数组中的每一个元素成为一个箱子，箱子中存放的是键值对。
哈希桶(hash bucket)，其中存储了hash code对应的所有数据；每个桶中包含了多个槽(slot)，即每个hash code可以对应多条数据。
优点：哈希表可以提供快速的操作。
缺点：哈希表通常是基于数组的，数组创建后难于扩展。 也没有一种简便的方法可以以任何一种顺序〔例如从小到大）遍历表中的数据项。
哈希冲突(hash collision)
由于哈希算法被计算的数据是无限的，而计算后的结果范围有限，因此总会存在不同的数据经过计算后得到的值相同，这就是哈希冲突。
在Java语言中，体现为两个对象进行equals比较时不相等，但它们的hashCode相等。
哈希拉链法
由于存在哈希冲突，导致同一个hash code可能对应多条数据；为了解决该问题，将这些hash code相同的数据以链表的形式存储起来，以便正常查找。
这种处理方式的数据结构，形似一个拉链，因此称为拉链法。
2. HashMap
HashMap基于哈希表(hash table)的Map接口的实现，它并允许空值和空键。（HashMap 类与Hashtable大致等效，不同之处在于它是不同步的，并且允许为null。）该类不保证映射的顺序，它不能保证顺序会随着时间的推移保持恒定。jdk1.8中的数据结构如下：
数据table即哈希桶数组，数组中每个元素都是一个哈希桶，每个哈希桶中以链表或红黑树的方式存储多个数据。下面从介绍HashMap的哈希函数和扩容机制。
新增数据
HashMap外层结构是一个组数，数组的长度是固定的，需要考虑扩容问题。默认情况下，初始容量为16。
调用put方法添加元素时的流程如下：
其中有几个需要重点关注的步骤：哈希函数、扩容机制。
哈希函数
HashMap通过哈希函数计算key的哈希值，达到快速定位数组下标的目的。对于哈希函数，总是希望计算后的结果可以均匀分布在数组中，从而提高存取性能。
一个优质的哈希函数对于HashMap的性能提升，是至关重要的。
HashMap中哈希函数的伪代码如下：
int h = key.hashCode();//1. 获得key的哈希值
// int hash ^= (h >>> 20) ^ (h >>> 12);
// hash = h ^ (h >>> 7) ^ (h >>> 4); // 2. jdk1.7中的hash计算方式，对h进行多次右移、异或运算。
int hash = h ^ (h >>> 16);//2. jdk1.8中的hash计算方式，对h做右移、异或运算
int index = (table.length - 1) & hash;//3. 取模运算，获得数组下标
注意：int类型是一个32位的二进制数。
第一步计算hashCode，不再赘述。
第二步，jdk1.7的计算方式，保证了对象的hashCode的32位值只要有一位发生改变，整个hash返回值就会改变，高位的变化会反应到低位里。
第二步，jdk1.8的计算方式，保证了对象的hashCode的高16位的变化能反应到低16位中，相比较而言减少了过多的位运算，是一种折中的设计。
第三步，HashMap的容量长度固定为2的n次方，当length总是2的n次方时，该计算方式与hash%length相同，即对hash取模，但是&比%效率更高。
HashMap的容量长度固定为2的n次方，是为了用位运算替换%运算，提高效率。
另外，当数组长度为2的n次幂时，不同的key算得得index相同的几率较小，那么数据在数组上分布就比较均匀。
扩容机制
HashMap的扩容需要满足两个条件：当前数据存储的数量（即size()）大小必须大于等于阈值；当前加入的数据是否发生了hash冲突。
1）创建一个新的Entry空数组，长度是原来的2倍。
2）遍历原Entry数组，把所有的Entry重新Hash到新数组里。为什么要重新Hash呢？因为长度扩大以后，Hash的规则也随之改变了。
3. 小结
本文整理了java.util包下的Map相关类，充分理解他们的适用场景，以便在使用时合理挑选。后面又介绍了HashMap的哈希函数和扩容机制，对HashMap的深入理解，就是对相关数据结构及算法的深入理解。
参考的文章
Java 8系列之重新认识HashMap
Java集合之LinkedHashMap
java中key值可以重复的map：IdentityHashMap
Hash（散列函数）百度百科
夯实Java基础系列19
搞iOS的，面试官问Hash干嘛？原因远比我下面要介绍的多
Java中hashCode()方法以及HashMap()中hash()方法
