实现原理
HashMap用于存储键值对，内部为散列表，每个数组槽位是一个链表或红黑树，即类似桶排序的结构。
当调用HashMap的put方法新增键值对时，会根据HashMap类的静态方法hash，用键值对的键来计算出哈希值，并用(散列表大小n - 1) & hash的值作为散列表数组下标，将新增的键值对放入。
为解决哈希碰撞，每个散列表数组槽位内是一个链表或红黑树。当链表长度大于8，且散列表数组长度大于等64时，链表转化为红黑树；当红黑树节点小于6时退化成链表。
来说计算哈希值的hashCode方法。当键不为null时，将键的hashCode方法的值，和自身右移16位的值进行异或，结果作为计算后的哈希值返回。键为空则结果为0。
再来说说(n - 1) & hash这个式子。其实就等同于hash的值对散列表长度n求模：hash % n。这样能确保计算出的哈希值不会超出散列表下标范围。
这里使用与运算&而不是模运算，是因为位运算是直接对内存数据进行操作，不需要转成十进制，因此处理速度非常快。
且：
$$ x / 2^n = x >>> n $$
$$ x % 2^n = x & (2^n - 1) $$
当除数是2的n次方时，x除的结果就等于二进制直接右移n位，模的结果就等于x和除数减一的二进制进行与运算。
例：$ 21 / 8 $ 和 $ 21 % 8 $
21的二进制：10101， 8的二进制：01000， 7的二进制：00111
$ 21 / 8 = 21右移三位 = 00010 = 2 $ ， $ 21 % 8 = 21 & 7 = 00101 = 5 $
扩容机制
虽然解决了哈希碰撞的问题，但若散列表太小，键值对太多，频繁出现哈希碰撞，链表或红黑树就会变得很长，此时就需要对散列表扩容。
前面提到，键值对放在散列表中的哪个位置，是由(散列表大小n - 1) & hash决定的，与散列表大小有关。现在散列表大小改变了，意味着键值对存放的位置可能发生改变，要计算出扩容后所有键值对的新位置。
JDK1.7 中的做法是每个键值对重新hash映射到新的散列表，在 JDK1.8 进行了改进：
根据之前的结论，散列表长度必须是 $ 2^n $ ，每次扩容为之前的两倍。这样的好处是，扩容后计算(n - 1) & hash，有变化的只有扩容前的n那一位。
例：原本散列表长度为8，下标为2处有一键值对，现长度扩容为16
8-1的二进制为00111，16-1的二进制为01111
则对于(n - 1) & hash，原先的值就是下标2，即00010，说明hash为??010，扩容后的值应该为0?010。
若?为0，则扩容后位置也不变，无需迁移。若?为1，则扩容后的新位置就是原先的下标加上扩容前的散列表长度。
HashMap 和 Hashtable 的区别
- 父类不同：HashMap继承抽象类
AbstractMap；而Hashtable实现Dictionary类。二者都实现Map接口 - 线程安全不同：Hashtable是线程安全的，而HashMap不是
- 能否有null：Hashtable中key和value都不允许出现null；而HashMap允许有一个为null的key，value可以有多个null，因此不能用
get()返回null来判断HashMap中是否有某个键 - 哈希值的使用不同：Hashtable直接使用对象的
hashCode；而HashMap重新计算哈希值 - 扩容方式不同：HashMap内散列表默认大小为16，扩容后一定为2n；Hashtable初始大小为11，扩容方式为
old * 2 + 1