JAVA开发之hashMap时间复杂度分析

发布时间:2022-08-24 14:40:44 作者:King 来源:本站 浏览量(1045) 点赞(48)
摘要:HashMap容器O(1)的查找时间复杂度只是其理想的状态,而这种理想状态需要由java设计者去保证。在由设计者保证了链表长度尽可能短的前提下,由于利用了数组结构,使得key的查找在O(1)时间内完成。可以将 HashMap分成两部分来看待,hash和map。map只是实现了键值对的存储。而其整个O(1)的查找复杂度很大程度上是由hash来保证的

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一个entey节点插入到数组中。时间复杂度O(1)。

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

第四步:如果桶里有元素,并且元素个数大于6,则调用equals方法,比较是否存在相同名字的key,不存在则new一个entry插入都链表尾部。时间复杂度O(1)+O(logn)=O(logn)。红黑树查询的时间复杂度是logn。

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

二,hash碰撞问题

HashMap在put元素时,首先会计算key的hashcode,这时候不会去调用equals方法。为什么呢?因为equals方法的时间复杂度是O(n)。但是HashMap存在hash碰撞问题,最坏的情况下,所有的key都被分配到了同一个桶,这时map的put和get时间复杂度都是O(n)。

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

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

答:HashMap解决哈希冲突采用的是链地址法。说白了就是把冲突的key连接起来,放到桶里。当桶中的元素个数不超过6个时,以单链表的形式串起来,当桶中的元素个数超过6个时,以红黑树的形式串起来。

 

过上面的分析,我们可以得出结论,HashMap的hash操作的时间复杂度是O(1),HashMap的equals操作的时间复杂度是O(n)。

如您有微信小程序开发、外卖、社区团购、分销商城、分销系统、量身定制开发、原生android定制、opencv人脸识别项目、网站建设等业务,可联系闪端,专业团队为您排优解难!


微信

扫一扫,关注我们

感兴趣吗?

欢迎联系我们,我们愿意为您解答任何有关网站疑难问题!

【如有开发需求】那就联系我们吧

搜索千万次不如咨询1次

承接:网站建设,手机网站,响应式网站,小程序开发,原生android开发等业务

立即咨询 16605125102