ArrayList、Vector

ArrayList和Vector都是有序的数组集合,内部是数组的实现。

一、ArrayList

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

1、核心结构

Object[] elementData；//存储列表元素的数组 int size； //数组中有效元素的个数

2、增、删、改、查

2.1、增加元素

public boolean add(E e) { ensureCapacityInternal(size + 1); //检查是否需要增加数组的容量 elementData[size++] = e; //设置元素 return true; } public void add(int index, E element) { rangeCheckForAdd(index); //检查数组下标是否越界 ensureCapacityInternal(size + 1); //检查是否需要增加数组的容量 System.arraycopy(elementData, index, elementData, index + 1,size - index); //移动数组 elementData[index] = element; //设置元素 size++; } public boolean addAll(Collection<? extends E> c) { Object[] a = c.toArray(); //转换为数组 int numNew = a.length; ensureCapacityInternal(size + numNew); // 检查是否需要增加数组的容量 System.arraycopy(a, 0, elementData, size, numNew);//将collection中的元素拷贝到list中 size += numNew; return numNew != 0; } public boolean addAll(int index, Collection<? extends E> c) { rangeCheckForAdd(index); //检查数组下标是否越界 Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); // 检查是否需要增加数组的容量 int numMoved = size - index; if (numMoved > 0) System.arraycopy(elementData, index, elementData, index + numNew, numMoved); System.arraycopy(a, 0, elementData, index, numNew); size += numNew; return numNew != 0; }

2.2、删除元素

public E remove(int index) { rangeCheck(index); //检查数组下标是否越界 E oldValue = elementData(index); //移除的元素值 fastRemove(index); // return oldValue; } public boolean remove(Object o) { if (o == null) { //null元素 for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; } } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { //通过equals判断元素是否相等 fastRemove(index); return true; } } return false; } private void fastRemove(int index) { modCount++; int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work } public void clear() { modCount++; // clear to let GC do its work for (int i = 0; i < size; i++) elementData[i] = null; size = 0; } 2.3、更换元素

public E set(int index, E element) { rangeCheck(index); //检查数组下标是否越界 E oldValue = elementData(index); elementData[index] = element; //替换元素 return oldValue; } 2.4、查询元素

public int indexOf(Object o) { if (o == null) { for (int i = 0; i < size; i++) if (elementData[i]==null) return i; } else { for (int i = 0; i < size; i++) if (o.equals(elementData[i])) //使用equals判断 return i; } return -1; } public int lastIndexOf(Object o) { if (o == null) { for (int i = size-1; i >= 0; i--) if (elementData[i]==null) return i; } else { for (int i = size-1; i >= 0; i--) //倒序查询 if (o.equals(elementData[i])) return i; } return -1; } public E get(int index) { rangeCheck(index); return elementData(index); } public boolean contains(Object o) { return indexOf(o) >= 0; } @SuppressWarnings("unchecked") E elementData(int index) { return (E) elementData[index]; }

3、多线程下使用ArrayList

ArrayList是非线程安全的,因此在多线程环境中操作ArrayList要加同步机制。

3.1、Collections.synchronizedList(list); 将ArrayList包装成SynchronizedList.

static class SynchronizedList<E> extends SynchronizedCollection<E> implements List<E> { private static final long serialVersionUID = -7754090372962971524L; final List<E> list; SynchronizedList(List<E> list) { super(list); this.list = list; } SynchronizedList(List<E> list, Object mutex) { super(list, mutex); this.list = list; } //读取 public E get(int index) { synchronized (mutex) {return list.get(index);} } //设值 public E set(int index, E element) { synchronized (mutex) {return list.set(index, element);} } //添加 public void add(int index, E element) { synchronized (mutex) {list.add(index, element);} } //删除 public E remove(int index) { synchronized (mutex) {return list.remove(index);} } 不管是读取还是修改，都加了同步锁。所以性能比较低。

3.2、CopyOnWriteArrayList

核心结构：

final transient ReentrantLock lock = new ReentrantLock();//同步锁，只在add、remove时需要添加锁机制，读不需要同步 private transient volatile Object[] array; //数组容器，容器中的都是实际存放的元素,即array.length=size();

//添加元素 ,同步添加元素操作，保证数组中元素顺序的正确性 public boolean add(E e) { final ReentrantLock lock = this.lock; lock.lock(); try { Object[] elements = getArray(); int len = elements.length; Object[] newElements = Arrays.copyOf(elements, len + 1); //复制一个新数组，先将元素添加到副本数组中，不影响原来的数组容器 newElements[len] = e;//设置元素 setArray(newElements);//将原容器的引用指向新的容器, 即array = newElements; return true; } finally { lock.unlock(); } } //读取元素 public E get(int index) { return array[index]; } 注意：CopyOnWriteList的性能要高于Collections.synchronizedList(list)

4、迭代时修改结构

//1.错误的处理方式，导致循环时获取的元素不正确 for (int i = 0; i < list.size(); i++) { System.out.println(list.get(i)); if (list.get(i).equals("1")) { list.remove("1"); } } // 2、通过迭代器添加或删除元素 ListIterator<String> listIterator = list.listIterator(); while (listIterator.hasNext()) { String item = listIterator.next(); if (item.equals("1")) { listIterator.remove(); } }

二、Vector

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

1、核心结构

protected Object[] elementData; //数组容器 protected int elementCount; //有效元素个数 protected int capacityIncrement; //当容器满时，容器自动增加的量

2、Vector是线程安全的

增删改查方法都使用了synchronized关键字

3、从JDK1.0开始有的类，ArrayList是JDK1.2开始有的类.