数据结构---ArrayList源码分析

数据结构---ArrayList源码分析

1.线程不安全 — ArrayList操作做改变位置和操作元素，在多线程环境下不能保证原子性 （原子性操作：原子性在一个操作是不可中断的，要么全部执行成功要么全部执行失败， 有着“同生共死”的感觉。及时在多个线程一起执行的时候， 一个操作一旦开始，就不会被其他线程所干扰。）

2.属性分析

a. 默认初始化容量 – ​​DEFAULT_CAPACITY = 10​​​ b. 可分配的最大容量 – ​​MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8​​ c. ArrayList底层数组 – ​​transient Object[] elementData;​​（transient 在已经实现序列化的类中，不允许某变量序列化，反序列化后该变量为空值）

ArrayList在序列化的时候会调用​​writeObject()​​​方法，将​​size​​​和​​element​​​写入​​ObjectOutputStream​​​； 反序列化时调用​​​readObject()​​​，从​​ObjectInputStream​​​获取​​size​​​和​​element​​​，再恢复到​​elementData​​。

问题二：为什么不直接用elementData来序列化，而采用上诉的方式来实现序列化呢？

elementData是一个缓存数组，它通常会预留一些容量， 等容量不足时再扩充容量，那么有些空间可能就没有实际存储元素， 采用上诉的方式来实现序列化时，就可以保证只序列化实际存储的那些元素， 而不是整个数组，从而节省空间和时间。

3.构造方法

有参构造（传数组大小）

public ArrayList(int initialCapacity) { if (initialCapacity > 0) { 如果传进来的参数>0 则构造指定大小的数组 this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { 如果传进来的参数=0 则构造一个空数组 this.elementData = EMPTY_ELEMENTDATA; } else { 否则抛异常 throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } }

无参构造

public ArrayList() { //默认构造一个容量为10的数组 this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }

有参构造 传入一个集合

public ArrayList(Collection c) { elementData = c.toArray();//先将集合转为数组形式 if ((size = elementData.length) != 0) { //判断数组长度 // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class) //动态扩容 将参数数组放入底层数组并且动态扩容 elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; } }

4.主要方法

将数组大小调整为当前元素所占用数组的实际大小。

public void trimToSize() { modCount++; if (size < elementData.length) { elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); } }

在数组末尾添加元素

public boolean add(E e) { // 首先调用了ensureCapacityInternal()方法.注意参数是size+1,判断数组容量是否已满，已满就扩容1.5倍（默认） ensureCapacityInternal(size + 1); elementData[size++] = e; return true; }

上边的详解

private void ensureCapacityInternal(int minCapacity) { //计算数组容量， int n = calculateCapacity(elementData, minCapacity); //判断数组是否已满，看是否需要扩容 ensureExplicitCapacity(); } //计算数组容量：如果elementData是空，则返回默认容量10和size+1的最大值，否则返回size+1 private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; } //判断是否需要扩容 private void ensureExplicitCapacity(int minCapacity) { modCount++; // size+1 > elementData.length证明数组已经放满，则增加容量，调用grow() if (minCapacity - elementData.length > 0) grow(minCapacity);//扩容方法 } //数组扩容 private void grow(int minCapacity) { // 获取当前数组长度=>oldCapacity int oldCapacity = elementData.length; // oldCapacity>>1 表示将oldCapacity右移一位(位运算)，相当于除2。再加上1，相当于新容量扩容1.5倍 int newCapacity = oldCapacity + (oldCapacity >> 1); // 如果newCapacity>1=1,1<2所以如果不处理该情况，扩容将不能正确完成 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; // 如果新容量比最大值还要大，则将新容量赋值为VM要求最大值 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // 将elementData拷贝到一个新的容量中 elementData = Arrays.copyOf(elementData, newCapacity); } // 判断新容量比最大值是否要大，大则返回整形的最大值 private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }

指定位置添加指定元素

public void add(int index, E element) { rangeCheckForAdd(index);//数组越界检查 ensureCapacityInternal(size + 1); // Increments modCount!!//检查数组容量和判断扩容 System.arraycopy(elementData, index, elementData, index + 1,//添加的实际操作方法 size - index); elementData[index] = element; size++; } //是一个本地方法 public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);参数情况：Object src : 原数组int srcPos : 从元数据的起始位置开始Object dest : 目标数组int destPos : 目标数组的开始起始位置int length :

数组越界检查

private void rangeCheckForAdd(int index) { if (index > size || index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }

在指定位置设值

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

返回指定元素的下标

public int indexOf(Object o) { if (o == null) { //可见数组可以放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])) return i; } return -1; }

获取指定下标元素

public E get(int index) { rangeCheck(index);// 检测index是否合法 return elementData(index); }

删除制定下标元素

public E remove(int index) { // 检测index是否合法 rangeCheck(index); // 数据结构修改次数 modCount++; E oldValue = elementData(index); // 记住这个算法 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 return oldValue; }

ArrayList优缺点优点：

1.因为其底层是数组，所以修改和查询效率高。

2.可自动扩容(1.5倍)。

缺点：

1.插入和删除效率不高。

2.线程不安全。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。