HashMap的底层原理

package com.programme.demo01;

import java.util.HashSet;
import java.util.List;

/**
 * @program: spring
 * @description: ${description}
 * @author: Mr.zw
 * @create: 2021-05-15 10:26
 **/
public class Demo01 {
    public static void main(String[] args) {
        HashSet<Integer> set = new HashSet<>();
        set.add(3);
        set.add(2);
        set.add(4);
        set.add(5);
        set.add(16);
        set.add(17);
        set.add(7);
        set.add(1);
        set.add(6);
        set.add(9);
        set.add(8);
        set.add(10);
        System.out.println(set);
       //输出： [16, 17, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    }
}

　　添加元素

package com.programme.demo01;

import java.util.HashSet;
import java.util.List;

/**
 * @program: spring
 * @description: ${description}
 * @author: Mr.zw
 * @create: 2021-05-15 10:26
 **/
public class Demo01 {
    public static void main(String[] args) {
        HashSet<Integer> set = new HashSet<>();
        set.add(3);
        set.add(2);
        set.add(4);
        set.add(5);
        set.add(16);
        set.add(17);
        set.add(7);
        set.add(1);
        set.add(6);
        set.add(9);
        set.add(8);
        set.add(10);
        set.add(11);
        set.add(12);
        set.add(13);
        System.out.println(set);
        //输出：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 16, 17]
    }
}

　　这里我们的16，17到了后面去了，这涉及到哈希表的底层，set集合的底层其实也是hashmap

哈希桶也是有索引的，哈希桶的初始容量是十六

1<<4;是1左移四位，也就是1乘以2的4次方，>>表示右移除以。

假设这里有一个元素要进来想往hashmap里面存，先是用hashcode.equals判断是否有值然后通过put存放进去

通过计算哈希值来放入tab中也就等于我们的数组中

通过这个方法计算哈希值扰乱函数低十六位异或高十六位这个操作叫做扰乱函数

将计算的哈希值右移16位，让哈希值尽量分散开，查询map的时候尽量快一点，所以也哈希表也叫散列表

异或相同为0不同为1

计算出来的哈希值这么大怎么将元素存入一个索引为0-15的哈希表去

长度必须是二的几次方

如果我们自定义的容量不是二的几次方也会强转为2的次方

这么做的目的就是为了计算存放索引

默认长度16的的2进制是10000 看源码的操作

这里将10000-1得到1111 再进行与操作得到0101也就是5索引这种操作叫做路由寻址

我们将元素存到5索引

假设这个又来个一个元素通过计算也存到了5索引就发生了哈希碰撞（哈希冲突）第一个存进去的元素后面有个拉链将他们拉起来 1.7是头插法1.8是尾插法

如果我们的数组存满了就会扩容，比如16扩容成了32，不能让后面16位空着，要尽量让它散列，1.7会出现环形链表也就是著名的约瑟夫环问题。

在 Java 1.8 中，如果链表长度到8，数组容量到64，链表会树化；删除元素红黑树长度小于6，红黑树退化为链表;（这里的数组容量指的是数组长度，不是64个元素）

何时扩容数组中长度*加载因子（0.75)个位置上都有元素，再存会扩容

16乘以0.75等于12

package com.programme.demo01;

import com.sun.org.apache.xpath.internal.operations.Equals;

import java.util.HashSet;
import java.util.List;

/**
 * @program: spring
 * @description: ${description}
 * @author: Mr.zw
 * @create: 2021-05-15 10:26
 **/
public class Demo01 {
    public static void main(String[] args) {
        HashSet<Integer> set = new HashSet<>();

        set.add(3);//1
        set.add(2);//2
        set.add(4);//3
        set.add(5);//4
        set.add(16);//5
        set.add(17);//6
        set.add(7);//7
        set.add(1);//8
        set.add(6);//9
        set.add(9);//10
        set.add(8);//11
        set.add(10);//12
        set.add(11);//13
        //输出：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 16, 17]
        System.out.println(set);
    }
}

package com.programme.demo01;

import com.sun.org.apache.xpath.internal.operations.Equals;

import java.util.HashSet;


/**
 * @program: spring
 * @description: ${description}
 * @author: Mr.zw
 * @create: 2021-05-15 10:26
 **/
public class Demo01 {
    public static void main(String[] args) {
        HashSet<Integer> set = new HashSet<>();

        set.add(3);//1
        set.add(2);//2
        set.add(4);//3
        set.add(5);//4
        set.add(16);//5
        set.add(17);//6
        set.add(7);//7
        set.add(1);//8
        set.add(6);//9
        set.add(9);//10
        set.add(8);//11
        set.add(10);//12
        //输出：[16, 17, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
        System.out.println(set);
    }
}

package com.programme.demo01;

import com.sun.org.apache.xpath.internal.operations.Equals;

import java.util.HashSet;


/**
 * @program: spring
 * @description: ${description}
 * @author: Mr.zw
 * @create: 2021-05-15 10:26
 **/
public class Demo01 {
    public static void main(String[] args) {
        HashSet<Integer> set = new HashSet<>();

        set.add(3);//1
        set.add(2);//2
        set.add(4);//3
        set.add(5);//4
        set.add(16);//5
        set.add(17);//6
        set.add(0);//7
        set.add(1);//8
        set.add(6);//9
        set.add(9);//10
        set.add(8);//11
        set.add(10);//12 16乘以0.75=13 未扩容
        //输出：[16, 17, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
        //16计算索引是0 17计算索引是1   16和0在一个链上 17和1在一个链上
        System.out.println(set);
    }
}

　　扩容一下

package com.programme.demo01;

import com.sun.org.apache.xpath.internal.operations.Equals;

import java.util.HashSet;


/**
 * @program: spring
 * @description: ${description}
 * @author: Mr.zw
 * @create: 2021-05-15 10:26
 **/
public class Demo01 {
    public static void main(String[] args) {
        HashSet<Integer> set = new HashSet<>();

        set.add(3);//1
        set.add(2);//2
        set.add(4);//3
        set.add(5);//4
        set.add(16);//5
        set.add(17);//6
        set.add(0);//7
        set.add(1);//8
        set.add(6);//9
        set.add(9);//10
        set.add(8);//11
        set.add(10);//12
        set.add(11);//13 已扩容
        //输出：[0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 16, 17] 16 17被分到扩容的位置上去了
        System.out.println(set);
    }
}

　　在扩容的时候会将链表分成低位链和高位链，扩容时低位链不变，高位链分配是原索引加原长度（下图原索引为1原长度为16，扩容后分配到17索引）