HashMap底层详解
1.简介
? HashMap是java种使用频繁的数据结构，其储存对象是无序的，以key，value的形式存放
? 1.key可以为null
? 2.key不能重复，如果key重复则会覆盖第一个key的value
? 3.一个key，对应一个value
2.HashMap的常用方法
| 方法 | 解释 |
|---|---|
| put（key，value） | 存入一对键值对key，value，如果key已存在则用这个value覆盖掉以前的，不存在则加入 |
| get（key） | 通过key来获取值 |
| values（） | 获得所有的value |
| keySet（） | 获得所有的key |
| isEmpty（） | 判断是否为空 |
| putAll（map） | 把另一个map全部加入这个map |
| containsKey(key) | 判断map种是否包含这个key |
| containsValue(value) | 判断map中是否包含这个value |
| size() | map的长度 |
3.底层数据结构
? hashMap底层的数据结构是以数组和链表的形式。
? 数组：查找快
? 链表：增删快
? 这也是设计成数组+链表的原因
? 底层的数组默认长度为16，随着map长度的加大可能会扩容，当链表变长的时候链表的数据结构也会变
以及为什莫数组默认长度为16？（下面会一 一陈述）
? 
HashMap储存对象时：***key所属的类***必须重写Object类里的HashCode（）和equals（）
HashCode（）：会为每个对象产生一个Hash值。 保证了高效性
equals（）：根据hash值判断两个对象是否一样，Hash值不一样两个***一定不相等***有
时可能会有两个对象Hash值相等但值不一样，这时候要调用equals（）比对两个对
象是否真的一致（保证key不重复）。 保证了准确性
4.Hash冲突
? 1.存入对象时，先算出其的Hash值然后和数组的长度求余也就是（Hash%16）算出来的值就是其存在的数组位数。
? 2.如果这一位已经有对象了那么就往下面链表里坠，next直到下一个为空，则把这个对象放到这。
5.Hash容量以及扩容机制
1.负载因子
? HashMap中有一个默认负载因子为0.75
? 为什莫为默认负载因子0.75？
? ① 阈值=负载因子容量*容量为2的幂次方所以必须保证
? 容量*负载因子为整数
? ② 负载因子越大Hash冲突越多，负载因子越少，空间浪费越大，权衡得出结果
2.扩容机制
? 当元素数量大于阈值则需要扩容，将数组长度按位向左移一位
? 由于：计算机底层按位移操作快(乘法的底层为加法效率不高)
? HashMap的容量是有上限的，必须小于1<<30，即1073741824。如果容量超出了这个数，则不再增长，且阈值会被设置为 Integer.MAX_VALUE（ [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-7P6Ksaik-1626959298692)(https://www.zhihu.com/equation?tex=2%5E%7B31%7D-1)] )，即永远不会超出阈值了)。
3.HashMap的数组开始长度为什莫为16
首先我们看hashMap的源码可知当新put一个数据时会进行计算位于table数组(也称为桶)中的下标：
int index =key.hashCode()&(length-1);
hashmap每次扩容都是以 2的整数次幂进行扩容
比如： 十进制: 201314
二进制: 11 0001 0010 0110 0010
假设初始化大小为16
15转化为二进制: 1111
index : 11 0001 0010 0110 0010 & 1111 =0010 为 3
? 因为是将二进制进行按位于，(16-1) 是 1111,末位是1，这样也能保证计算后的index既可以是奇数也可以是偶数，并且只要传进来的key足够分散，均匀那么按位于的时候获得的index就会减少重复，这样也就减少了hash的碰撞以及hashMap的查询效率。
? 这样看起来2的n次方都可以，但8和4太小，Hash碰撞太多，32太大故选16
6.HashMap中的扰动函数
什么为扰动函数?
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
对象在Hash表中存放的位置算法为=key.hashCode()&(length-1);
又由于Hash表初始长度为16，减去1为15
00000000 00000000 00000000 00001111与无论什么值取&结果都只能由后四位决定（0&1=0; 0&0=0; 1&0=0; 1&1=1;）
例如
? 00000000 00000000 00000000 00001111 16-1 （16hash表初始长度）
? 11000101 10011101 10000001 11110100 HashCode
? 00000000 00000000 00000000 00000100 结果
? 这样做的话hash冲突会很大所以采用一个办法，将hashCode右移16位与自己取^，产生的值作为新值去做运算
? 00000000 00000000 11000101 10011101 HashCode
? 11000101 10010101 10000001 11110100 h>>>16
? 11000101 10010101 01000100 01101001 新值 （更加散列）
用新值算对象在Hash表中存放的位置算法为=key.hashCode()&(length-1);
又由于Hash表初始长度为16，减去1为15
? 00000000 00000000 00000000 00001111
? 11000101 10010101 01000100 01101001
? 00000000 00000000 00000000 00001001
? 等于9
获得的值更加散列，减少Hash冲突
7.HashMap底层在·jdk1.8后的改动
? 当发现链表表中的链表长度大于8时，当发现链表中的元素个数大于8之后，
1.还会判断一下当前数组的长度，如果数组长度小于64时，此时并不会转化为红黑树，而是进行扩容。
2.只有当链表中的元素个数大于8，并且数组的长度大于等于64时才会将链表转为红黑树
?
?
?