java集结——List

增删改都需要获得锁,获取数组对应index的元素,构造函数,类似于数组下标)来访问List中的元素,List是有序的Collection,通过对象锁对所有访问可变状态的代码进行同步,将可变状态封装在对象内部

图片 1

那篇文章的指标如下:

  • 问询一下ArrayList和CopyOnWriteArrayList的增删改查金玉满堂原理
  • 探访为何说ArrayList查询快而增加和删除慢?
  • CopyOnWriteArrayList为何并发安全且品质比Vector好

第一我们来看看List接口,因为ArrayList和CopyOnWriteArrayList都以落实了List接口,我们今日任重先生而道远是商讨增加和删除改查原理,所以只六柱预测应的法子就可以。

public interface List<E> extends Collection<E> { int size(); boolean isEmpty(); boolean contains; Iterator<E> iterator(); Object[] toArray(); <T> T[] toArray; boolean add; boolean remove; boolean containsAll(Collection<?> c); boolean addAll(Collection<? extends E> c); boolean addAll(int index, Collection<? extends E> c); boolean removeAll(Collection<?> c); boolean retainAll(Collection<?> c); void clear(); boolean equals; int hashCode(); E get(int index); E set(int index, E element); void add(int index, E element); E remove(int index); int indexOf; int lastIndexOf; ListIterator<E> listIterator(); ListIterator<E> listIterator(int index); List<E> subList(int fromIndex, int toIndex);}

ArrayList
是一个动态数组,体量能够动态增加。他是线程不安全的,允许成分为null。它的平底数据结构是数组,所以会占领一块延续的内存空间。它完成了List<E>, RandomAccess, Cloneable, java.io.Serializable
接口。RandomAccess
代表List获取了大肆访谈成效,也正是经过下标获取成分对象的效率。

List是不改变,成分可重新的Collection,完毕List接口的常用类有ArrayList,LinkedList,Vector和Stack。List接口有关的有的UML类图如下:

Vector

public class Vector<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable


2.1 多少个基本点

  • 底层是数组,开始大小为10
  • 插入时会判别数组体量是还是不是丰富,缺乏的话交易会开扩容
  • 所谓扩容正是新建二个新的数组,然后将老的数码之中的成分复制到新的数组里面
  • 移除成分的时候也波及到数组瓜时素的位移,删除钦定index地点的要素,然后将index+1至数组最后贰个成分往前挪动三个格

定义

图片 1

一:自动扩容机制

The Vector class implements a growable array of objects. Like an array,
it contains components that can be accessed using an integer index.
However, the size of a Vector can grow or shrink as needed to
accommodate adding and removing items after the Vector has been created.

  1. 初始化

    底层为目的数组protected Object[] elementData;

    protected int elementCount; 成分个数

    protected int capacityIncrement;拉长个数

        public Vector(int initialCapacity, int capacityIncrement) {
            super();
            if (initialCapacity < 0)
                throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
            this.elementData = new Object[initialCapacity];
            this.capacityIncrement = capacityIncrement;
        }
    
        public Vector(int initialCapacity) {
            this(initialCapacity, 0);
        }
    
        public Vector() {
            this(10);
        }
    
  2. add

    public synchronized boolean add(E e) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = e;
        return true;
    }
    

    认清是还是不是分配

    private void ensureCapacityHelper(int minCapacity) {
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    

    重中之重:capacityIncrement》0时,每回增加capacityIncrement个成分;

    ​ capacityIncrement《=0时,2倍扩增;

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    
  3. remove: 并不会调护医治底层数组的高低

    public synchronized E remove(int index) {
        modCount++;
        if (index >= elementCount)
            throw new ArrayIndexOutOfBoundsException(index);
        E oldValue = elementData(index);
    
        int numMoved = elementCount - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--elementCount] = null; // Let gc do its work
    
        return oldValue;
    }
    

    clear实现

    public synchronized void removeAllElements() {
        modCount++;
        // Let gc do its work
        for (int i = 0; i < elementCount; i++)
            elementData[i] = null;
    
        elementCount = 0;
    }
    

    真正收缩底层数组体积

    public synchronized void trimToSize() {
        modCount++;
        int oldCapacity = elementData.length;
        if (elementCount < oldCapacity) {
            elementData = Arrays.copyOf(elementData, elementCount);
        }
    }
    

2.2 增加和删除改查

1)增

 public boolean add { //进行数组容量判断,不够就扩容 ensureCapacityInternal; // Increments modCount!! elementData[size++] = e; return true; } public void add(int index, E element) { //检查是否会越界 rangeCheckForAdd; //进行数组容量判断,不够就扩容 ensureCapacityInternal; // Increments modCount!! //将index至数据最后一个元素整体往后移动一格,然后插入新的元素 System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++;}

2)删

public E remove(int index) { //判断是否越界 rangeCheck; modCount++; E oldValue = elementData; int numMoved = size - index - 1; //若该元素不是最后一个元素的话,将index+1至数组最后一个元素整体向前移动一格 if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work return oldValue; }

3)改

 public E set(int index, E element) { rangeCheck; E oldValue = elementData; elementData[index] = element; return oldValue;}

逻辑很粗大略,将数组对应index的因素实行轮换

4)查

public E get(int index) { rangeCheck; return elementData;}E elementData(int index) {return  elementData[index]; }

逻辑非常粗略,实行数组越界剖断,获取数组对应index的因素

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable

List是雷打不动的Collection,使用此接口能够准确的支配每种成分插入的职责。客商能够使用索引(成分在List中的地点,类似于数组下标)来拜谒List中的成分,那类似于Java的数组。

二:线程安全

jdk1.0 Vector ,jdk1.2 ArrayList

Vector
将可变状态封装在对象内部,通过对象锁对具有访谈可变状态的代码实行协同,使得在该目的上不会产生并发访谈。

相比ArrayList能够窥见,增加和删除改查全数办法都加了synchronized 关键字。

    public synchronized int size() {
        return elementCount;
    }