面试官：请说说 HashMap的时间复杂度是多少?

问：ConcurrentHashMap 的存储结构是怎样的？

• Java7 中 ConcurrnetHashMap 使用的分段锁，

  也就是每一个 Segment 上同时只有一个线程可以操作，每一个 Segment 都是一个类似 HashMap 数组的结构，它可以扩容，它的冲突会转化为链表。但是 Segment 的个数一但初始化就不能改变，默认 Segment的个数是 16 个。

• Java8 中的 ConcurrnetHashMap 使用的 Synchronized 锁加 CAS 的机制。

  结构也由 Java7 中的 Segment 数组 + HashEntry 数组 + 链表 进化成了 Node 数组 + 链表 / 红黑树，Node 是类似于一个 HashEntry 的结构。它的冲突再达到一定大小时会转化成红黑树，在冲突小于一定数量时又退回链表。

https://www.processon.com/view/link/638bfe69e0b34d527931186b

以上链接，请参见《尼恩Java 面试宝典》V14版本。

聊聊：HashMap的时间复杂度

HashMap容器O(1)的查找时间复杂度只是其理想的状态，而这种理想状态需要由java设计者去保证。

在由设计者保证了链表长度尽可能短的前提下，由于利用了数组结构，使得key的查找在O(1)时间内完成。

可以将 HashMap分成两部分来看待，hash和map。map只是实现了键值对的存储。而其整个O(1)的查找复杂度很大程度上是由hash来保证的。

HashMap对hash的使用体现出一些设计哲学，如：通过key.hashCode()将普通的object对象转换为int值，从而可以将其视为数组下标，利用数组O(1)的查找性能。

OK，下面我们来看看HashMap中新增元素的时间复杂度。

put操作的流程：

第一步：key.hashcode()，时间复杂度O(1)。

第二步：找到桶以后，判断桶里是否有元素，如果没有，直接new一个entry节点插入到数组中。时间复杂度O(1)。

第三步：如果桶里有元素，并且元素个数不超过8时，则调用equals方法，比较是否存在相同名字的key，不存在则new一个entry插入都链表尾部。时间复杂度O(1)+O(n)=O(n)。

第四步：如果桶里有元素，并且元素个数超过8时，则调用equals方法，比较是否存在相同名字的key，不存在则new一个entry插入红黑树。时间复杂度O(1)+O(logn)=O(logn)。红黑树查询的时间复杂度是logn。

通过上面的分析，我们可以得出结论，HashMap新增元素的时间复杂度是不固定的，可能的值有O(1)、O(logn)、O(n)。

get操作的流程：

和put操作的流程很类似， 需要从 计算key的hashcode，得到key的bucket 桶的槽位，然后通过 equals方法，在桶的链表或者红黑树里边，一个一个的比较，找到 equals方法为true的为主。

通过上面的分析，我们可以得出结论，HashMap获取元素的时间复杂度是不固定的，可能的值有O(1)、O(logn)、O(n)。

根因：hash碰撞问题

HashMap在put、get元素时，首先会计算key的hashcode，如果没有发生hash碰撞，而不是去调用equals方法。

为什么呢？因为equals方法的时间复杂度是O(n)。

但是HashMap，无论hash多么分布均匀，在空间不够僧多粥少的情况下，基本都会存在hash碰撞问题，

最坏的情况下，所有的key都被分配到了同一个桶，这时map的put和get时间复杂度都是O(n)。

所以HashMap的设计者必须要考虑的一个问题就是减少hash碰撞。

HashMap解决哈希冲突采用的是哪种方式呢？

答：HashMap解决哈希冲突采用的是链地址法。

说白了就是把冲突的key连接起来，放到桶里。

当桶中的元素个数不超过8时，以单链表的形式串起来，put和get时间复杂度都是O(1)+O(n)。

当桶中的元素个数超过8个时，以红黑树的形式串起来，put和get时间复杂度都是O(1)+O(logn)。

硬核文章推荐

• 一文穿透：高性能环形队列、 条带环形队列 Striped-RingBuffer 架构分析
• 吊打面试官：如何优雅的使用 单例模式 ？来看看缓存之王 Caffeine 、链路之王 Skywalking 是如何做的吧！
• 吊打面试官：Java官方JVM 为啥要叫做 HotSpot JVM？ 背后的水，不知道有多深！！！

硬核电子书

本文收录于：《尼恩Java 面试宝典》V13版 

长按二维码，点击“识别图中二维码”即可查看老架构师尼恩个人微信，发暗号 “领电子书” 给尼恩，获取最新PDF。

• 最新的《尼恩Java面试宝典》

  极致经典，不断升级，目前最新为V13

• 尼恩Java高并发三部曲

  《Java高并发核心编程-卷1（加强版）》，不断升级

  《Java高并发核心编程-卷2（加强版）》，不断升级

  《Java高并发核心编程-卷3（加强版）》，不断升级

• 尼恩架构笔记100篇+，不断添加