ArrayList源码分析
一、核心变量 // 序列化ID private static final long serialVersionUID = 8683452581122892189L; // 默认初始化容量 private static final int DEFAULT_CAPACITY = 10; // 空数组 private static final Object[] EMPTY_ELEMENTDATA = {}; // 空数组 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 存储数据元素的数组 transient Object[] elementData; // non-private to simplify nested class access // 当前arraylist集合的大小，也就是elementData数组中数据元素的个数 private int size; 二、构造函数 /** * 一：无参构造方法 */ public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } /** * 二：携带一个int类型的参数，指定arraylist的初始容量 */ public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } } 1、无参构造 可以看到，在构造方法中直接将 elementData 指向 DEFAULTCAPACITY_EMPTY_ELEMENTDATA空数组，这个时候该ArrayList的size为初始值0。 1、有参构造 进行参数校验： 参数大于0，则指定数组长度； 参数等于0，则为空数组； 参数小于0，则抛异常。 三、add方法 /** * 一：直接添加数据元素到arraylist的尾部 */ public boolean add(E e) { //是否扩容、记录modCount ensureCapacityInternal(size + 1); // Increments modCount!! //把值添加到数组尾部 elementData[size++] = e; return true; } ---------------------------------------------------------------------- private void ensureCapacityInternal(int minCapacity) { //minCapacity=size+1； //minCapacity表示如果添加成功后，数组的最小长度 //如果为无参构造 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { //取默认长度和minCapacity的最大值，即10 minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } //是否扩容 ensureExplicitCapacity(minCapacity); } ---------------------------------------------------------------------- private void ensureExplicitCapacity(int minCapacity) { modCount++; // 如果添加后最小长度大于 数组长度 if (minCapacity - elementData.length > 0) //扩容 grow(minCapacity); } ---------------------------------------------------------------------- private void grow(int minCapacity) { //获取数组长度 int oldCapacity = elementData.length; //1.5倍扩容 int newCapacity = oldCapacity + (oldCapacity >> 1); //1.5倍扩容也不够用 if (newCapacity - minCapacity < 0) //扩容后长度=minCapacity newCapacity = minCapacity; //简直最大长度 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // 复制 elementData = Arrays.copyOf(elementData, newCapacity); } 代码中已经有注释了，很清晰。 四、remove方法 /* * 一：根据角标进行remove操作 */ public E remove(int index) { // 1. 对角标越界进行判断 if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); // 2.modCount自增1 modCount++; // 3.获取到指定下角标位置的数据 E oldValue = (E) elementData[index]; // 4.计算需要移动的元素个数 int numMoved = size - index - 1; if (numMoved > 0) // 5. 指定角标位置后的元素前移一位，效率低 System.arraycopy(elementData, index+1, elementData, index, numMoved); // 6.将size自减1，并将数组末尾置为null，便于垃圾回收 elementData[--size] = null; // clear to let GC do its work // 7.最后将所要删除的数据元素return掉 return oldValue; } /* * 二：根据数据元素进行remove操作 */ public boolean remove(Object o) { if (o == 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])) { fastRemove(index); return true; } } return false; } ---------------------------------------------------------------------- private void fastRemove(int index) { // 1.modCount的值自增1 modCount++; // 2.计算需要移动的元素个数 int numMoved = size - index - 1; if (numMoved > 0) // 3. 指定角标位置后的元素前移一位 System.arraycopy(elementData, index+1, elementData, index, numMoved); // 4.将size自减1，并将数组末尾置为null，便于垃圾回收 elementData[--size] = null; // clear to let GC do its work } 五、set方法 public void set(E e) { if (lastRet < 0) throw new IllegalStateException(); //检查modCount checkForComodification(); try { ArrayList.this.set(lastRet, e); } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } ---------------------------------------------------------------------- public E set(int index, E element) { rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; return oldValue; } ---------------------------------------------------------------------- final void checkForComodification() { if (expectedModCount != ArrayList.this.modCount) throw new ConcurrentModificationException(); } 六、get方法 public E get(int index) { rangeCheck(index); checkForComodification(); return ArrayList.this.elementData(offset + index); } ---------------------------------------------------------------------- E elementData(int index) { return (E) elementData[index]; } 七、clear方法 public void clear() { modCount++; // clear to let GC do its work for (int i = 0; i < size; i++) elementData[i] = null; size = 0; } 八、contains方法 public boolean contains(Object o) { return indexOf(o) >= 0; } ---------------------------------------------------------------------- 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])) return i; } return -1; } 未命名文件.jpg 九、fail-fast机制 ail-fast机制是集合中的一种错误检测机制，我们在操作集合中经常会遇到 java.util.ConcurrentModificationException异常，产生该异常的原因就是fail-fast机制。 实现：如果在迭代期间计数器被修改，那么hasNext或next将抛出concurrentModificationException 缺点：这种检查是没有同步的情况下进行的，因此可能会看到失效的计数值，而迭代器可能并没有意识到已经发生了修改。这是一种设计上的权衡，从而降低了并发修改操作的检测代码对程序性能带来的影响。 十、可能的并发问题 add() EX：a、100个元素，可能最后数组长度不到100。 两个线程并发add，对索引位置5的地方几乎同时赋值，第二个线程会覆盖第一个线程的值，并且size少了1个。 b、假设有两个线程在操作同一个ArrayList，线程一执行step1(容量足够)后被挂起，线程二执行add()方法后，线程一被唤醒，这时线程一因为已经不再判断容量是否足够（已经判断过），执行step2就会出现数组越界 数组容量检测的并发问题 remove 两个线程有可能会想要删除同一个内容，一个线程先完成的时候第二个线程再删，就找不到这个内容了
