1. hashMap 1.8 之后当 链表的数量大于8 并且数组数量大于64 链表升级为红黑树
2. 1.8之前 get方法的时间复杂度:
最好情况:O(1)
最坏情况:去链表查找 O(1) + O(n)
put方法 时间复杂度:
最好的情况: O(1)
最坏的情况: O(1) (JDK8前才用头插法,即在单链表头部直接插
入,不需要遍历)
3. jdk 1.8 之后:
get方法的时间复杂度:
最好情况:O(1) 元素少的时候
最坏的情况:
当桶内元素不大于6个:O(N) (即单链表查询的时间复杂度)
当桶内元素大于8个:O(logN)(红黑树查询的时间复杂度为O(logN)与二分查找类似)
最坏情况,是搜索的结果,我认为应该是二者的时间复杂度之和,即: O(1) + O(n) 是数组 + 链表 时 get方法的时间复杂度, 当链表转换为红黑树后 O(1) + O(logN)
put 方法的时间复杂度:
最坏情况:O(1)
最坏的情况:
当桶内元素不大于6个:O(N)(JDK8尾插法,遍历到尾部再插入)
当桶内元素大于8个:O(logN)(红黑树插入的时间复杂度为O(logN)与二分插入类似)
最坏的情况,同理我认为需要加上O(1)
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
网站名称:HashMap的时间复杂度-创新互联
路径分享:https://www.cdcxhl.com/article20/dhpcjo.html
成都网站建设公司_创新互联,为您提供网站改版、响应式网站、建站公司、动态网站、品牌网站设计、软件开发
声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联