1.HashMap的个线数据机构详解
    HashMap数据机构 = 数组 + 线性链表 + 红黑数（当数组长度>=8的时候链表会转红黑树）
    数组查询时间复杂度 = O（1）
    链表查询时间复杂度 = O （N）-> 红黑树诞生 -> 问题：当插入多的时候，很容易打破树的平衡性 -> 维持再平衡（左旋、右旋）以及重新作色
    数组长度必须是2的指数次幂，默认情况下，hashmap进行初始化操作的时候,会把数组长度和加载因子传递进来，如果传进来的数组长度不是2的指数次幂，会自动改成大于这个容量最接近的2的指数次幂的数，它为什么要去这么做呢？保证hashmap在获取下标的时候，数组下标在容量大小的范围内，位运算的特特点，还有就是如果不是2的次幂，那么位运算的结果会导致和取模结果不等价。哇，对，就是这两个原因。
    加载因子为什么是0.75？因为hashmap为了使数据能够更加的散列，避免产生大量的hash碰撞,以空间换时间的方式,使得数据能够分散到容器当中去。

    hashmap8中为什么当链表长度>=8的时候，会将链表转换成红黑数？概率统计学的算法，【泊松分布】算法，这个算法，可以使得一个链表形成之后，重复的定位在同一个桶里的概率，会成指数级的越来越小。
    hashmap8比7性能高的并不多，8%-10%

    hashmap产生循环链的原因是什么？

    扩容前 = 容器大小 = 4

    image.png

    线程1 执行 => Entry next = e.next; 线程阻塞 ，等待唤醒

    线程2 第一次遍历，此时的 e 和 next 同时指向了B节点
    image.png

    线程2 执行第2次循环
    image.png

    此时，造成了链表中的数据，发生了体位互换了

    线程1 此时被唤醒，继续开始执行，由于迁移的时候，链表中的数据发生了体位互换，当指针指来指去的时候,就形成了链表环

    hashmap8 提供了4组指针,2组高位，2组地位指针，同时把高位和低位的指针断掉，转移到同数组下标的新容器当中去，这样做的好处就是，不会形成循环链表了，同时扩容的时候不需要重新hash取下标,大大提高了性能。这里面还有一个点就是高位在进行迁移的时候是数组下标+老数组大小，所以说，这也是为什么，数组长度必须是2的指数次幂。但hashmap8还不是线程安全的,hashmap没有考虑在初始化阶段保证线程安全的。

    2.为何初始化容量要是2的指数幂？加载因子为什么是0.75
    3.Java7的hashmap扩容死锁演示与环链分析
    4.Jdk8的hashmap扩容优化，如何做到扩容无需rehash?
    5.CurrentHashMap线程安全吗？为什么是分段锁？

    红黑树：接近于平衡的二叉树（O（logn））
    image.png

    2.ConcurrentHashMap讲解 

    1. class Node(){
    2.     private String key;
    3.     private String value;
    4.     private Node next;        //单项链表方式
    5. }
    1. class TreeNode(){
    2.     private Node left;        //左子树
    3.     private Node right;        //右子树
    4.     private boolean red;    //是否红
    5. }
    1. 1.先有数组:一定是在线程中执行的    main进行进行初始化的操作,单线程,多线程呢？
    2. Node[] table = new Node(16);
    3. resize()    -> 对数组进行初始化static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;//16
    4.     ->    newCap = DEFAULT_INITIAL_CAPACITY;    //设置大小
    5.     ->    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);    //设置阀值
    6.     ->    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];    //初始化操作
    7.         table = newTab;    //其中的1<<4的意思就是1向右位移四位，在1的后面补上4个0,也就是2^4次方
    9. 2.key,value--Node();
    10.     Node对象put数组中
    1. Node[] table = new Node(16);    //单线程情况下,无论怎么折腾,都不会有问题的
    3. T1：执行Task 16
    4. T2：执行Task 32
    6. 在多线程的情况下操作，有可能和单线程的结果不一致。
    8. 所以：HashTable 在put/get的时候使用了synchroized(lock)保证线程安全，但是效率很低。
    10. 如何使用无锁化机制CAS,保证线程安全    -> Compare And Swap:比较并替换    -> 保证对某个线程操作安全
    11. Cas是一种乐观锁的机制
    12. int a = 内存当中有自己的值
    13.     T1    -> a 修改成b
    14.     T2    -> a 修改成c
    16. ConcurrentHashMap使用了Cas无锁化机制保证了线程安全的机制

    ConcurrentHashMap

    1. //保证线程可见性
    2. transient volatile Node<K,V>[] table;
    4. if (tab == null || (n = tab.length) == 0)
    5.                 tab = initTable();
    7. private final Node<K,V>[] initTable() {
    8.     Node<K,V>[] tab; int sc;
    9.     while ((tab = table) == null || tab.length == 0) {
    10.         //线程1如果完成了初始化操作，线程2会进行一个让步，不会再进行初始化了
    11.         if ((sc = sizeCtl) < 0)
    12.             //让出现线程的执行权
    13.             Thread.yield(); // lost initialization race; just spin
    14.         //(U.compareAndSwapInt 无锁化线程保障
    15.         //操作数
    16.         //    SIZECTL:内存当中的值
    17.         //    sc：预期值
    18.         //    -1：新值
    19.         //    初始化值操作只有一次会操作成功
    20.         else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
    21.             try {
    22.                 //此时：SIZECTL = -1
    23.                 if ((tab = table) == null || tab.length == 0) {
    24.                     int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
    25.                     @SuppressWarnings("unchecked")
    26.                     //进行初始化
    27.                     Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
    28.                     table = tab = nt;
    29.                     sc = n - (n >>> 2);
    30.                 }
    31.             } finally {
    32.                 sizeCtl = sc;
    33.             }
    34.             break;
    35.         }
    36.     }
    37.     return tab;
    38. }
    1. hash 函数
    3. 1.得到一个整形值    hash函数（key.hashCode()-> 高低16位运算）是一个随机值,保证了取模算法后取得的数组下标是
    4. 一定在这个容器大小的范围之内的。如何保证数组下标不一样，让数组均匀的分布在容器中，就是这个
    5. hash函数的取值结构。
    1. final V putVal(K key, V value, boolean onlyIfAbsent) {
    2.     if (key == null || value == null) throw new NullPointerException();
    3.     int hash = spread(key.hashCode());
    4.     int binCount = 0;
    5.     for (Node<K,V>[] tab = table;;) {
    6.         Node<K,V> f; int n, i, fh;
    7.         if (tab == null || (n = tab.length) == 0)
    8.             tab = initTable();
    9.         //线程安全
    10.         else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
    11.             if (casTabAt(tab, i, null,
    12.                          new Node<K,V>(hash, key, value, null)))
    13.                 break;                   // no lock when adding to empty bin
    14.         }
    15.         //判断当前头节点的hash值如果MOVED=-1的话,让当前线程暂停,去帮忙搬数组
    16.         else if ((fh = f.hash) == MOVED)
    17.             tab = helpTransfer(tab, f);
    18.         else {
    19.             V oldVal = null;
    20.             //同步数组索引的头节点,和分段锁是不一样的
    21.             synchronized (f) {
    22.                 if (tabAt(tab, i) == f) {
    23.                     if (fh >= 0) {
    24.                         binCount = 1;
    25.                         for (Node<K,V> e = f;; ++binCount) {
    26.                             K ek
    27.                             //替换key值
    28.                             if (e.hash == hash &&
    29.                                 ((ek = e.key) == key ||
    30.                                  (ek != null && key.equals(ek)))) {
    31.                                 oldVal = e.val;
    32.                                 if (!onlyIfAbsent)
    33.                                     e.val = value;
    34.                                 break;
    35.                             }
    36.                             Node<K,V> pred = e;
    37.                             //按链表方式,放入一个最新的节点
    38.                             if ((e = e.next) == null) {
    39.                                 pred.next = new Node<K,V>(hash, key,
    40.                                                           value, null);
    41.                                 break;
    42.                             }
    43.                         }
    44.                     }
    45.                     //红黑树放节点
    46.                     else if (f instanceof TreeBin) {
    47.                         Node<K,V> p;
    48.                         binCount = 2;
    49.                         if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
    50.                                                               value)) != null) {
    51.                             oldVal = p.val;
    52.                             if (!onlyIfAbsent)
    53.                                 p.val = value;
    54.                         }
    55.                     }
    56.                 }
    57.             }
    58.             if (binCount != 0) {
    59.                 if (binCount >= TREEIFY_THRESHOLD)
    60.                     treeifyBin(tab, i);
    61.                 if (oldVal != null)
    62.                     return oldVal;
    63.                 break;
    64.             }
    65.         }
    66.     }
    67.     addCount(1L, binCount);
    68.     return null;
    69. }
    70. //保证线程可见性、防止指令重排序
    71. //使用cas保证原子性，比如初始化操作的时候
    72. //数组索引的头节点上锁