HashMap的时间复杂度

HashMap的时间复杂度

HashMap的时间复杂度

HashMap在jdk1.8之后引入了红黑树的概念,表示若桶中链表元素超过8时,会自动转化成红黑树;

若桶中元素小于等于6时,树结构还原成链表形式。

原因:

红黑树的平均查找长度是log(n),长度为8,查找长度为log(8)=3,链表的平均查找长度为n/2,当长度为8时,平均查找长度为8/2=4,这才有转换成树的必要;链表长度如果是小于等于6,6/2=3,虽然速度也很快的,但是转化为树结构和生成树的时间并不会太短。

还有选择6和8的原因是:

中间有个差值7可以防止链表和树之间频繁的转换。假设一下,如果设计成链表个数超过8则链表转换成树结构,链表个数小于8则树结构转换成链表,如果一个HashMap不停的插入、删除元素,链表个数在8左右徘徊,就会频繁的发生树转链表、链表转树,效率会很低。

时间复杂度

不管插入还是查找,由key获取hash值然后定位到桶的时间复杂度都是O(1),那么真正决定时间复杂度的实际上是桶里面链表/红黑树的情况

如果桶里面没有元素,那么直接将元素插入/或者直接返回未查找到,时间复杂度就是O(1),如果里面有元素,那么就沿着链表进行遍历,时间复杂度就是O(n),链表越短时间复杂度越低,如果是红黑树的话那就是O(logn)

所以平均复杂度很难说,只能说在最优的情况下是O(1)

HashMap的时间复杂度

上一篇:git 仓库操作


下一篇:Auth2.0 授权码、凭证式授权两种方式