[关闭]
@pastqing 2016-04-14T05:27:03.000000Z 字数 6817 阅读 1597

Java集合框架——List(一)

java java-collection-framwork


一、ArrayList源码分析(JDK7)

ArrayList内部维护了一个动态的Object数组,ArrayList的动态增删就是对这个对组的动态的增加和删除。

1、ArrayList构造以及初始化

  1. //ArrayList默认容量
  2. private static final int DEFAULT_CAPACITY = 10;
  3. //默认空的Object数组, 用于定义空的ArrayList
  4. private static final Object[] EMPTY_ELEMENTDATA = {};
  5. //ArrayList存放存放元素的Object数组
  6. private transient Object[] elementData;
  7. //ArrayList中元素的数量
  8. private int size;

2、ArrayList的容量分配机制

  1. private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
  1. public boolean add(E e) {
  2. ensureCapacityInternal(size + 1); // Increments modCount!!
  3. elementData[size++] = e;
  4. return true;
  5. }

ensureCapacityInternal(int)方法实际上确定一个最小扩容大小。

  1. private void ensureCapacityInternal(int minCapacity) {
  2. if (elementData == EMPTY_ELEMENTDATA) {
  3. minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
  4. }
  5. ensureExplicitCapacity(minCapacity);
  6. }
  1. private void ensureExplicitCapacity(int minCapacity) {
  2. modCount++;
  3. // overflow-conscious code
  4. if (minCapacity - elementData.length > 0)
  5. grow(minCapacity);
  6. }
  1. This field is used by the iterator and list iterator implementation returned by the iterator and listIterator methods.
  2. If the value of this field changes unexpectedly, the iterator (or list iterator) will throw a ConcurrentModificationException in response to the next, remove, previous, set or add operations.
  3. This provides fail-fast behavior, rather than non-deterministic behavior in the face of concurrent modification during iteration.
  1. private void grow(int minCapacity) {
  2. // overflow-conscious code
  3. int oldCapacity = elementData.length;
  4. int newCapacity = oldCapacity + (oldCapacity >> 1);
  5. if (newCapacity - minCapacity < 0)
  6. newCapacity = minCapacity;
  7. if (newCapacity - MAX_ARRAY_SIZE > 0)
  8. newCapacity = hugeCapacity(minCapacity);
  9. // minCapacity is usually close to size, so this is a win:
  10. elementData = Arrays.copyOf(elementData, newCapacity);
  11. }

其中对大容量扩容多少还有个hugeCapacity方法

  1. private static int hugeCapacity(int minCapacity) {
  2. if (minCapacity < 0) // overflow
  3. throw new OutOfMemoryError();
  4. return (minCapacity > MAX_ARRAY_SIZE) ?
  5. Integer.MAX_VALUE :
  6. MAX_ARRAY_SIZE;
  7. }

二、ArrayList迭代器

ArrayList的迭代器主要有两种ItrListItr, 但是在jDK1.8中还添加了一个ArrayListSpliterator, 下面分别学一下ItrListItr的源码分析。

1、Itr:只能向后遍历

  1. private class Itr implements Iterator<E> {
  2. int cursor; // index of next element to return
  3. int lastRet = -1; // index of last element returned; -1 if no such
  4. //expectedModCount 是modCount的一个副本
  5. int expectedModCount = modCount;
  6. public boolean hasNext() {
  7. return cursor != size;
  8. }
  9. @SuppressWarnings("unchecked")
  10. public E next() {
  11. checkForComodification();
  12. //记录当前位置
  13. int i = cursor;
  14. if (i >= size)
  15. throw new NoSuchElementException();
  16. Object[] elementData = ArrayList.this.elementData;
  17. if (i >= elementData.length)
  18. throw new ConcurrentModificationException();
  19. //下一个元素的位置
  20. cursor = i + 1;
  21. return (E) elementData[lastRet = i];
  22. }
  23. //使用迭代器的remove方法
  24. public void remove() {
  25. if (lastRet < 0)
  26. throw new IllegalStateException();
  27. checkForComodification();
  28. try {
  29. //注意内部类调用外部类的方式
  30. ArrayList.this.remove(lastRet);
  31. //remove之后需要重新调整各个指针的位置
  32. cursor = lastRet;
  33. lastRet = -1;
  34. expectedModCount = modCount;
  35. } catch (IndexOutOfBoundsException ex) {
  36. throw new ConcurrentModificationException();
  37. }
  38. }
  39. final void checkForComodification() {
  40. if (modCount != expectedModCount)
  41. throw new ConcurrentModificationException();
  42. }
  43. }

2、ListItr:支持向前和向后遍历,下面看看ListItr的源码:

  1. private class ListItr extends Itr implements ListIterator<E> {
  2. ListItr(int index) {
  3. super();
  4. cursor = index;
  5. }
  6. public boolean hasPrevious() {
  7. return cursor != 0;
  8. }
  9. public int nextIndex() {
  10. return cursor;
  11. }
  12. public int previousIndex() {
  13. return cursor - 1;
  14. }
  15. @SuppressWarnings("unchecked")
  16. public E previous() {
  17. checkForComodification();
  18. //arrayList前一个元素的位置
  19. int i = cursor - 1;
  20. if (i < 0)
  21. throw new NoSuchElementException();
  22. Object[] elementData = ArrayList.this.elementData;
  23. if (i >= elementData.length)
  24. throw new ConcurrentModificationException();
  25. cursor = i;
  26. return (E) elementData[lastRet = i];
  27. }
  28. //该迭代器中添加了set方法
  29. public void set(E e) {
  30. if (lastRet < 0)
  31. throw new IllegalStateException();
  32. checkForComodification();
  33. try {
  34. ArrayList.this.set(lastRet, e);
  35. } catch (IndexOutOfBoundsException ex) {
  36. throw new ConcurrentModificationException();
  37. }
  38. }
  39. //该迭代器添加了add方法
  40. public void add(E e) {
  41. checkForComodification();
  42. try {
  43. int i = cursor;
  44. ArrayList.this.add(i, e);
  45. //重新标记指针位置
  46. cursor = i + 1;
  47. lastRet = -1;
  48. expectedModCount = modCount;
  49. } catch (IndexOutOfBoundsException ex) {
  50. throw new ConcurrentModificationException();
  51. }
  52. }
  53. }

3、使用java.util.concurrent中的CopyOnWriteArrayList解决fast-fail问题

CopyOnWriteArrayList是线程安全的, 具体看一下它的add方法源码:

  1. public boolean add(E e) {
  2. final ReentrantLock lock = this.lock;
  3. lock.lock();
  4. try {
  5. Object[] elements = getArray();
  6. int len = elements.length;
  7. Object[] newElements = Arrays.copyOf(elements, len + 1);
  8. newElements[len] = e;
  9. setArray(newElements);
  10. return true;
  11. } finally {
  12. lock.unlock();
  13. }
  14. }

三、ArrayList的其他方法源码:

  1. private boolean batchRemove(Collection<?> c, boolean complement) {
  2. //下面会提到使用final的原因
  3. final Object[] elementData = this.elementData;
  4. int r = 0, w = 0;
  5. boolean modified = false;
  6. try {
  7. //遍历List中的元素,进行验证
  8. for (; r < size; r++)
  9. if (c.contains(elementData[r]) == complement)
  10. elementData[w++] = elementData[r];
  11. } finally {
  12. //try中如果出现异常,则保证数据一致性执行下面的copy操作
  13. if (r != size) {
  14. System.arraycopy(elementData, r,
  15. elementData, w,
  16. size - r);
  17. w += size - r;
  18. }
  19. //清理无用的元素, 通知GC回收
  20. if (w != size) {
  21. // clear to let GC do its work
  22. for (int i = w; i < size; i++)
  23. elementData[i] = null;
  24. modCount += size - w;
  25. size = w;
  26. modified = true;
  27. }
  28. }
  29. return modified;
  30. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注