首页 > 代码库 > java集合-ArrayList
java集合-ArrayList
一直要总结java集合中的知识,不知道应该如何下笔。觉得集合太多东西了,写细了太难了,写粗了又感觉写不好。不管如何觉得还是要坚持的写一写基础这一类的东西,为了提高自己的编程基础。本来觉的自己对这些已经很熟悉,最近见过一些大神后发现差距太大了,瞬间懵了,只能在加强学习了。
一、ArrayList是什么?
ArrayList是实现List接口的动态数组,所谓动态是指它的大小是可变的。实现了所有可选列表操作,并允许包括 null 在内的所有元素。除了实现 List 接口外,此类还提供一些方法来操作内部用来存储列表的数组的大小。
既然是数组,肯定就有容量。每个ArrayList对象都有一个容量,该容量是用来表示可以存放多少个数据在里面,即是数组的大小(默认是10)。当然,动态的肯定就会自动增加,每次我们往里面添加数据的时候,它都会进行扩容检查,检查完扩容会扩大为原来的1.5倍,扩容操作带来数据向新数组的重新拷贝,影响性能,所以如果我们知道具体业务数据量,在构造ArrayList时可以给ArrayList指定一个初始容量,这样就会减少扩容时数据的拷贝问题。当然在添加大量元素前,应用程序也可以使用ensureCapacity操作来增加ArrayList实例的容量,这可以减少递增式再分配的数量。
ArrayList的底层实现是不同步,多线程操作会出现问题,这一点大家要注意。可以插入重复数据,可以插入Null。
二、ArrayList源码分析
2.1、ArrayList定义
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
ArrayList的定义,继承AbstractList,实现List<E>, RandomAccess, Cloneable, java.io.Serializable,其中AbstractList实现了 List 的一些位置相关操作(比如 get,set,add,remove),是第一个实现随机访问方法的集合类,但不支持添加和替换。RandomAccess代表该类是否支持 随机访问,Cloneable类支持克隆,Serializable支持序列化。
2.2、底层使用数组
private static final long serialVersionUID = 8683452581122892189L;//serialVersionUID作用是序列化时保持版本的兼容性,即在版本升级时反序列化仍保持对象的唯一性。
private transient Object[] elementData;//Object数组,transient关键字不知道的同学自己查资料去,带transient关键字的变量不会序列化。ArrayList容器,基本操作都是基于该数组进行操作的。
private int size;//数组的大小。
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;//要分配的数组的最大大小。
2.3、构造函数
ArrayList有三个构造函数:
ArrayList():默认构造函数,提供初始容量为10的空列表。
ArrayList(int initialCapacity):构造一个具有指定初始容量的空列表。
ArrayList(Collection<? extends E> c):构造一个包含指定 collection 的元素的列表,这些元素是按照该 collection 的迭代器返回它们的顺序排列的。
/** * 构造具有指定初始容量的空列表。. * * @param 初始容量列表的初始容量 * @throws IllegalArgumentException 如果指定的初始容量为负会抛出非法异常。 */ public ArrayList(int initialCapacity) { super(); if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); this.elementData = http://www.mamicode.com/new Object[initialCapacity]; } /** * 构建一个初始容量为十的空列表. */ public ArrayList() { this(10); } /** * 构造包含指定元素的列表。 * 集合,按集合返回的顺序 * 迭代器 * * @param c的集合,其元素将放在这个列表中。 * @throws NullPointerException 如果指定的集合为null为抛出这个空指针异常。 */ public ArrayList(Collection<? extends E> c) { elementData = c.toArray();//如果为空,这里会抛异常 size = elementData.length; // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); }
2.4、add方法
ArrayList提供了add(E e)、add(int index, E element)、addAll(Collection<? extends E> c)、addAll(int index, Collection<? extends E> c)、set(int index, E element)这个五个方法来实现ArrayList增加。
我就拿一个来讲了,懂的一个,其他应该都懂了。
public boolean add(E e) { ensureCapacityInternal(size + 1); //增加操作次数 elementData[size++] = e;//把值放到最后一位 return true; } private void ensureCapacityInternal(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0)//如果数组真实存储大于数组容量就增加 grow(minCapacity); } private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length;//原来的容量 int newCapacity = oldCapacity + (oldCapacity >> 1);//新的容量为旧的1.5倍 if (newCapacity - minCapacity < 0)//增加了还小就按真实的来 newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0)//如果比最大还大 newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData =http://www.mamicode.com/ Arrays.copyOf(elementData, newCapacity);//复制数组 } private static int hugeCapacity(int minCapacity) {//注意是个静态方法 if (minCapacity < 0) // overflow 小于0,抛异常 throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ?//大于MAX_ARRAY_SIZE就设置为MAX_VALUE,否则就MAX_ARRAY_SIZE Integer.MAX_VALUE : MAX_ARRAY_SIZE;}
2.5、remove方法
ArrayList提供了remove(int index)、remove(Object o)、removeRange(int fromIndex, int toIndex)、removeAll()四个方法进行元素的删除。
remove(int index):移除此列表中指定位置上的元素。
public E remove(int index) {//根据下标删除 rangeCheck(index);//检查是否越界 modCount++;//操作增加 E oldValue = http://www.mamicode.com/elementData(index);//获得下标的值 int numMoved = size - index - 1;//要移动的数据 if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved);//数组往前移 elementData[--size] = null; // 让GC工作 return oldValue;//返回旧值 } private void rangeCheck(int index) {//检查越界 if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } private String outOfBoundsMsg(int index) {//是不是感觉经常空间这个,哈哈 return "Index: "+index+", Size: "+size; } @SuppressWarnings("unchecked") E elementData(int index) { return (E) elementData[index]; }
remove(Object o):如果存在移除此列表中首次出现的指定元素。
public boolean remove(Object o) { if (o == null) {//如果为null for (int index = 0; index < size; index++) if (elementData[index] == null) {//==来比较 fastRemove(index); return true;//存在并删除返回true } } else {//如果不为null for (int index = 0; index < size; index++) if (o.equals(elementData[index])) {//equals来比较 fastRemove(index);//存在并删除返回true return true; } } return false;//不存在返回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; // Let gc do its work }
2.6、get方法
public E get(int index) { rangeCheck(index);//检查是否越界 return elementData(index);//取值 }
2.7、注意subList方法
public static void main(String[] args) { List<Integer> list1 = new ArrayList<Integer>(); list1.add(1); list1.add(2); // 通过构造函数新建一个包含list1的列表 list2 List<Integer> list2 = new ArrayList<Integer>(list1); // 通过subList生成一个与list1一样的列表 list3 List<Integer> list3 = list1.subList(0, list1.size()); // 修改list3 list3.add(3); System.out.println(list1.size()); System.out.println("list1 == list2:" + list1.equals(list2)); System.out.println("list1 == list3:" + list1.equals(list3)); }
上面一段代码我感觉大部人都会认为结果是2个false,list2是新构造的肯定与list1不一样,list3是截取的肯定也不一样。所以会认为都是false,我们深入subList去看看。
public List<E> subList(int fromIndex, int toIndex) { subListRangeCheck(fromIndex, toIndex, size);//检查下标和大小 return new SubList(this, 0, fromIndex, toIndex);//新创建一个SubList对象,注意传入的是this,代表了要截取的对象}private class SubList extends AbstractList<E> implements RandomAccess {//我擦,跟list差不多的感觉private final AbstractList<E> parent;private final int parentOffset;private final int offset;int size;//我擦,熟悉的感觉SubList(AbstractList<E> parent,int offset, int fromIndex, int toIndex) {//刚刚的构造 this.parent = parent;//this.parent = parent;而parent就是在前面传递过来的list,也就是说this.parent就是原始list的引用。 this.parentOffset = fromIndex; this.offset = offset + fromIndex; this.size = toIndex - fromIndex; this.modCount = ArrayList.this.modCount;//操作数也是跟原来的一样}
原来sublist里面操作的是原来的list,并没有生成新的list,导致2个其实是一样的。
所以上面正确的结果是:
list1 == list2:false
list1 == list3:true
三、ArrayList总结
因为它是基于数组实现的,主要有如下特点:
1、插入、删除比较慢,因为插入、删除需要移动数据位置。
2、可以重复插入数据、可以插入null。
3、查找比较快,可以直接使用下标。
java集合-ArrayList