hashmap get、put时间复杂度

标签：logN 单链 hashmap 复杂度 元素 当桶 情况 put

在JDK8之前

用单链表HashMap作为一个桶来储存存在哈希碰撞的元素。无论是get还是put方法，步骤都可以分为第一步找桶(找桶时间都为O(1)，可以忽略)，第二步在桶内进行操作(查找或者插入)，首先最好的情况为没有任何哈希碰撞的情况,即所有元素分配在不同的桶，最坏的情况为所有元素碰撞在一起，即全部被分配在同一个桶。所以情况复杂度如下：

• GET最好情况:O(1)

• GET最坏情况:O(N) (即单链表查询的时间复杂度)

• 平均:O(1)

• PUT最好情况:O(1)

• PUT最坏情况:O(1) (JDK8前才用头插法,即在单链表头部直接插入，不需要遍历)

• 平均:O(1)

在JDK8之后

当桶内元素元素大于8个，桶内的储存结构会由单链表转化为红黑树。时间复杂度如下

• GET最好情况:O(1)

• GET最坏情况:当桶内元素不大于6个:O(N)(即单链表查询的时间复杂度)，当桶内元素大于8个:O(logN)(红黑树查询的时间复杂度为O(logN)与二分查找类似)

• 平均:O(1)

• PUT最好情况:O(1)

• PUT最坏情况:当桶内元素不大于6个:O(N)(JDK8才用尾插法,遍历到尾部再插入)，当桶内元素大于8个:O(logN)(红黑树插入的时间复杂度为O(logN)与二分插入类似)

• 平均：O(1)

解释

平均复杂O(1),因为哈希碰撞频率实际上不是十分多，即使存在，也比较少出现极端情况。 空间复杂度:O(M)。M为map元素的个数。因为几乎每多一个元素就多一个空间储存，多一个桶或者在桶内多一个位置。

标签：logN,单链,hashmap,复杂度,元素,当桶,情况,put
From： https://www.cnblogs.com/zhengbiyu/p/17233813.html