HashMap

HashMap

1. 当变成红黑树之前会将单向链表变成双向链表，所以jdk1.8（1.8之前没有红黑树）后红黑树不仅具有红黑树的特点，还有双向链表的特点，在查找，增加和删除元素时用的是红黑树的特点，在遍历的时候用的是双向链表的特点

2. 链表的长度大于8的时候才会转为红黑树

3. 红黑树的特点，节点不可能出现双红，红节点的父节点一定是黑节点

4. 为什么要对key的高16位做异或运算呢？

   //put操作
    public V put(K key, V value) {
           return putVal(hash(key), key, value, false, true);
       }
   //对key进行hash处理
   static final int hash(Object key) {
           int h;
        //为什么hashMap中key可以为null,因为这里处理了，当key为null时，其hash值为0
           return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
       }
   //部分putVal方法
   final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                      boolean evict) {
           Node<K,V>[] tab; Node<K,V> p; int n, i;
           if ((tab = table) == null || (n = tab.length) == 0)
               n = (tab = resize()).length;
            //数组容量-1与上经过高16位运算的hash值
           if ((p = tab[i = (n - 1) & hash]) == null)
               tab[i] = newNode(hash, key, value, null);
           else {
               Node<K,V> e; K k;
               if (p.hash == hash &&
                   ((k = p.key) == key || (key != null && key.equals(k))))
                   e = p;
               else if (p instanceof TreeNode)
                   ......
   
      
   

因为最终求得数组索引的位置是通过这个(n - 1) & hash方式计算得到的，n表示的是数组容量，并且n是2的幂次方，所以n-1得到的2进制数就是后面的都为1，前面的都为0，比如 n = 8 时，那么（n-1）对应的二进制数最后三位为111，前面的都是0，同理 n = 16 时，（n-1）对应的最后四位为1111，前面的都为0，因为&运算是一假即假，所以影响&运算结果的就是后面那几位，也就是对应的2的多少次方，比如8为2的3次方，那么影响&运算结果的就是后面3位，16为2的4次方，所以影响&运算结果的就是后面四位，以此类推，2的n次方，影响其&运算结果的就是后面的n位，而我们的日常开发中n最大基本上也到不了2^16（2的16次方），所以（n-1）& key的hashCode值（32位）进行运算时，key的hashCode最多就只有后16位参与了运算，高16位就没有参与运算，那么这样子就增加了数组中索引碰撞的概率，导致整个数组利用率不高，所以为了让key的hashCode值的高16位也参加进来，使其hash值更加散列，减少碰撞几率，就先对key的hashCode值进行了高16位的异或运算

常见问题

1.jdk1.8中HashMap的底层数据结构是数组+链表（单向，在转为红黑树之前会先变成双向的）+红黑树结构
2.默认容量是16，拓容阈值 = 负载因子（0.75）* 数组容量，可以自定义初始容量，如果不是2的幂次方，那么内部会有tableSizeFor找到离我们自定义容量最近的2的幂次方数值作为数组长度，比如你设置的初始容量为31，那么tableSizeFor会自动将数组容量转为32（2的5次方）

put逻辑：

1. 通过key的hash值（key的hashCode值异或运算上key的hashCode值的高16位所得到的hash值）&（数组长度 - 1）计算出索引位置，判断是否为空，如果为空，直接在这个数组位置上放入Node对象,如果不为空，遍历链表，先判断下一个元素是否为null,然后使用if（p.hash == hash && ((k = p.key) == key || (key ！= null && key.equals(k))))公式判断是否为同一个元素，如果一直不同，直到下一个元素为null时，那么就往链表中尾插法插入元素

2. 当链表长度大于8，同时数组长度小于64时，只会进行拓容操作

3. 当链表长度大于8，同时数组长度大于64时，会进行树化操作,单向链表转红黑树之前，会先转为双向链表，再进行树化，目的就是当我们查询，增加和删除元素时使用红黑树的特性，而遍历的时候使用双向链表的特性

4. 当添加的元素个数大于拓容阈值的时候会进行拓容的操作，这里需要注意的是当我的数组容量为16的时候，那么我的拓容阈值为12，只要往里面添加的元素大于12个，不管它在什么位置，即使都在数组的第一个位置上（链表上），剩下15个数组的位置没有用，那么再插入一个元素的时候还是会拓容，总结来说只要插入的元素大于12时就会进行拓容

5. 判断是否是同一个值的公式：if（p.hash == hash && ((k = p.key) == key || (key ！= null && key.equals(k))))

6. 如何判断放进来的是否是同一个值，先判断key的hash值是否相等，hash值相等后还要判断key是否相等或者equals是否相等，如果条件满足才是同一个值进行覆盖，这里就衍生出一个问题，如果是自定义的key,重写了equas方法，但是没有重写hashcode方法，如果不重写hashcode方法，那么默认的hashcode就是地址值，那么我们定义的两个内容相等就为同一个对象的做法在hashMap中时就可能会有问题，两个内容相等但hashcode值不一样的对象作为key,存入hashMap时,由于hashCode值不一样，就可能得到不一样的数组索引，所以定义的相同的key就不会百分百覆盖了，另外就是比如两个key计算得到的hash值分别为1和17，那么经过对16取余的运算，得到的都是索引1，就会去到同一个位置，同一个位置时会先判断其hash值是否一样，明显是不一样的，所以即使去到了同一个数组索引，也不会覆盖，还有一种情况，就是两个key的内存地址对应的hashcode值恰好一模一样，那么这时候所得的hash值是一样的，重写了equals，内容也是一样的，这时候就可以覆盖，所以最终就出现了一种情况，我们的size容量，可能一会儿多一个一会儿少一个，不稳定。

拓容逻辑

1. 新数组长度是原数组长度*2

2. 循环旧数组，如果数组位置上为null,那么就直接跳过，如果数组位置上只有一个元素，那么就会根据这个元素的hash值计算放在新数组的哪个位置

3. 如果是链表，那么就会将链表分割成高位链表和低位链表，将低位链表插入到计算得到的新数组的j位置，往j+n位置插入高位链表

4. 如果是红黑树，会分割成高位双向链表和低位双向链表，如果分裂出来的链表个数 <= 6,那么就会转成单向链表，如果大于6则会将分裂出来的链表变成新的红黑树

5. x%n(x对n取余) = x&(n-1)的前提是n必须是2的n次方，将模运算变成与运算的目的是提高计算的性能，因为程序更利于处理2进制的运算

6. 两种情况下会拓容，一是当插入的元素个数大于拓容阈值的时候，二是当链表上的个数大于8，且数组长度小于64的时候

hash算法

1. int类型数据的hash值，底层返回的就是它本身（hash目的尽量是分散点，不要重复，现在我有1,2,3,4,5共5个数，那怎么计算hash值保证既简单又不重复呢？那就是返回它本身）

2. 拓容时如果对应的位置是链表，数据是怎么转到新数组中去的呢？比如旧数组容量为16，那么当hash值为1或者17,33的key所在的索引都是一样的都在1号位置，这时候如果拓容了，新数组容量为32，那么hash值为17的key就不在1号索引位置了，而是去到了索引为17的位置（17 % 32 ），而hash值为1的key在新数组的1号位置，1号位就是低位链表过来的，17号位就是高位链表过来的，那低位链表和高位链表是怎么得到的呢？

   do {
       next = e.next;
      /* 主要就是通过这里来计算高位和低位链表的，当(e.hash &oldCap) == 0就是低位链表里面的节点，不等0时就是高位链表里面的节点，所以高位链表元素在新数组中位置为低位链表所在的位置+oldCap（旧数组容量）*/
       if ((e.hash & oldCap) == 0) {
           if (loTail == null)
               loHead = e;
           else
               loTail.next = e;
           loTail = e;
       }
       else {