HashMap
HashMap是由数组和链表组合构成的数据结构。
大概如下,数组里面每个地方都存了Key-Value这样的实例,在Java1.7叫Entry,在Java1.8中叫Node。
因为它本身所有位置都为null,在put插入的时候会根据key的hash去计算一个index值。
就比如我put(“rubenwei”,666),我插入了为"rubenwei"的元素,这个时候我们会通过哈希函数计算出插入的位置,如果计算出来index是2,那就放在第三个位置
但我们知道数组长度是有限的,在有限的长度里面我们使用哈希,哈希本身就存在概率性,就是"rubenwei"和“ruben”我们都去hash有一定的概率计算出来的hashcode是重复的,这时候如果put“ruben”就会在当前entry节点下形成一个链表用于存放hashcode一样的这些元素
每一个节点都会保存自身的hash、key、value以及(next)下个节点
java8之前采用头插法,原有的值顺推到链表中去,新来的值变成链表表头,是因为代码作者认为新来的值会被查找的可能性大一点,为了提升查找的效率设计的
java8之后改用尾插法,当hashmap里数据插入达到一定值的时候【这个值可以通过Capacity(当前长度)*LoadFactor(负载因子,默认0.75f)计算得到】
扩容的时候分为两步,先创建一个长度为原有数组的两倍的空数组,再调用rehash遍历原有entry数组,把所有的entry重新hash到新数组
因为扩容的时候,Capacity会改变,所以不能直接复制
改用尾插法的原因:
因为hashmap是线程不安全的,所以如果多线程同时进行插入,此时又触发了扩容机制的时候,可能会导致环形链表,此时如果对它取值会导致死循环
因此java8之后改成了尾插法,在扩容时会保持链表元素原本的顺序,就不会出现链表成环的问题了
而且改用了红黑树,降低了时间复杂度
hashmap是线程不安全的,原因是put/get都没有加同步锁,多线程容易发生上一秒put的值,下一秒get就变了
hashmap初始化默认长度是16,因为1对4执行位运算就是16,位运算比算术计算的效率高了很多,所以选择2的幂,是为了实现均匀分布
重写equals时重写hashcode,是因为我们得通过这个hashcode方法去计算出我们在数组的哪个位置,然后通过equals去找到具体在链表的哪个位置
一般在需要线程安全的场景,我们用HashTable或者ConcurrentHashMap,但是因为HashTable的并发度原因,基本没什么使用场景了,所以一般使用ConcurrentHashMap
HashTable直接在方法上加锁,最多同时只能有一个线程操作,效率极低,ConcurrentHashMap则在效率上胜之
上一篇: 单链表反转 Java 版
推荐阅读
-
Java-深度分析基础HashMap实现
-
深入理解HashMap的内部工作原理
-
剖析 JDK源码:HashMap 1.8版本详解
-
透彻讲解 Java HashMap:关键点须知与性能提升技巧 - Java基础知识系列
-
大聪明教你学Java|Mybatis的一级缓存和二级缓存--🍊作者简介:不愿过河东,一个来自二线城市的程序员,致力于用 "猥琐 "的方法解决琐碎的问题,让复杂的问题变得简单易懂。支持作者:喜欢👍,关注💖,留言💌~! 前言。 在计算机世界中,缓存无处不在;操作系统有操作系统缓存,数据库会有数据库缓存,我们还可以利用中间件(如 Redis)来充当缓存。MyBatis 作为一个优秀的 ORM 框架,也用于缓存,所以今天我们就来谈谈 Mybatis 的一级缓存和二级缓存。 Mybatis 一级缓存 首先,我们来看一张图片👇。 我们在开发项目的过程中,如果打开Mybatis的SQL语句打印,经常会看到这样一句话:创建一个新的 SqlSession,其实这就是我们常说的 Mybatis 一级缓存。 Mybatis 的一级缓存也就是在执行一次 SQL 查询或 SQL 更新后,这条 SQL 语句并不会消失,而是被 MyBatis 缓存起来,当再次执行同样的 SQL 语句时,就会直接从缓存中提取出来,而不用再次执行 SQL 命令。第一级缓存也称为 SqlSession 级缓存。对数据库进行操作时,需要构建一个 SqlSession 对象,其中有一个用于存储缓存数据的数据结构(HashMap)。对象中有一个用于存储缓存数据的数据结构(HashMap)。不同 SqlSession 之间的缓存数据区域(HashMap)互不影响。 在我们的应用系统运行过程中,我们可能会在一个数据库会话中,执行多条查询条件相同的 SQL 语句,那么对于这种情况,你来进行设计,那么你会如何考虑呢?没错,就是加入缓存,MyBatis也是这么来处理的,如果是同一条SQL语句,会优先打入一级缓存,避免直接查询数据库,给数据库造成压力,提高性能。具体实现过程如下图所示👇 SqlSession 是一个接口,提供了一些 CRUD 方法,SqlSession 的默认实现类是 DefaultSqlSession,DefaultSqlSession 类持有 Executor 接口对象,Executor 的默认实现是 BaseExecutor 对象,每个 BaseExecutor 对象都有一个 PerpetualCache 缓存,即上图中的本地缓存。当用户发起查询时,MyBatis 会根据当前执行的语句生成一个 MappedStatement,并在本地缓存中进行查询,如果缓存被命中,查询结果会直接返回给用户;如果缓存未被命中,查询结果会直接返回给用户。如果缓存未命中,则查询数据库,将结果写入本地缓存,最后将结果返回给用户。这时候可能有小伙伴要说了:我还在控制台中看到 "关闭非事务性 SqlSession "这句话,说明我每次创建一个 SqlSession 到 SqlSession 结束都是关闭的,那么我的缓存还是有毛线用!😥 事情肯定不是我们想的那样,让我们继续👇。 🍊 getSqlSession 源代码
-
Java HashMap putIfAbsent 方法 | Java HashMap putIfAbsent 方法。
-
Java] HashMap、HashTable 和 ConcurrentHashMap 的区别--三、ConcurrentHashMap
-
询问如何在 Kotlin 中将 HashMap 转换为 ArrayListEN
-
java HashMap 按值回溯测试关键代码示例
-
HashMap 基础源代码分析