库调多了,都忘了最基础的概念 -HashMap 篇

? 作者:知识浅谈,CSDN博客专家,阿里云签约博主,InfoQ签约博主,华为云云享专家

? 擅长领域:全栈工程师、爬虫、ACM算法

? 公众号:知识浅谈

​温馨提醒:由于内容较好,请18岁以上成年人观看​

?这次都给他拿下?

库调多了,都忘了最基础的概念 -HashMap 篇

?说一下HashMap底层实现?及元素添加流程?

因为JDK1.7和JDK1.8是有区别的,所以按照不同的版本记录 JDK1.7版本:

  1. 底层结构使用数组+链表的方式实现。
  2. 数组中最初的大小为16个节点,阈值为0.75,当达到阈值的时候进行扩容,扩容每次扩容为原来的2倍。
  3. 链表插入节点的时候使用头插法。

?元素添加的过程:这个版本的元素添加是先判断是否达到阈值,即先扩容,后添加。 添加的时候找到对应的位置,如果为空进行赋值,否则如果是链表采用头插法把值插入。

?存在的问题:存在循环链表和值覆盖的问题。

JDK1.8版本:

  1. 底层结构使用数组+链表+红黑树的方式实现。
  2. 数组中最初的大小为16个节点,阈值为0.75,当达到阈值的时候进行扩容,扩容每次扩容为原来的2倍,相比于JDK1.7还有一点就是当链表的节点数大于8且整个map中元素的个数大于64的时候,链表转化为红黑树,当链表中的节点数小于6的时候,红黑树退化为链表。
  3. 链表插入节点的时候使用尾插法。

?元素添加的过程:这个版本的元素添加是先添加,后判断是否进行扩容。 添加的时候找到对应的位置,如果为空进行赋值,否则如果是链表采用尾部插法把值插入,否则如果是红黑树,则在红黑树中插入对应的节点。

?存在的问题: 解决了循环链表的问题,但是仍然存在值覆盖的问题。

?为什么HashMap会产生死循环?

这个死循环就是上边提到的循环链表的问题,这个问题是发生在扩容的时候,当多个线程进行节点并发插入的时候,都需要进行扩容,一个线程扩容完,另一个线程本来在前一个线程扩容之前已经指向原本的头节点,扩容之后头节点指向的next节点变化了,当第二个线程扩容的时候就行成了循环。

?HashMap除了死循环之外,还有什么问题?

正如上边提到的,除了死循环,还有值覆盖的问题,就是当数组中的一个节点为空的时候两个元素要同时插入的时候当一个节点获取了位置要插入的时候,时间片到了,另一个线程插入了,之后到另一个线程的时候也进行了插入,就把之前的给覆盖了。

?为什么ConcurrentHashMap是线程安全的?

?JDK1.7版本: 使用分段锁的形式,即用segment数组来进行加锁的形式,每个锁下记录一个数组+链表的结构,这个数组的初始值和阈值为16和0.75,同理每个segment下都是如此,为什么concurrentHashMap是安全的,就是因为当修改的时候先锁住一个段下的所有内容进行修改,如果不同段中的数据,是可以并行修改的。

?JDK1.8版本: 采用Synchronized+CMS的形式,就是对数组中每个节点加synchronized的形式,然后在进行扩容,sychronized锁住结点之后使用CMS的方法进行扩容,并且还支持并发扩容,也就是可以多个线程同时进行扩容,且扩容不用计算hash值,如果之前的hash大于原来的数组则就把当前节点移动到当前节点+原数组长度的位置。

?总结

发表评论

相关文章