001-Java基础-Map

Map整体结构

Map的子类主要包括HashTable、HashMap、TreeMap、LinkedHashMap。

HashMap应用范围最广。 HashTable是HashMap早期的线程安全版本,但以不推荐使用。 TreeMap通过红黑树实现。 LinkedHashMap在HashMap基础上增加双向链表保存数据插入顺序。

HashMap的数据结构

这是非常高频的一个问题,最常见回答是HashMap由数组+链表实现,在JDK 1.8以后,如果链表超过一定长度,会变成一颗红黑树。

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

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

HashMap执行put方法的逻辑

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

除了put方法的逻辑,还可以继续追问get方法。

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等操作,在特定场景进行无锁并发操作。
上篇001-Java基础-并发包(线程安全容器)
下篇001-Java基础-集合