摘要
HashMap是一个神奇的东西，它能够快速地存储和检索数据。它的底层实现非常复杂，但它的魔力却是无穷的。用它来处理数据，就像用魔法来解决问题一样，让人感到无比神奇和惊奇。
正文
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索引）
如果在扩容的时候这个链表已经树化了，树里面也存放了计算上一个元素的地址值，虽然它是一棵树，但是它里面也有链表所用到的地址值
为什么链表长度到8了进化红黑树，不是7或者9呢，这就涉及到概率论：泊松分布
这个链表到8的概率其实是非常低的 ，Java是优先扩容的，而不是优先拉链，哈希碰撞的概率其实是很低的。
全图
关注不迷路
扫码下方二维码，关注宇凡盒子公众号，免费获取最新技术内幕！
评论0