首页 > 其他 > 详细

集合扩容

时间:2020-10-18 12:33:40      阅读:0      评论:0      收藏:0      [点我收藏+]

                                      技术分享图片

 

Map

  HashMap

    HashMap的初始容量为16。 扩容因子 默认 0.75 , 可以改。 扩容时是当前容量翻倍即:capacity*2。  查询效率 jdk 1.7 为 O(N), jdk 1.8 为 O(lgN)

  HashTable

    初始容量为11。扩容因子 默认 0.75 , 可以改。扩容时是容量翻倍+1即:capacity*2+1。

  ConcurrentHashMap

    初始容量为16。 扩容因子 默认 0.75 , 不可以改。 扩容时是当前容量翻倍即:capacity*2

List

  Arraylist 

    线程不安全。 初始容量是10。 扩容倍数是 1.5 + 1, 即初始为10, 扩容后为16。 

  Vector

    线程安全。 初始容量为10,一次扩容后容量为20

Set

  HashSet

    线程不安全,存取速度快。初始容量为16, 加载因子为0.75

  TreeSet

    线程不安全, 底层是红黑树

  EnumSet

    线程不安全

        HashSet的性能总是比TreeSet好(特别是最常用的添加、查询元素等操作),因为TreeSet需要额外的红黑树算法来维护集合元素的次序。只有当需要一个保持排序的Set时,使用TreeSet,其他情况都应该使用HashSet。

 

ArrayList 和 LinkedList 时间复杂度

      技术分享图片

 

 

        注: 1、在 add(index, E) 中,ArrayList 和 LinkedList 的 查询时间复杂性 和 插入时间复杂度的区别

      2、在 remove(index, E) 中,ArrayList 和 LinkedList 的 查询时间复杂性 和 插入时间复杂度的区别

     3、get(index), ArrayList 和 LinkedList 的 查询时间复杂性

 

 

  ArrayList 是线性表(数组)
  get() 直接读取第几个下标,复杂度 O(1)
  add(E) 添加元素,直接在后面添加,复杂度O(1)
  add(index, E) 添加元素,在第几个元素后面插入,后面的元素需要向后移动,复杂度O(n)
  remove()删除元素,后面的元素需要逐个移动,复杂度O(n)

  LinkedList 是链表的操作
  get() 获取第几个元素,依次遍历,复杂度O(n)
  add(E) 添加到末尾,复杂度O(1)
  add(index, E) 添加第几个元素后,需要先查找到第几个元素,直接指针指向操作,复杂度O(n)
  remove()删除元素,直接指针指向操作,复杂度O(1)

集合扩容

原文:https://www.cnblogs.com/grtse/p/13833565.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号