HashMap
JDK1.7中，底层使用数组+链表
JDK1.8中，底层使用数组+链表+红黑树
共同点：
容量（capacity）：HashMap中数组的长度
- 容量范围：必须是2的幂 & <最大容量（2的30次方）
- 初始容量 = 哈希表创建时的容量
- 默认容量 = 16 = 1<<4 = 00001中的1向左移4位 = 10000 = 十进制的2^4=16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; - 最大容量 = 2的30次方（若传入的容量过大，将被最大值替换）
static final int MAXIMUM_CAPACITY = 1 << 30;
加载因子(Load factor)：HashMap在其容量自动增加前可达到多满的一种尺度
- 加载因子越大、填满的元素越多 = 空间利用率高、但冲突的机会加大、查找效率变低（因为链表变长了）
- 加载因子越小、填满的元素越少 = 空间利用率小、冲突的机会减小、查找效率高（链表不长）
- 默认加载因子 = 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
扩容机制
扩容时resize(2 * table.length)，扩容到原数组长度的2倍。
若key == null，则hash(key) = 0，则将该键-值 存放到数组table 中的第1个位置，即table [0]
异同点
JDK1.7中
使用一个Entry数组来存储数据,用key的hashcode取模来决定key会被放到数组里的位置,如果hashcode相同,或者hashcode取模后的结果相同(hash collision),那么这些key会被定位到Entry数组的同一个格子里,这些key会形成一个链表。
在hashcode特别差的情况下,比方说所有key的hashcode都相同,这个链表可能会很长,那么put/get操作都可能需要遍历这个链表
,也就是说时间复杂度在最差情况下会退化到O(n)。
发生hash冲突时，新元素插入到链表头中，即新元素总是添加到数组中，就元素移动到链表中。
在扩容resize（）过程中，采用单链表的头插法，在将旧数组上的数据 转移到 新数组上时，转移操作 = 按旧链表的正序遍历链表、在新链表的头部依次插入，即在转移数据、扩容后，容易出现链表逆序的情况 。
HashMap线程不安全的一个重要原因就是：多线程下resize()容易出现死循环，此时若（多线程）并发执行 put（）操作，一旦出现扩容情况，则 容易出
现 环形链表，从而在get数据、遍历链表时 形成死循环（Infinite Loop），即 死锁的状态 。
JDK1.8中
使用一个Node数组来存储数据,但这个Node可能是链表结构,也可能是红黑树结构
如果插入的key的hashcode相同,那么这些key也会被定位到Node数组的同一个格子里。
如果同一个格子里的key不超过8个,使用链表结构存储。
如果超过了8个,那么会调用treeifyBin函数,将链表转换为红黑树。
那么即使hashcode完全相同,由于红黑树的特点,查找某个特定元素,也只需要O(log n)的开销
也就是说put/get的操作的时间复杂度最差只有O(log n)
由于 JDK 1.8 转移数据操作 = 按旧链表的正序遍历链表、在新链表的尾部依次插入（尾插法），所以不会出现链表 逆序、倒置的情况，故不容易出现环形链表的情况 ，但jdk1.8仍是线程不安全的，因为没有加同步锁保护。
发生hash冲突后，会优先判断该节点的数据结构式是红黑树还是链表，如果是红黑树，则在红黑树中插入数据，如果是链表，则将数据插入到链表的尾部并判断链表长度是否大于8，如果大于8要转成红黑树，另一还要判断数组长度是否超过阀值
