开篇语：回头看，我这两个月基本没有啥更新，工作一年多，从来没加过班，这两个月开始加班了，平时加加班，周末就知道浪自然就给公号丢下了。但是我心里还是有你们的，还有就是，特别感谢最近刚刚关注的小伙伴们，我们一下努力哈，下面就一起看看 Java 7 & 8 中的 Map 吧！
先来看看 Map 这个顶级接口都有哪些具体的实现。
HashMap 最多允许一个 key 为 null，可以有多个 value 为 null，线程不安全，想要实现安全可以使用 Collections 的 synchronizedMap 方法或者使用 ConcurrentHashMap。
Hashtable 这个类看看名字就知道非常老了，因为命名都不是驼峰式的，不允许 key 和 value 为 null，但是这个类基本不用了。
LinkedHashMap ：LinkedHashMap 是 HashMap 的一个子类，保存了记录的插入顺序，在用 Iterator 遍历 LinkedHashMap 时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序 。
TreeMap ：TreeMap 实现 SortedMap 接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的 比较器 ，当用 Iterator 遍历 TreeMap 时，得到的记录是排过序的。如果使用排序的映射，建议使用 TreeMap 。在使用 TreeMap 时，key 必须实现 Comparable 接口或者在构造 TreeMap 时传入自定义的 Comparator ，否则会在运行时抛出 ClassCastException 类型的异常。
上面说的这几种 Map，最常用的就是 HashMap 了，等下就重点分析这一个，另外一点就是我们在选择 Key 时，要求 key 是不可变对象，因为这样才不会出现 hashcode 改变的情况。如果 hashcode 发生变化，可能就会找不到对应的值。而我们常用的 String 类就是不可变对象。可参考这篇文章。
首先从结构上来说，HashMap 是数组 + 链表 + 红黑树（JDK 1.8）实现的。
那为什么采用这样的结构呢？HashMap 本质实现了哈希表，而 哈希表 就是使用数组来存储。在发生哈希冲突之后，可以采用开放地址法和链地址法来解决冲突，在 HashMap 中使用链地址法来解决，也就是数组 + 链表的结构，在 JDK 1.8 中，当 链表 长度大于 8 的时候，就会将链表转化为 红黑树 。
简单说说 HashMap 中的 put 和 get 方法，在 put 方法中，根据 key 的哈希值得到一个索引，这就是 Node 存放的位置。当多个 key 求出的索引一样时就会产生链表甚至红黑树。在 get 方法中，根据 key 求出索引，然后去数组中取出对应的值即可，若是发生冲突，则再根据 key 的 equals 方法去一一比较链表上对应 Node 的 key，得到 equals 为 true 的那个 Node。
我们知道 HashMap 的默认长度是 16，而且后续即使扩容，长度也要满足 2 的 n 次方，这是为什么呢？首先来看看 索引 的生成
static final int hash(Object key) { //jdk1.8 & JDK 1.7
int h;
// h = key. Hash Code() 为第一步 取hashCode值
// h ^ (h >>> 16) 为第二步 高位参与运算
return (key == null) ? 0 : (h = key. hashCode ()) ^ (h >>> 16);
}
static int indexFor(int h, int length) { //jdk1.7的源码，jdk1.8没有这个方法，但是实现原理一样的
return h & (length-1); //第三步 与运算，length-1 得到的 二进制 全是1
}
这里的 Hash 算法本质上就是三步 ：取 key 的 hashCode 值、高位运算、与运算。
这个方法非常巧妙，它通过 h & (table.length – 1) 来得到该对象的保存位，而 HashMap 底层数组的长度总是 2 的 n 次方，这是 HashMap 在速度上的优化。当 length 总是 2 的 n 次方时，h & (length – 1) 运算等价于对 length 取模，也就是 h % length，但是 & 比 % 具有更高的效率。
在 JDK1.8 的实现中，优化了高位运算的算法，通过 hashCode() 的高 16 位异或低 16 位实现的 ：( h = k.hashCode()) ^ (h >>> 16 )，主要是从速度、功效、质量来考虑的，这么做可以在数组 table 的 length 比较小的时候，也能保证考虑到高低 Bit 都参与到 Hash 的计算中，同时不会有太大的开销。
下面举例说明得出数组下标的过程，n 为 table 的长度。
下面再来看看 JDK 1.7 和 1.8 中扩容有什么不同。
首先看看 JDK 1.7 中的扩容的核心部分，这个 transfer 方法就是将旧的 table 移动到新的 table 中。
void transfer(Entry[] newTable) {
Entry[] src = table; //src引用了旧的Entry数组
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
Entry<K,V> e = src[j]; //取得旧Entry数组的每个元素
if (e != null) {
src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）
do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity); //！！重新计算每个元素在数组中的位置
e.next = newTable[i];
newTable[i] = e; //将元素放在数组上
e = next; //访问下一个Entry链上的元素
} while (e != null);
}
}
}
这里注意两点就行，一就是每放入一个元素都要重新计算索引值，二是，发生冲突，那后来的元素在链表的首位，最开始来的元素在链表的最尾端。
再来看看 JDK 1.8 做了什么样的优化。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// 超过最大值就不再扩充了，就只好随你碰撞去吧
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 没超过最大值，就扩充为原来的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 计算新的resize上限
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes"，"unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 把每个bucket都移动到新的buckets中
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // 链表优化重hash的代码块
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 原索引
key: if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 原索引+oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 原索引放到bucket里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引+oldCap放到bucket里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
在扩容之后，长度扩为原来的 2 倍，所以元素的位置要么在原位置，要么在原位置加 oldCap，看下图可以明白这句话的意思，n 为 table 的长度，图（a）表示扩容前的 key1 和 key2 两种 key 确定索引位置的示例，图（b）表示扩容后 key1 和 key2 两种 key 确定索引位置的示例，其中 hash1 是 key1 对应的哈希与高位运算结果。
元素在重新计算 hash 之后，因为 n 变为 2 倍，那么 n-1 的 mask 范围在高位多 1bit (红色)，因此新的 index 就会发生这样的变化 ：
因此，我们在扩充 HashMap 的时候，不需要像 JDK1.7 的实现那样重新计算 hash ，只需要看看原来的 hash 值新增的那个 bit 是 1 还是 0 就好了，是 0 的话索引没变，是 1 的话索引变成 “ 原索引 + oldCap ”。
这里就可以看出，JDK 1.8 与 1.7 相比优化的地方，resize 的时候不需要 rehash ，而且由于最高位是 0 还是 1 也是随机的（根据 key.hashcode 求出来的），所以也保证了索引的随机性，另外就是 JDK 1.7 中链表会倒置，而 1.8 中不会倒置。
最后再说两点，为什么 HashMap 的数据结构为数组 + 链表，而不是数组 + 数组，数组其实也行，不用那肯定是为了性能考虑，数组差在哪里呢，差就差在在扩容的时候，链表可以很方便的扩容，而数组不行。
还有就是为什么 JDK 1.8 中在链表长度大于 8 的时候要使用红黑树，原因肯定是为了提高性能，那就看看红黑树有什么比较好的特性，红黑树虽然本质上是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)，提高检索速率。
