Java基础-Hashmap1.8

JDK1.8的HashMap数据结构和原理[面试9.9]?

JDK1.8的HashMap数据结构和原理[面试9.9]?

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tPC09pPk-1661824113916)(images/base_p_008.png)]

数据结构: 数组+链表+红黑树
数组: 空间连续,查询快,但是插入和删除较慢,因为要移动元素
链表: 增加删除快,因为是内存地址指针,查找慢,因为需要按顺序依次查询
红黑树: 一种平衡的二叉树,以O(log(n))的时间复杂度进行搜索,插入,删除等操作
hashmap数据结构-原理
hashmap1.8数据结构-视频
key是怎么进行hash运算的?
若key为空直接返回0
若key不为空才进行运算,key取hashCode的值(32位)无符号右移(>>>)16位得到的值和该hashCode进行异或(^)
异或是二进制相同为0,不同为1的算法
这样做可以减少Hash碰撞,原因是高位特征和低位特征可以得到异或(^)混合保留下来,更能区分Hash值,而按位与(&)计算结果趋于0,按位或(|)计算结果趋于1,都不适合用来做计算
为啥要右移: 由于hashMap通常是低位进行运算

HashMap怎么获取数组下标的?:
(n - 1) & hash --> 得到下标,其中n是数组的长度,n为2的n次方时该方法等价于hash % n

为什么hashmap要用16来作为数组的初始长度,并且扩容时按16的倍数来扩容?
因为这样n是2的n次方,这种情况下hashcode % n == hashcode & (n-1),而且后者效率高
之所以相等: 是因为2的n次方的整数减去一个1的话->二进制正好从1000…变成0111…这种结果
之所以效率高:
位运算消耗的CPU周期少,根据反汇编可以看到
另外位运算不需要转化为10进制,是内存直接操作的

HashMap什么时候转化为红黑树?
链表长度大于7时,数组长度达到64时转为红黑树,是因为根据泊松分布的概率统计来看,当链表长度为8时,数组中某一个下标放入8个数据的概率很小大致为亿分之六,已经很小了所以可以做为转化为红黑树的临界值

红黑树什么时候会退化为链表?
当节点数为6时进行退化,因为若为7的话可能会频繁的转化为树或退化为链表

转化为链表时是头插法还是尾插法?
尾插法,因为头插法在多线程的情况下会导致死链
死链: 1.7会出现,因为采用了头插法(头先插入新哈希表,尾后插入),试想两个线程,一个线程先执行完了next已经指定好了,第二个线程将next指向按相反的方式指向就会形成环,而1.8由于都是在尾部插入,元素的顺序始终一致所以不会出现环

HashMap中put方法过程:
对Key求Hash值,计算数组下标
若无碰撞,直接放入数组,若碰撞了,以链表的方式链接到Node后面(尾插法)
如果链表长度大于8且数组长度达到64时就把链表转成红黑树
如果数组快满了(容量 * 加载因子),就需要扩容,扩容按16->32->64…进行扩容

HashMap怎样扩容的?
数组为空初始化时调用扩容方法,这时容量被设置为16,扩容阈值为12(容量长度*加载因子)
转为红黑树时扩容,hash冲突时,链表达到长度9开始判断是否要转为红黑树,当未达到最小树化数组长度64时,按32和64进行扩容
实际数组长度大于扩容阈值时扩容
扩容时,数组长度规律是16->32->64…即两倍(原长度左移1位)
扩容后,然后对每个节点重新计算哈希值,开始搬砖

HashMap效率那么高:
HashMap采用数组+链表+红黑树的方式数据结构
hashCode算法本身是位移操作比较快
数组查询快(时间复杂度为O(1)),添加删除慢
链表添加删除快,查询慢HashMap正好采用了两者的优点
红黑树能够以O(log2(N))的时间复杂度进行搜索,插入,删除操作效率都比较快

为什么HashMap线程不安全:
未做同步处理,Java的内存模型中是主内存提供共享变量,工作内存负责加载变量的副本,并交由线程处理变量的值,在多线程环境下,若不实现同步就会导致同一时间一个工作线程在写数据,一个工作线程在读数据,倘若正好读到没有及时刷新到主内存的数据就会读到之前的数据,导致数据问题

hashmap1.8详解
hashmap参考[阅5分钟,250行]

ConcurrentHashMap怎么实现线程安全的?[面试8.0]

ConcurrentHashMap
针对数组元素采用了for循环的CAS(CompareAndSwapObject)机制来保证线程安全
针对链表或红黑树的节点(Node)采用了synchronized,保证线程安全,由于是在节点上加锁,没有对整个数组加锁,这样效率是比较好的