HashMap连环问

“Hash的实现原理”是Java面试中非常高频的一个问题,以这个问题为起点,我们能问出多少与HashMap相关的问题?甚至进一步引申到其它的知识点?

这篇文章我就来开开脑洞,来一个HashMap连环问。

HashMap

HashMap的数据结构

最常见的一个问题,一般都会回答HashMap是由数组+链表实现,在JDK 1.8以后,当链表超过一定长度之后,会变成一颗红黑树。

但是,说数组其实并不完全正确,最准确的说法其实是散列表。

由此,可以继续问HashMap相关的内容,也可以扩展到散列表链表三个方向。

HashMap执行put方法的逻辑

  • 通过Hash算法根据key计算对应的Hash值。-> Hash算法
  • 根据Hash值找到散列表中对应的位置,并判断是否需要扩容。
  • 查看散列表对应链表,判断value在链表中是否已存在,不存在则将数据添加到链表。
  • (JDK1.8以后) 判断链表长度,如果超过阈值,则将链表变化为红黑树。 ->

HashMap的装载因子有什么作用

装载因子表示散列表中空间的最大使用比例,当被使用空间超过这个比例时,HashMap会对散列表进行扩容。

装载因子的计算公式: 装载因子 = 散列表中元素个数 / 散列表长度

装载因子的设置要综合时间、空间复杂度来考虑。

装载因子小,哈希冲突少,但是内存利用率低,HashMap会频繁扩容。 装载因子大,内存利用率更高,但是哈希冲突更频繁。

HashMap扩容时会执行哪些操作

  • 申请一个新的散列表,长度是原散列表的两倍。
  • 遍历原散列表的数据,根据当前散列值计算在新表中的位置。
  • 将数据复制到新表的新位置。

由此可见,每次扩容时都会有数据迁移,当HashMap比较大时,这会是一个非常耗时过程。

HashMap是非线程安全的,这会导致什么问题

在高并发情况下执行扩容时,新的链表可能出现环,导致程序陷入死循环,最后CPU飙升到100%。

简述过程:

  • A、B两个线程同时进行扩容。
  • A线程获取到链表节点C的信息,next节点为D。
  • B线程获取到链表节点C的信息,next节点为D。
  • B线程完成扩容,扩容后C变成D的next节点。
  • A线程继续扩容,复制C节点的信息后拿到D节点。
  • A线程复制D节点信息后,获取next节点,此时为C。
  • A线程陷入D->C->D->C…的死循环。

扩展阅读 -> 漫画:高并发下的HashMap 如何检测链表中是否有环

Java中线程安全的Map有哪些

HashTable或者CocurrentHashMap。

Hashtable如何实现线程安全

简单粗暴,在put、get、size等方法上使用synchronized 关键字来保证线程安全。

这种方式虽然简单,但是对性能很差,因此在高并发场景中并不推荐使用Hashtable。

ConcurrentHashMap如何实现线程安全

首先要注意的是,ConcurrentHashMap的实现方式一直在演讲,尤其是Java8版本,发生了很大的变化。

Java8以前,ConcurrentHashMap的实现:

  • 分离锁,将内部分为多个Segment,每个Segment包含若干HashEntry数组,和HashMap类似,哈希相同的数据以链表形式存放。
  • HashEntry内部使用volatile关键字保证可见性。

Java8以后,ConcurrentHashMap的实现:

  • 取消Segment结构,采用与HashMap类似的散列表+链表结构,同步控制的颗粒度更新。
  • 内部仍有Segment定义,但不在有任何结构上的用处,仅仅是为了兼容。
  • 使用CAS等操作,在特定场景进行无锁并发操作。

Hash算法

// TODO

好的哈希算法应该具备哪些特点

如何避免散列冲突

哈希算法的应用场景

散列表

// TODO

散列表的特点

哈希算法的特点

解决哈希冲突都有哪些办法(寻址法、链表法)

常见的哈希算法有哪些(MD5、SHA256)

哈希算法的应用(安全加密、数据校验、唯

一标识、散列函数、负载均衡、数据分片、分布式存储)

为什么散列表经常和链表一起使用

为什么数组能够根据下标快速查找数据

为什么数组插入数据很慢

链表

// TODO

如何检测链表中是否有环

链表与数组性能的对比

为什么链表查找慢,插入/删除快

如何用链表实现LRU缓存淘汰算法 -> 缓存

为什么HashMap中链表长了要变成红黑树 ->

// TODO

链表与树的关系

什么是二叉树,特点

二叉树的查询,插入,删除过程

二叉树与散列表的对比

红黑树的特点,解决了什么问题

B+树的特点,解决了什么问题 -> MYSQL

缓存

// TODO

缓存的类型(本地、集中、分布式)

常用的缓存中间件

使用缓存常见的设计问题(穿透、雪崩、预热、刷新、降级)

Redis到底有多快

为什么Redis这么快(基于内存、数据结构 简单、单线程、多路复用,底层模型)

Redis支持哪些数据类型,它们的数据结构是怎样的

什么是多路复用

MYSQL

// TODO

mysql的索引是如何存储数据的(主键索引,非主键索引)

为什么mysql主键建议用连续的数字(减少主键索引页分裂)

什么是索引的最左原则

什么是回表操作

mysql执行sql语句的过程

mysql的redolog与binlog

mysql count(*) 的统计逻辑

mysql delete与drop的区别

如何对比两个不同的数据库

上篇001-JAVA基础-异常类
下篇常见链表操作-求链表的中间节(JAVA实现)