JDK8中对HashMap做了优化，依然是用数组存储数据，但是扩容时采用双链表的方式避免了高并发情况下导致出现循环链表的问题，另外也引入了红黑树，提高碰撞元素的搜索速度。

一段代码

     下面这段代码创建一个容量为64的HashMap和插入一些数据。

HashMap<Integer,Integer> hashMap=new HashMap<>(64);
        hashMap.put(5,5);
        hashMap.put(2,2);
        hashMap.put(69,69);
        hashMap.put(66,66);
        hashMap.put(325,325);
        hashMap.put(197,197);
        hashMap.put(261,261);
        hashMap.put(133,133);
        hashMap.put(389,389);
        hashMap.put(453,453);
        hashMap.put(133,999);

如何定位数据下标

      一开始说到HashMap是用数组来存储数据，那么数组下标和key是怎么关联上的呢。其实它是将key的hash值和数组长度进行一系列的位运算（异或和与）得出数据下标。例如key=69时，运算如下

最后得出下标是5，那就把（69,69）包装成Node<Integer,Integer>放在数组5的位置上。

链表

     从上面公式可以看到，大小相差64的key计算出来的位置都是一样的，例如5和69计算出来的下标都是5，产生冲突了。数组一个下标只能存储一个元素，那么怎么办。HashMap这个时候会用链表来存储冲突的元素，第一个存储在数组的就是链表头Node，接下来冲突元素放在链表头Node的Next位置上，上面那段代码执行流程如下：

       从上面的动图可以看到,每个元素都是链表顺序往下找,如果找到相同key的元素,就替换value,否者就放在链表的尾元素的next上。那么问题来了，如果链表很长，每次都要一直遍历到尾部，这太耗时了，时间复杂度为O(n)。如果将链表改成红黑树，那么时间复杂度将会是O(logn)。事实上，HashMap就是这么干的。

红黑树

      在HashMap中，当链表长度大于8时，链表将会转成红黑树。而红黑树的根会存储在数组中。如果这个时候再put一个元素（517,517），将会触发树转换，最终转换的结果如下

      在说转换之前，可以先来了解一下红黑树的概念。其实红黑树是近似二叉平衡树的，二叉平衡树又是二叉树的一种，他们之间的关系如下

      我个人觉得从二叉搜索树开始,在计算机科学中才有一定价值。每一种树都有性质，性质是继承的，越里面的树性质越多。

• 二叉搜索树：它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值。
• 平衡二叉搜索树：在二叉树的基础上，加上性质：它的左右两个子树的高度差的绝对值不超过1。平衡二叉搜索树搜索复杂度总是O（logn），有效规避了有序元素插入的情况导致退化成链表的问题。
• 红黑树:在二叉搜索树的基础上,加入四个性质,使树总是保持近似平衡,搜索时间复杂度也是O（logn）。

             1. 节点是红色或黑色。

             2. 根节点是黑色。

      按照红黑树的性质，每次新插入的都是在树的最下面，为红叶子，因为红叶子可能都不用调整，黑叶子100%要调整。从上面的流程图可以看到，调整都是从新增的红叶子开始的，通过变色或者左旋右旋的操作不断向上调整，直到调整到根节点。