HashMap的时间复杂度 |
您所在的位置:网站首页 › hashmap查询数据的时间复杂度 › HashMap的时间复杂度 |
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) |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |