HashMap五大核心问题总结

简介: HashMap五大核心问题总结

Jdk8的hashmap与Jdk7的hashmap有什么区别

1. JDK8中新增了红黑树,JDK8是通过数组+链表+红黑树来实现的

2. JDK7中链表的插入是用的头插法,而JDK8中则改为了尾插法

3. JDK8中的因为使用了红黑树保证了插入和查询了效率,所以实际上JDK8中 的Hash算法实现的复杂度降低了

4. JDK8中数组扩容的条件也发了变化,只会判断是否当前元素个数是否超过了阈值,而不再判断当前put进来的元素对应的数组下标位置是否有值。

5. JDK7中是先扩容再添加新元素,JDK8中是先添加新元素然后再扩容

HashMap中put方法的流程

1. 通过key计算出一个hashcode

2. 通过hashcode与“与操作”计算出一个数组下标

3. 在把put进来的key,value封装为一个entry对象

4. 判断数组下标对应的位置,是不是空,如果是空则把entry直接存在该数组位置

5. 如果该下标对应的位置不为空,则需要把entry插入到链表中

6. 并且还需要判断该链表中是否存在相同的key,如果存在,则更新value

7. 如果是JDK7,则使用头插法

8. 如果是JDK8,则会遍历链表,并且在遍历链表的过程中,统计当前链表的元 素个数,如果超过8个,则先把链表转变为红黑树,并且把元素插入到红黑树中

Jdk8中链表转换为红黑树的条件

1. 链表中的元素的个数为8个或超过8个

2. 同时,还要满足当前数组的长度大于或等于64才会把链表转变为红黑树。因为链表转变为红黑树的目的是为了解决链表过长,导致查询和插入效率慢的问题,而如果要解决这个问题,也可以通过数组扩容,把链表缩短也可以解决这个问题。所以在数组长度还不太长的情况,可以先通过数组扩容来解决链表过长的问题。

HashMap的扩容流程

1. HashMap的扩容指的就是数组的扩容, 因为数组占用的是连续内存空间, 所以数组的扩容其实只能新开一个新的数组,然后把老数组上的元素转移到新数组上来,这样才是数组的扩容

2. 在HashMap中也是一样,先新建一个2倍数组大小的数组

3. 然后遍历老数组上的每一个位置,如果这个位置上是一个链表,就把这个链表上的元素转移到新数组上去

4. 在这个过程中就需要遍历链表,当然jdk7,和jdk8在这个实现时是有不一样 的,jdk7就是简单的遍历链表上的每一个元素,然后按每个元素的hashcode结合新数组的长度重新计算得出一个下标,而重新得到的这个数组下标很可能和之前的数组下标是不一样的,这样子就达到了一种效果,就是扩容之后,某个链表会变短,这也就达到了扩容的目的,缩短链表长度,提高了查询效率

5. 而在jdk8中,因为涉及到红黑树,这个其实比较复杂,jdk8中其实还会用到 一个双向链表来维护红黑树中的元素,所以jdk8中在转移某个位置上的元素 时,会去判断如果这个位置是一个红黑树,那么会遍历该位置的双向链表,遍 历双向链表统计哪些元素在扩容完之后还是原位置,哪些元素在扩容之后在新 位置,这样遍历完双向链表后,就会得到两个子链表,一个放在原下标位置, 一个放在新下标位置,如果原下标位置或新下标位置没有元素,则红黑树不用 拆分,否则判断这两个子链表的长度,如果超过八,则转成红黑树放到对应的 位置,否则把单向链表放到对应的位置。

6. 元素转移完了之后,在把新数组对象赋值给HashMap的table属性,老数组会被回收。

为什么HashMap的数组大小是2的幂次方

JDK7的HashMap是数组+链表实现的

JDK8的HashMap是数组+链表+红黑树实现的

当某个key-value对需要存储到数组中时,需要先生成一个数组下标index,并且这个 index不能越界。在HashMap中,先得到key的hashcode,hashcode是一个数字,然后通过  hashcode & (table.length - 1) 运算得到一个数组下标index,是通过与运算计算出 来一个数组下标的,而不是通过取余,与运算相比于取余运算速度更快,但是也有一 个前提条件,就是数组的长度得是一个2的幂次方数。

目录
打赏
0
4
4
0
41
分享
相关文章
蚂蚁金服Java研发岗二面:redis 常见数据结构以及使用场景分析
redis简单来说 就是一个数据库,不过与传统数据库不同的是 redis 的数据是存在内存中的,所以存写速度非常快,因此 redis 被广泛应用于缓存方向。另外,redis 也经常用来做分布式锁。redis 提供了多种数据类型来支持不同的业务场景。除此之外,redis 支持事务 、持久化、LUA脚本、LRU驱动事件、多种集群方案。所以在面试中我们经常可以看到redis的身影,今天给大家带来一道redis的面试真题以及解析,后面会给大家分享今年来redis常考试的一些真题。
232 0
java之上转型与下转型对象
java之上转型与下转型对象
119 0
探索ConcurrentHashMap:从底层到应用的深度剖析
【10月更文挑战第6天】在Java并发编程中,ConcurrentHashMap是一个非常重要的数据结构,它提供了一种线程安全的哈希表实现。本文将深入探讨ConcurrentHashMap的底层存储结构、红黑树转换时机、数组扩容时机、核心属性sizeCtl、数组初始化、DCL操作、散列算法、写入操作的并发安全、计数器的安全机制以及size方法的实现策略。
138 1
|
11月前
|
Queue大比拼:为何LinkedList能在众多Java集合中脱颖而出?
【6月更文挑战第18天】**Java的LinkedList作为队列的优势在于其双向链表实现,支持O(1)时间复杂度的首尾操作,适合作为Queue接口的实现。它也是线程不安全的,但在单线程环境下性能优越,并可通过Collections同步化。此外,它的灵活性使其也能胜任栈和双端队列的角色。**
71 5
技术经验分享:HashCode解析
技术经验分享:HashCode解析
53 0
Java 8新特性解析及应用区块链技术在供应链管理中的应用与挑战
【4月更文挑战第30天】本文将深入探讨Java 8的新特性,包括Lambda表达式、Stream API和Optional类等。通过对这些新特性的详细解析和应用实例,帮助读者更好地理解和掌握Java 8的新技术。
蚂蚁金服Java研发岗二面:说说HashMap 中的容量与扩容实现
JDK1.8 中 HashMap 的底层实现,我相信大家都能说上来个 一二,底层数据结构 数组 + 链表(或红黑树) ,源码如下
【Java编程进阶之路 01】深入探索:HashMap、ConcurrentHashMap与HashTable的演进之路
HashMap、ConcurrentHashMap与HashTable均为Java中的哈希表实现。HashMap非线程安全但性能高,适用于单线程;HashTable线程安全但性能较低,已少用;ConcurrentHashMap线程安全且高性能,是并发环境下的首选。三者在线程安全性与性能间各有侧重。
98 1
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等