关于hashmap

落日映苍穹つ 2024-04-07 14:40 31阅读 0赞

**为什么说HashMap是线程不安全的？**  
在接近临界点时，若此时两个或者多个线程进行put操作，都会进行resize（扩容）和reHash（为key重新计算所在位置），而reHash在并发的情况下可能会形成[链表][Link 1]环。总结来说就是在多线程环境下，使用HashMap进行put操作会引起死循环，导致CPU利用率接近100%，所以在并发情况下不能使用HashMap。为什么在并发执行put操作会引起死循环？是因为多线程会导致HashMap的Entry链表形成环形数据结构，一旦形成环形数据结构，Entry的next节点永远不为空，就会产生死循环获取Entry。jdk1.7的情况下，并发扩容时容易形成链表环，此情况在1.8时就好太多太多了。因为在1.8中当链表长度大于阈值（默认长度为8）时，链表会被改成树形（红黑树）结构。

1.7和1.8的不安全  
1.7是容易形成环  
1.8假设两个线程A、B都在进行put操作，并且[hash][]函数计算出的插入下标是相同的，当线程A要执行插入的时候由于时间片耗尽导致被挂起，而线程B得到时间片后在该下标处插入了元素，完成了正常的插入，然后线程A获得时间片，由于之前已经进行了hash碰撞的判断，所有此时不会再进行判断，而是直接进行插入，这就导致了线程B插入的数据被线程A覆盖了，从而线程不安全。

**何时转红黑树？**  
hash冲突默认采用单链表存储，当单链表节点个数大于8时，会转化为红黑树存储。  
但是有一个前提：要求[数组][Link 2]长度大于64，否则不会进行转化

**1.7为什么cpu100%?**  
假设两个线程同时进行扩容，然后线程一再准备的扩容的时候被挂起，然后线程二进行了扩容，假设rehash的值，又进行了一个碰撞，所以线程二扩容之后，顺序已经改变了，相反，但是线程一这时候被唤醒了，然后他最初的指向没有变，e指向3，next指向2，这时候，进行扩容，会出现环状。就会导致cpu%100的情况。

**为什么阈值为8加载因子为0.75？**  
在理想情况下,使用随机哈希码，节点出现的频率在 hash 桶中遵循泊松分布。0.0000006源码写的  
对照桶中元素个数和概率的表，可以看到当用 0.75 作为加载因子时，桶中元素到达 8 个的时候，概率已经变得非常小，因此每个碰撞位置的链表长度超过 8 个是几乎不可能的，因此在链表节点到达 8 时才开始转化为红黑树。当然为了防止编程人员自己重新hashcode，让hash冲突增加，还是设置了红黑树的设定。

因为负载因为会使用在扩容上，0.5会使数组不停的扩容，扩容需要复制内容，牺牲了空间，换取了时间，而1.0会使红黑树一直处于修补树状态，会造成时间的浪费。而取舍是 两边各一半，0.75

**为什么不直接使用红黑树？**  
因为红黑树的结点存储是普通结点的两倍，红黑树虽然查询效率比链表高，但是结点占用的空间大，只有达到一定的数目才有树化的意义，这是基于时间和空间的平衡考虑。

因为红黑树需要进行左旋，右旋操作， 而单链表不需要，  
以下都是单链表与红黑树结构对比。  
如果元素小于8个，查询成本高，新增成本低  
如果元素大于8个，查询成本低，新增成本高  
鱼和熊掌不能兼得

**为什么退化为链表的阈值是6？**  
上面说到，当链表长度达到阈值8的时候会转为红黑树，但是红黑树退化为链表的阈值却是6，为什么不是小于8就退化呢？比如说7的时候就退化，偏偏要小于或等于6？  
主要是一个过渡，避免链表和红黑树之间频繁的转换。如果阈值是7的话，删除一个元素红黑树就必须退化为链表，增加一个元素就必须树化，来回不断的转换结构无疑会降低性能，所以阈值才不设置的那么临界。

**算出在数组的位置**  
1.首先计算key的hash值（不是单纯的调用key的hashCode方法）(h = key.hashCode()) ^ (h >>> 16)足够散列，高低位的异或  
2.hash值和（数组空间大小 - 1）做与运算，计算元素在数组中的索引。

**为什么数组大小一定是2的n次幂？**  
因为如果不是2的n次幂，比如14，1110，你会发现，你转二进制的时候，总会有的位数是0，这时候去&那个hashcode出来的值，这个位置上的值永远是0，会导致散列到你的数组时候，永远有一个地方空着的。

大小是2^n（2的n次幂）  
说是2的倍数并不严谨，就算你是个偶数，比如说12，那么12-1=11,11的二进制是1011，并不符合设计

**为什么要数组长度64？**  
当链表长度大于8并且数组长度大于64时，才会转换为红黑树。  
如果链表长度大于8，但是数组长度小于64时，还是会进行扩容操作，不会转换为红黑树。因为数组的长度较小，应该尽量避开红黑树。因为红黑树需要进行左旋，右旋，变色操作来保持平衡，  
所以当数组长度小于64，使用数组加链表比使用红黑树查询速度要更快、效率要更高

**hashmap1.7和hashmap1.8put区别？**  
1.7：  
计算h = key.hashCode()) ^ (h >>> 16)然后对数组长度取模运算。把put进来的key和value封装成一个entry对象，计算出在数组长度的位置，然后判断该位置是否有数据，没数据直接存储，有数据，先判断链表中是否有相同的数据，没有直接把数据插入该链表中。有相同的直接覆盖。使用的是头插法  
1.8：  
计算h = key.hashCode()) ^ (h >>> 16)然后对数组长度取模运算，算出数组的位置。先判断是否为空。  
为空，直接将封装的entry赋值给该数组的位置  
不为空，先判断是否等于该位置的元素，  
等于当前直接覆盖，  
不等于，说明hash碰撞，再进行判断是否为treenode类型  
是代表直接是一个红黑树，直接进行插入，判断是否重复  
不是就说明是链表，然后进行一个遍历，同时会进行一个计数，查询是否有结点跟我put的结点相同，相同继续覆盖，如果没有，插入到尾部，判断我插入的这个结点之后链表长度是否大于了8，大于了8转为红黑树  
这里面所有的重复的，都调用onlyIfAbsent标记来判断是否需要更新value值  
**就直接简化为四种情况**  
1.slot等于null 直接占用  
2.slot不等于null而且没有链化  
判断key是否相等，然后相等进行覆盖，不相等为尾节点插入  
3.slot已经链化了  
依次遍历链表有重复 的进行覆盖，没有就插入到尾节点，在判断插入的时候是否大于8，数组大于64，进行一个转红黑树，树化  
4.slot是红黑树  
遍历红黑树，然后也判断key是否重复，重复覆盖，不重复，进行一个插入。基于红黑树的插入。就不涉及了

**hashmap1.7和hashmap1.8get**  
先判断数组是否为空。为空直接返回  
计算h = key.hashCode()) ^ (h >>> 16)然后对数组长度取模运算，算出数组的位置，先判断第一个位置的元素是否等于我传过来的key  
是，就直接返回该元素的value  
不是，再进行判断是否有下一个元素  
没有，直接返回空  
有，判断该结点的类型是treenode还是链表结点  
然后对应分别进行遍历，判断是否存在key，不存在返回null

**hashmap1.7和hashmap1.8扩容**  
数组的扩容，新建一个2倍大小的数组，然后遍历老数组的元素，如果是链表，直接把这个链表转移到新数组上去  
这个过程就是设计到1.7和1.8的实现  
1.7只是简单的遍历原数组的每一个元素，然后重新hash计算，然后存放到新的数组里面去。这样链表会缩短，提高查询效率  
1.8，因为涉及到红黑树。所以他底层用了一个双向链表(高低位链表)来维护这个红黑树(减少扩容的迁移量)，如果该结点是一个红黑树，然后遍历整个红黑树，计算出哪些结点在原数组的位置，哪些结点在新数组的位置。这样就会生成两个子链表，然后再判断原数组和新数组的位置是否存在元素。  
不存在，就直接存储。  
存在，判断两个子链表的长度是否超过8  
超过，转成红黑树放到对应的位置  
不超过，把单链表放到对应的位置

**1.8的扩容  
分4种情况**  
1.null 不变  
2.存储的是一个单个node  
直接计算hash进行迁移  
3.存储的是一个链表  
高位链和低位链  
因为是链表。所以这个链表所计算出来的低位链都是相同的，就是这个链表的所有数据&老表的长度-1都是相同的，这时候的低位链都是相同的(假设老数组为16，1111)。但这时候的高位(第五位)可能不同有得为1有得为0，因为扩容计算肯定会多一位嘛，所以迁移到新表得位置也不一样，假设为0，就说明在原来的位置没有变，但是是1的话，就是当前的位置加老数组的位置，这就是在新数组的位置例如原来是8数组16现在的位置就是24  
4.存储的是红黑树  
其实差不多。主要是看一下长度，高低位的链表的长度，如果是小于6的话，转为链表来进行一个存放。如果是8的话还是会进行一个重新构建红黑树。

**为什么Java8中HashMap链表使用红黑树而不是AVL树？**  
在CurrentHashMap中是加锁了的，实际上是读写锁，如果写冲突就会等待，如果插入时间过长必然等待时间更长，而红黑树相对AVL树他的插入更快！  
因为AVL的查询很快，但是增删比红黑树慢，整体性能红黑树好一点  
红黑树整体的查询和增加删除更加稳定，虽然AVL查询更快，但是它的增删比红黑树慢

**HashMap是先插入还是先扩容？**  
HashMap初始化后首次插入数据时，先发生resize扩容再插入数据，之后每当插入的数据个数达到threshold时就会发生resize，此时是先插入数据再resize。

**为什么要右移16位？**  
其实是为了减少碰撞，进一步降低hash冲突的几率。int类型的数值是4个字节(32位)的，右移16位异或可以同时保留高16位于低16位的特征

**为什么要异或运算？**  
首先将高16位无符号右移16位与低十六位做异或运算。如果不这样做，而是直接做&运算那么高十六位所代表的部分特征就可能被丢失 将高十六位无符号右移之后与低十六位做异或运算使得高十六位的特征与低十六位的特征进行了混合得到的新的数值中就高位与低位的信息都被保留了 ，而在这里采用异或运算而不采用& ，| 运算的原因是 异或运算能更好的保留各部分的特征，如果采用&运算计算出来的值会向1靠拢，采用|运算计算出来的值会向0靠拢

**HashMap以null作为key时，总是存储在table数组的第一个节点上**  
它是根据key的hashCode来寻找存放位置的，在put方法里头，其实第一行就处理了key=null的情况。  
当HashMap的put方法，第二个判断就是key为null的判断后进入putForNullKey(V value)这个方法  
putForNullKey个for循环，是在talbe\[0\]链表中查找key为null的元素，如果找到，则将value重新赋值给这个元素的value，并返回原来的value。  
如果上面for循环没找到则将这个元素添加到talbe\[0\]链表的表头。

**通过构造初始化的参数，会动态的生成该参数的最小二倍数**  
hashmap通过构造设置得初始值会动态得扩容到2得n次幂  
例如想要用 HashMap 存放 1k 条数据，应该设置 1000 / 0.75，实际传递进去的值是 1333，然后会被 tableSizeFor() 方法调整到 2048，足够存储数据而不会触发扩容。

当想用 HashMap 存放 1w 条数据时，依然设置 10000 / 0.75，实际传递进去的值是 13333，会被调整到 16384，和我们直接传递 10000 效果是一样的。

这儿用的tableSizeFor 的算法（核心思想是生成大于数字的最小2倍数）  
static final int tableSizeFor(int cap) \{  
int n = cap - 1;  
n |= n >>> 1; //或右移1位的算法使 最高位的"非零0 第1位"变1  
n |= n >>> 2; // 或右移2位的算法使 最高位的"非零0 第1,2位"变1  
n |= n >>> 4;// 或右移2位的算法使 最高位的"非零0 第1~4位"变1  
n |= n >>> 8;// 或右移2位的算法使 最高位的"非零0 第1~8位"变1  
n |= n >>> 16;//或右移2位的算法使 最高位的"非零0 第1~16位"变1  
//算法结束后，得到 cap 的非0位的1+2+4+8+16 = 31位变1 基本上覆盖了最大值Integer.MaxValue;  
return (n < 0) ? 1 : (n >= MAXIMUM\_CAPACITY) ? MAXIMUM\_CAPACITY : n + 1;  
\}

使用位运算：位运算确实比取模运算快得多，大约快了27倍。

[Link 1]: https://so.csdn.net/so/search?q=%E9%93%BE%E8%A1%A8&spm=1001.2101.3001.7020
[hash]: https://so.csdn.net/so/search?q=hash&spm=1001.2101.3001.7020
[Link 2]: https://so.csdn.net/so/search?q=%E6%95%B0%E7%BB%84&spm=1001.2101.3001.7020