简介 ArrayList可以说是我们最常用的一种集合了。
他的本质是一个数组,一个可以自动扩容的动态数组 ,线程不安全 ,允许元素为null 。
由于数组的内存连续,可以根据下标以O(1)的时间读写元素,因此时间效率很高。
内部属性 我们先来看下ArrayList里面有哪几个属性:
private static final long serialVersionUID = 8683452581122892189L;
序列话UID。由于ArrayList实现了Serializable接口,为了序列化和反序列化的方便,我们就手动为他添加一个序列化UID。
private static final int DEFAULT_CAPACITY = 10;
默认的容量。
private static final Object[] EMPTY_ELEMENTDATA = {};
空数组。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
默认的空数组。
transient Object[] elementData;
真正存放元素的数组。
private int size;
当前元素个数。
构造方法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 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); } } public ArrayList () { this .elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } public ArrayList (Collection<? extends E> c) { elementData = c.toArray(); if ((size = elementData.length) != 0 ) { if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { this .elementData = EMPTY_ELEMENTDATA; } }
常用API 增 ArrayList # add(E e) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 public boolean add (E e) { ensureCapacityInternal(size + 1 ); elementData[size++] = e; return true ; } private void ensureCapacityInternal (int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 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; int newCapacity = oldCapacity + (oldCapacity >> 1 ); if (newCapacity - minCapacity < 0 ) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0 ) newCapacity = hugeCapacity(minCapacity); elementData = Arrays.copyOf(elementData, newCapacity); } private static int hugeCapacity (int minCapacity) { if (minCapacity < 0 ) throw new OutOfMemoryError (); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }
ArrayList # add(E e) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public void add (int index, E element) { if (index > size || index < 0 ) throw new IndexOutOfBoundsException (outOfBoundsMsg(index)); ensureCapacityInternal(size + 1 ); System.arraycopy(elementData, index, elementData, index + 1 , size - index); elementData[index] = element; size++; }
ArrayList # addAll(Collection<? extends E> c) 1 2 3 4 5 6 7 8 9 10 11 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); size += numNew; return numNew != 0 ; }
ArrayList # addAll(int index, Collection<? extends E> c) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 public boolean addAll (int index, Collection<? extends E> c) { if (index > size || index < 0 ) throw new IndexOutOfBoundsException (outOfBoundsMsg(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 ; }
总结
无论是add还是addAll,都是先判断是否越界,如果越界就扩容,然后再移动数组
如果需要扩容,默认扩容原来的一般大小;如果还不够,那就直接将目标的size作为扩容后的大小
在扩容成功后,会修改modCount
删 ArrayList # remove(int index) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 public E remove (int index) { if (index >= size) throw new IndexOutOfBoundsException (outOfBoundsMsg(index)); modCount++; E oldValue = (E) elementData[index]; int numMoved = size - index - 1 ; if (numMoved > 0 ) System.arraycopy(elementData, index+1 , elementData, index, numMoved); elementData[--size] = null ; return oldValue; }
ArrayList # remove(Object o) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 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) { modCount++; int numMoved = size - index - 1 ; if (numMoved > 0 ) System.arraycopy(elementData, index+1 , elementData, index, numMoved); elementData[--size] = null ; }
ArrayList # removeAll(Collection<?> c) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 public boolean removeAll (Collection<?> c) { Objects.requireNonNull(c); return batchRemove(c, false ); } private boolean batchRemove (Collection<?> c, boolean complement) { final Object[] elementData = this .elementData; int r = 0 , w = 0 ; boolean modified = false ; try { for (; r < size; r++) if (c.contains(elementData[r]) == complement) elementData[w++] = elementData[r]; } finally { if (r != size) { System.arraycopy(elementData, r, elementData, w, size - r); w += size - r; } if (w != size) { for (int i = w; i < size; i++) elementData[i] = null ; modCount += size - w; size = w; modified = true ; } } return modified; }
这块我看的时候有点绕,但是一想通就好了。
其实这个地方是要把C集合中和原集合中共有的元素删除,那我就只需要遍历原数组,然后碰到和C集合相同的元素就直接放到前面去,然后等遍历完成后,一次性把后面的全部置空。
ArrayList # retainAll(Collection<?> c) 1 2 3 4 5 public boolean retainAll (Collection<?> c) { Objects.requireNonNull(c); return batchRemove(c, true ); }
ArrayList # clear() 1 2 3 4 5 6 7 8 9 10 public void clear () { modCount++; for (int i = 0 ; i < size; i++) elementData[i] = null ; size = 0 ; }
总结
改 1 2 3 4 5 6 7 8 9 10 public E set (int index, E element) { if (index >= size) throw new IndexOutOfBoundsException (outOfBoundsMsg(index)); E oldValue = (E) elementData[index]; elementData[index] = element; return oldValue; }
没啥好分析的
不需要修改modCount,相对高效
查 1 2 3 4 5 6 public E get (int index) { if (index >= size) throw new IndexOutOfBoundsException (outOfBoundsMsg(index)); return (E) elementData[index]; }
没啥好分析的
不需要修改modCount,相对高效
包括 contains() & indexOf() 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 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 ; }
没啥好分析的
判空 isEmpty() 1 2 3 public boolean isEmpty () { return size == 0 ; }
没啥好分析的
迭代器 Iterator 创建迭代器 1 2 3 4 public Iterator<E> iterator () { return new Itr (); }
Itr属性 1 2 3 4 5 6 7 8 9 protected int limit = ArrayList.this .size;int cursor; int lastRet = -1 ; int expectedModCount = modCount;
Itr # hasNext() 1 2 3 public boolean hasNext () { return cursor < limit; }
不用多说
Itr # next() 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 public E next () { if (modCount != expectedModCount) throw new ConcurrentModificationException (); int i = cursor; if (i >= limit) throw new NoSuchElementException (); Object[] elementData = ArrayList.this .elementData; if (i >= elementData.length) throw new ConcurrentModificationException (); cursor = i + 1 ; return (E) elementData[lastRet = i]; }
Itr # remove() 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 public void remove () { if (lastRet < 0 ) throw new IllegalStateException (); if (modCount != expectedModCount) throw new ConcurrentModificationException (); try { ArrayList.this .remove(lastRet); cursor = lastRet; lastRet = -1 ; expectedModCount = modCount; limit--; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException (); } }
总结 modCount到底是个什么东西? 如果你看过很多集合源码的话,你就会发现你会在很多地方都会碰到这个modCount,例如ArrayList、LinkedList、HashMap等等。modCount字面意思就是修改次数,那么为什么需要纪录这个修改次数呢?
你回想下,似乎用到modCount的地方,如ArrayList、LinkedList等等,他们都用一个共性——线程不安全。
而在你看了这几个类的迭代器后就会发现,他们迭代器中一定有一个属性(如我们上面的expectedModCount)初始化时的值就是modCount的值。
然后在迭代器的方法中,只要是遍历这个集合的时候,都需要将两个值进行对比,然后再移除元素的时候,都需要更新迭代器里面的modCount变量。
这时,你需要了解下Fail-Fast机制 。
我们都知道这些集合是线程不安全的,如果在使用迭代器的过程中,有其他线程对集合进行了修改,那么就会抛出ConcurrentModificationException异常,这就是Fail-Fast策略。而这个时候源码中就通过modCount进行了操作。迭代器在创建时,会创建一个变量等于当时的modCount,如果在迭代过程中,集合发生了变化,modCount就是++。这时迭代器中的变量的值和modCount不相等了,那就抛异常。
所以,遍历线程不安全的集合时,尽量使用迭代器
解决办法:
在遍历过程中所有涉及到改变 modCount 值得地方全部加上 synchronized 或者直接使用 Collections.synchronizedList,这样就可以解决。但是不推荐,因为增删造成的同步锁可能会阻塞遍历操作。
使用 CopyOnWriteArrayList 来替换 ArrayList。推荐使用该方案。关于CopyOnWriteArrayList的内容此处不再过多的去将,想了解的同学可以百度或者谷歌。
ArrayList和Vector的区别
ArrayList线程不安全,Vector线程安全
扩容的时候ArrayList默认扩容1.5倍,Vector默认扩容1倍