1.HashMap数据结构
    jdk7:数组+链表(头插法)
    jdk8:数组(操作时间复杂度为o(1))+链表(解决hash碰撞冲突)+(红黑树)

    单向链表只能向前查找，不能往向查找。
    双向链表可以往回查找。
    image.png
    image.png

    2.重要成员变量

    • DEFAULT_INITIAL_CAPACITY = 1 << 4; Hash表默认初始容量
    • MAXIMUM_CAPACITY = 1 << 30; 最大Hash表容量
    • DEFAULT_LOAD_FACTOR = 0.75f；默认加载因子
    • TREEIFY_THRESHOLD = 8；链表转红黑树阈值
    • UNTREEIFY_THRESHOLD = 6；红黑树转链表阈值
    • MIN_TREEIFY_CAPACITY = 64；链表转红黑树时hash表最小容量阈值，达不到优先扩容。

    3.内部的执行机制源码
    HashMap是线程不安全的，不安全的具体原因就是在高并发场景下，扩容可能产生死锁(Jdk1.7存在)以及get操作可能带来的数据丢失。

    Jdk7-扩容死锁分析
    死锁问题核心在于下面代码，多线程扩容导致形成的链表环!主要原因是没做同步锁导致多个线程同时都在做transfer从而形成死锁。
    image.png
    去掉了一些冗余的代码， 层次结构更加清晰了。

    • 第一行：记录oldhash表中e.next
    • 第二行：rehash计算出数组的位置(hash表中桶的位置)
    • 第三行：e要插入链表的头部， 所以要先将e.next指向new hash表中的第一个元素
    • 第四行：将e放入到new hash表的头部
    • 第五行： 转移e到下一个节点， 继续循环下去

    单线程扩容
    假设：hash算法就是简单的key与length(数组长度)求余。hash表长度为2，如果不扩容， 那么元素key为3,5,7按照计算(key%table.length)的话都应该碰撞到table[1]上。
    扩容：hash表长度会扩容为4重新hash，key=3 会落到table[3]上(3%4=3)， 当前e.next为key(7), 继续while循环重新hash，key=7 会落到table[3]上(7%4=3), 产生碰撞， 这里采用的是头插入法，所以key=7的Entry会排在key=3前面(这里可以具体看while语句中代码)当前e.next为key(5), 继续while循环重新hash，key=5 会落到table[1]上(5%4=3)， 当前e.next为null, 跳出while循环，resize结束。
    如下图所示
    image.png
    多线程扩容
    下面就是多线程同时put的情况了， 然后同时进入transfer方法中：假设这里有两个线程同时执行了put()操作，并进入了transfer()环节
    image.png
    那么此时状态为：
    image.png
    从上面的图我们可以看到，因为线程1的 e 指向了 key(3)，而 next 指向了 key(7)，在线程2 rehash 后，就指向了线程2 rehash 后的链表。
    然后线程1被唤醒了：

    1. 执行e.next = newTable[i]，于是 key(3)的 next 指向了线程1的新 Hash 表，因为新 Hash 表为空，所以e.next = null，
    2. 执行newTable[i] = e，所以线程1的新 Hash 表第一个元素指向了线程2新 Hash 表的 key(3)。好了，e 处理完毕。
    3. 执行e = next，将 e 指向 next，所以新的 e 是 key(7)

    然后该执行 key(3)的 next 节点 key(7)了:

    1. 现在的 e 节点是 key(7)，首先执行Entry next = e.next,那么 next 就是 key(3)了
    2. 执行e.next = newTable[i]，于是key(7) 的 next 就成了 key(3)
    3. 执行newTable[i] = e，那么线程1的新 Hash 表第一个元素变成了 key(7)
    4. 执行e = next，将 e 指向 next，所以新的 e 是 key(3)

    此时状态为：
    image.png
    然后又该执行 key(7)的 next 节点 key(3)了：

    1. 现在的 e 节点是 key(3)，首先执行Entry next = e.next,那么 next 就是 null
    2. 执行e.next = newTable[i]，于是key(3) 的 next 就成了 key(7)
    3. 执行newTable[i] = e，那么线程1的新 Hash 表第一个元素变成了 key(3)
    4. 执行e = next，将 e 指向 next，所以新的 e 是 key(7)

    这时候的状态如图所示：
    image.png
    很明显，环形链表出现了。
    Jdk8-扩容
    Java8 HashMap扩容跳过了Jdk7扩容的坑，对源码进行了优化，采用高低位拆分转移方式，避免了链表环的产生。
    扩容前：
    image.png
    扩容后：
    image.png
    由于Jdk8引入了新的数据结构，所以put方法过程也有了一定改进，其过程如下图所示。
    image.png
    总结：
    java jdk8中对HashMap的源码进行了优化，在jdk7中，HashMap处理“碰撞”的时候，都是采用链表来存储，当碰撞的结点很多时，查询时间是O（n）。
    在jdk8中，HashMap处理“碰撞”增加了红黑树这种数据结构，当碰撞结点较少时，采用链表存储，当较大时（>8个），采用红黑树（特点是查询时间是O（logn））存储（有一个阀值控制，大于阀值(8个)，将链表存储转换成红黑树存储）。
    image.png
    虽说jdk8中对HashMap做了优化，不会产生死锁问题了，但在面对高并发的情况下依然是会有问题的，毕竟HashMap是线程不安全的，所以高并发场景下推荐使用concurrentHashMap。

    TreeMap
    HashMap是无序的，想让Map有序的话可以用TreeMap