By zxy

更新日期:

文章目录
  1. 1. 1.总述
  2. 2. 2.Iterator
    1. 2.0.1. (1).访问方式：
    2. 2.0.2. (2).fail-fast
  • 3. 3.List
  • 4. 4.Set：不包括重复的元素， 其实Set的实现原理是基于Map上面的
  • 5. 5.Queue:队列先进先出，类似排队,是双端队列
  • 6. 5.Map:映射表,键必须唯一

    • 1.总述

    简单的容器分类图

    • Iterator:遍历并选择序列中的对象，只可以向后遍历的迭代器（ListIterator extends Iterator 可以前后遍历）
      只有三个方法：
      hasNext()：判断有没有元素
      next()：取出下一个,到达集合末尾抛出异常
      remove()：将迭代器新近返回的元素在原列表中删除，所以在使用remove()方法前必须使用next().
    • Collection:继承接口Iterator,存放一组对象的方式(AbstractCollection size()和iterator()是抽象方法，其他的都实例化)
      size()
      isEmpty()
      contains()
      containsAll()
      retainAll(Collection<?> other)删除与other不同的元素，成功返回true
      add()
      addAll()
      remove()
      removeAll()
      clear()
      hashCode()
      iterator()
      toArray()
    • Map:一组成对的“键值对”对象，可根据键的值来查找对象

    2.Iterator

    (1).访问方式：
        顺序的，比如：ArrayList,Iterator从0开始，next()一次，向后移动一个，
        将其认为是在两个元素中间，next()一次，就越过一个元素，返回刚刚越过的元素的引用；
     每次调用remove()之前要调用next(),否则会抛出异常，remove()一次，删除左边的元素。
     若是ListIterator，previous()就向前移动一个，返回刚刚越过的元素，即右边的元素，删除时也是右边
非顺序的，set,元素会按照某种随机的次序出现，next()一次，就随机返回一个。
    (2).fail-fast
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    public E next() {
               checkForComodification();
               int i = cursor;
               if (i >= size)
                   throw new NoSuchElementException();
               Object[] elementData = ArrayList.this.elementData;
               if (i >= elementData.length)
                   throw new ConcurrentModificationException();
               cursor = i + 1;
               return (E) elementData[lastRet = i];
           }
    final void checkForComodification() {
               if (modCount != expectedModCount)
                   throw new ConcurrentModificationException();
           }

    迭代器在调用next()和remove()方法时都调用了checkForComodification()，检查在迭代进行时，容器有没有发生结构性的改变
    checkForComodification()检测 modCount != expectedModCount ? 若不等则抛出ConcurrentModificationException 异常，从而产生fail-fast机制
    AbtractList
    protected transient int modCount = 0;
    modCount: The number of times this list has been structurally modified.
    Structural modifications are those that change the size of the list,
    or otherwise perturb it in such a fashion that iterations in progress may yield incorrect results.
    ArrayList
    expectedModCount = modCount
    如果迭代器在迭代时发现容器发生了结构性的变化，不包括set()，就会抛出fail-fast

    3.List

    (1).ArrayList：内部是通过数组实现的，一般用于对元素进行快速随机访问,时间复杂度为O(1),删除添加O(n)
    数组的缺点是每个元素之间不能有间隔，当数组大小不满足时需要增加存储能力，
    要把已经有数组的数据复制到新的存储空间(大小为*1.5+1)中。
    (2).LinkedList：内部是通过循环链表实现的，很适合数据的动态插入和删除，时间复杂度为O(1)，访问为O(n)除了第一个元素和最后一个元素（O(1)）
    缺点是随机访问比较慢，要从头进行遍历
    (3).同步：

    • vector和arrayList一样，是使用数组实现，但是vector是线程安全的（sychronized）
      vector扩容int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);capacityIncrement为扩容因子
    • 同步包装器，List users1 = Collections.synchronizedList(new ArrayList())等
    • java.util.concurrent.*,一般使用，但是CopyOnWriteArrayList效率没有同步包装器好

    4.Set：不包括重复的元素， 其实Set的实现原理是基于Map上面的

    (1).hashSet：存放顺序和添加进去时候的顺序没有任何关系，
    就是建立一个“键值对”，“键”就是我们要存入的对象，“值”则是一个常量。这样可以确保， 我们所需要的存储的信息之是“键”
    return map.put(e, PRESENT)==null;
    (1).treeSet：对我们的Set中的元素进行排序存放
    (2).LinkedHashSet：则保持元素的添加顺序

    5.Queue:队列先进先出，类似排队,是双端队列

    出错是要报错的
    offer()添加，满了报错
    peek()弹出，不删除，空了报错
    poll()弹出，删除，空了报错
    (1).PriorityQueue：使用小根堆实现，最小的在上面

    5.Map:映射表,键必须唯一

    (1).HashMap：对键进行hashCode(),以此来寻找和添加，
    (2).TreeMap：排序，使用键的顺序对元素进行排序，比如搜索树
    (3).WeakHashMap：使用弱引用保存键，如果某个对象那个只被key引用，垃圾收集器仍然回收

    文章目录
    1. 1. 1.总述
    2. 2. 2.Iterator
      1. 2.0.1. (1).访问方式：
      2. 2.0.2. (2).fail-fast
  • 3. 3.List
  • 4. 4.Set：不包括重复的元素， 其实Set的实现原理是基于Map上面的
  • 5. 5.Queue:队列先进先出，类似排队,是双端队列
  • 6. 5.Map:映射表,键必须唯一