HashMap

JDK1.6、JDK1.7：HashMap采用位桶+链表实现，即使用链表处理冲突，同一hash值的链表都存储在一个链表里。
                但是当位于一个桶中的元素较多，即hash值相等的元素较多时，通过key值依次查找的效率较低。
JDK1.8：HashMap采用位桶+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间。
HashMap是基于哈希算法实现的，我们通过put(key,value)存储，get(key)来获取数据。
存储：put(key,value)
===========================================================================================================================================
0、当添加一个元素（key-value），HashMap 根据 key.hashCode() 计算出key的hash值。
1、根据 hash值确定插入数组中的位置，将该元素(key-value)存放在该位置，但有可能数组中的该位置已被同hash值得元素占用了(hash冲突：hash值相同，key值不同)。
2、这时就将该元素添加在同一hash值的元素的后面，他们在数组的同一位置，但是形成了链表，同一各链表上的Hash值是相同的，所以说数组存放的是链表。
3、当链表长度太长时，链表就转换为红黑树，这样大大提高了查找的效率。
===========================================================================================================================================
1、HashMap 的每一个元素，都是链表的一个节点（entry）。
2、新增一个元素时，会先计算 key 的 hash 值，找到存入数组的位置。
3、如果该位置已经有节点（链表头），则存入该节点的最后一个位置（链表尾）。
4、所以 HashMap 就是一个数组（bucket），数组上每一个元素都是一个节点（节点和所有下一个节点组成一个链表）或者为空，显然同一个链表上的节点 hash 值都一样。
===========================================================================================================================================
1、先获取key对象的hashcode。
2、根据hashcode计算出hash值
3、根据对应的hash值来将Entry对象放到table数组中，如果对应的索引没有Entry对象,就直接存进数组中，如果对应索引位置已经有Entry对象，则将已有Entry对象的next指向本Entry对象，形成链表。
===========================================================================================================================================
1、table未初始化或者长度为0，进行扩容
2.1、数组长度和元素哈希值做&操作，确定元素存放在哪个桶中，桶为空，新生成结点放入桶中
2.2、数组新增元素，判断是否达到临界值，达到则扩容、2倍
3、桶中已经存在元素：p(指向链表头节点)
3.1、key相等：比较桶中第一个元素p与要插入元素的key是否相等，key相等则此次put为覆盖操作
3.2、key不相等；头节点p为红黑树结点，则此次put为向红黑树中插入节点
3.3、key不相等；头节点p为链表结点，则此次put为向链表中插入节点（树化发生在此处）
	 第一种：已经遍历到尾部(没有相同的key)，在最后插入新节点跳出，因节点数量+1，判断是否需要树化，需要则树化
	 第二种：e指向的节点与要插入节点的key相同，此次put为覆盖操作
2.2 处扩容机制：  
1、如果旧表的长度不是空
1.1、若已经到了最大容量，这时还要往map中放数据，则阈值设置为整数的最大值 
1.2把新表的长度设置为旧表长度的两倍，newCap=2*oldCap
2、如果旧表的长度的是0
2.1、旧阈值>0 则将阈值赋值给新表长度，因为在构造方法中是将capacity赋值给了threshold。 
2.2、旧阈值=0 则阈值使用默认值 
3、新阈值=0时，为新阈值赋值
4、下面开始构造新表，初始化表中的数据
4.1、遍历原来的旧表，移到新表中	
4.2、判断表(数组)中元素是否为空
4.2.1、判断当前表元素是否存下一个节点(链表)，不存在则直接将该元素放在新表中
4.2.2、判断当前表元素是否存在树
4.2.1.1 如果当前元素(e后边有链表)存在链表带着个单链表，需要遍历单链表，将每个节点重新放在新表中( 新计算在新表的位置，并进行搬运)
5、循环判断下一个节点是否为空，同时为该链表进行分队 	
===========================================================================================================================================
HashMap：数组(bucket)+链表(或红黑树)组成
HashMap 的每一个元素，都是链表的一个节点(Entry：(hash、key、value，next))
当链表数组的容量超过初始容量的0.75时，再散列将链表数组扩大2倍，把原链表数组的搬移到新的数组中。

1、HashMap的底层数据结构？
   数组+单向链表+红黑树
2、HashMap的主要参数都有哪些？
   默认初始容量：16；负载因子(填充比)：0.75
3、HashMap是怎么处理hash碰撞的？
   hashCode值相同，替换旧值、插入链表、插红黑树
4、hash的计算规则？
   index的计算公式：index = HashCode(Key) & (Length- 1)
5、HashMap的存取原理？
       1.计算关于key的hashcode值（与Key.hashCode的高16位做异或运算）
       2.如果散列表为空时，调用resize()初始化散列表
       3.如果没有发生碰撞，直接添加元素到散列表中去
       4.如果发生了碰撞(hashCode值相同)，进行三种判断
           4.1:若key地址相同或者equals后内容相同，则替换旧值
           4.2:如果是红黑树结构，就调用树的插入方法
           4.3:链表结构，循环遍历直到链表中某个节点为空，尾插法进行插入，插入之后判断链表个数是否到达变成红黑树的阙值8；
               也可以遍历到有节点与插入元素的哈希值和内容相同，进行覆盖。
       5.如果桶满了大于阀值，则resize进行扩容
6、HashMap的扩容方式？负载因子是多少？为什是这么多？
      扩容方式：数组实际长度 > 数组容量长度 * 负载因子
      负载因子：0.75
7、默认初始化大小是多少？为啥是这么多？为啥大小都是2的幂？
       默认初始化容量：16
       为啥是16：因为在使用不是2的幂的数字的时候，Length-1的值是所有二进制位全为1111，这种情况下，index的结果等同于HashCode后几位的值。
       为啥是2的幂：为了数据的均匀分布，减少哈希碰撞；因为确定数组位置是用的位运算，若数据不是2的次幂则会增加哈希碰撞的次数和浪费数组空间。
                   当数组长度不为2的n次幂 的时候，hashCode 值与数组长度减一做与运算的时候，会出现重复的数据，
                   因为不为2的n次幂 的话，对应的二进制数肯定有一位为0 , 这样不管你的hashCode 值对应的该位，是0还是1，
                   最终得到的该位上的数肯定是0，这带来的问题就是HashMap上的数组元素分布不均匀，而数组上的某些位置，永远也用不到
       初始容量16，n只要是2的幂，n - 1的二进制一定全是1，假设有i位，那么它和任何hash做&操作肯定都是保留hash的后i位（&操作两个都是1才是1），
       这样就非常滴均匀，不容易冲突。            
                   https://blog.csdn.net/eaphyy/article/details/84386313
                   https://www.cnblogs.com/seakyfly/p/13391638.html
8、Java7和Java8的区别？
9、HashMap为啥会线程不安全？
   get、put方法没有加锁，有可能造成元素的覆盖
   以put方法为例：判断table的在(n-1)&hash的值是否为空，为空就新建一个节点插入在该位置：if ((p = tab[i = (n - 1) & hash]) == null)
   假如现在有两个线程都执行到了上图中的划线处。当线程一判断为空之后，CPU 时间片到了，被挂起。
   线程二也执行到此处判断为空，继续执行下一句，创建了一个新节点，插入到此下标位置。
   然后，线程一解挂，同样认为此下标的元素为空，因此也创建了一个新节点放在此下标处，因此造成了元素的覆盖。   
10、有什么线程安全的类代替么?
   1、HashTable：get、put方法加synchronize锁，简单读取时也加锁，而且锁住的是整张表，导致效率低下
   2、CurrentHashMap：
11、HashMap的为啥用尾插法? 
   1、1.7 用头插法：新来的值会取代原有值得位置，原有的值就顺推到链表中去，在扩容时，
          头插法会改变链表中元素原本的顺序，以至于在并发场景下导致链表成环的问题，
          单线程下正常，多线程下，会有可能形成链表成环(死循环)，导致CPU爆满，程序崩溃
   2、1.8 用尾插法：主要是为了安全,防止环化(维护了链表元素的原有顺序，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题)