Java教程

从源码深入底层解析Java的数组列表ArrayList

Java基础 小海豚博客管理员 2019-03-30 20:42:00.0 278 0条

在数据结构中有学习到数字列表就是对数组的各种操作,其实Java的ArrayList类也是这样的,说白点就是对数组的get,add,set,remove,和遍历这几种操作。

读ArrayList的源码前,我要说几个方法:
在System类里有这个方法:

public static native void arraycopy(Object src, int srcPos, Object dest, int destPos,int length);
这个方法只有定义,却没有实现,方法用了一个native来修饰。native的方法,是由其它语言来实现的,一般是(C或C++),所以这儿没有实现代码。这是一个数组拷贝方法,我们只要记得这个方法就是用来将src数组里的元素的值赋值给dest数组的元素,其实srcPos指定从src数组的第几个元素开始赋值,而length是指定src数组将来赋值几个元素给dest,destPos指定赋值到dest的第几个元素开始。

Arrays的几个方法,其实这几个方法于是封装System类的arraycopy

  1. public static <T> T[] copyOf(T[] original, int newLength) {
  2. return (T[]) copyOf(original, newLength, original.getClass());
  3. }
  4. public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
  5. @SuppressWarnings("unchecked")
  6. T[] copy = ((Object)newType == (Object)Object[].class)
  7. ? (T[]) new Object[newLength]
  8. : (T[]) Array.newInstance(newType.getComponentType(), newLength);
  9. System.arraycopy(original, 0, copy, 0,
  10. Math.min(original.length, newLength));
  11. return copy;
  12. }

这2个方法就是会把原数组original赋值成新的一个数组,其中newLength是新数组的长度。

ArrayList一直维护transient Object[] elementData这个数组。

  1. /**
  2. * The array buffer into which the elements of the ArrayList are stored.
  3. * The capacity of the ArrayList is the length of this array buffer. Any
  4. * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
  5. * will be expanded to DEFAULT_CAPACITY when the first element is added.
  6. */
  7. transient Object[] elementData; // non-private to simplify nested class access

我们知道要知道数组大小,我们就要用length这个属性就行,但是我们要知道数组保存了多少元素,就只能遍历了,于是ArrayList保存了一个size,用来记录当前数组保存了多少元素。

  1. /**
  2. * The size of the ArrayList (the number of elements it contains).
  3. *
  4. * @serial
  5. */
  6. private int size;

创建ArrayList

其中ArrayList给了我们3种构造函数,分别是

  1. public ArrayList(int initialCapacity) {
  2. if (initialCapacity > 0) {
  3. this.elementData = new Object[initialCapacity];
  4. } else if (initialCapacity == 0) {
  5. this.elementData = EMPTY_ELEMENTDATA;
  6. } else {
  7. throw new IllegalArgumentException("Illegal Capacity: "+
  8. initialCapacity);
  9. }
  10. }
  11. public ArrayList() {
  12. this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  13. }
  14. public ArrayList(Collection<? extends E> c) {
  15. elementData = c.toArray();
  16. if ((size = elementData.length) != 0) {
  17. // c.toArray might (incorrectly) not return Object[] (see 6260652)
  18. if (elementData.getClass() != Object[].class)
  19. elementData = Arrays.copyOf(elementData, size, Object[].class);
  20. } else {
  21. // replace with empty array.
  22. this.elementData = EMPTY_ELEMENTDATA;
  23. }
  24. }

当你没有传入参数时,会默认给我创建的数组大小是10
当你传入初始化大小时,对其判断,如果大于1就创建数组你指定的数组,如果是0,就创建空数组,或抛出异常。
当你用其他ArrayList初始化时,用了Arrays.copyOf()进行数组的重新赋值,把传入进来的赋值成新的elementData数组。
ArrayList的get方法
这个最简单了,数组列表相比于链表,获取元素最简单,根据索引就行。用E对其进行强制转换,从这我们可以看出ArrayList保存的都是Object。

  1. E elementData(int index) {
  2. return (E) elementData[index];
  3. }
  4. public E get(int index) {
  5. rangeCheck(index);
  6. return elementData(index);
  7. }
  8. 其中 rangeCheck(index);是判断索引是否大于size
  9. private void rangeCheck(int index) {
  10. if (index >= size)
  11. throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
  12. }
  13. ArrayListset方法
  14. 这个也是简单,先判断索引是否大于size,然后保存旧的值,再重新赋值,返回旧的值。
  15. public E set(int index, E element) {
  16. rangeCheck(index);
  17. E oldValue = elementData(index);
  18. elementData[index] = element;
  19. return oldValue;
  20. }

ArrayList的add方法
这个方法有点复杂,因为我们初始化时,数组是有大小的,当你再添加新元素之前,要先判断是否数组已经满了,如果满了,就要对其进行扩容。
add(E e)

  1. public boolean add(E e) {
  2. ensureCapacityInternal(size + 1); // 对其进扩容判断
  3. elementData[size++] = e;
  4. return true;
  5. }
  6. private void ensureCapacityInternal(int minCapacity) {
  7. if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
  8. minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
  9. }
  10. ensureExplicitCapacity(minCapacity);
  11. }
  12. private void ensureExplicitCapacity(int minCapacity) {
  13. modCount++; //记录数组结构改变的次数,包括增加,删除操作都会记录
  14. // overflow-conscious code
  15. if (minCapacity - elementData.length > 0)
  16. grow(minCapacity);
  17. }
  18. private void grow(int minCapacity) {
  19. // overflow-conscious code
  20. int oldCapacity = elementData.length; //获取旧数组的长度
  21. int newCapacity = oldCapacity + (oldCapacity >> 1);//相当于int newCapacity = oldCapacity + (oldCapacity/2)
  22. if (newCapacity - minCapacity < 0)
  23. newCapacity = minCapacity;
  24. if (newCapacity - MAX_ARRAY_SIZE > 0)
  25. newCapacity = hugeCapacity(minCapacity);
  26. // minCapacity is usually close to size, so this is a win:
  27. elementData = Arrays.copyOf(elementData, newCapacity);
  28. }

在这里有个变量modCount,记录数组结构改变的次数,在增加,删除方法操作里都有,都会记录

  1. protected transient int modCount = 0;

在扩容判断这个阶段,先判断当前元素数量+1是否大于数组的长度,如果是就要扩容,扩容方法是grow()。从 int newCapacity = oldCapacity + (oldCapacity >> 1);可以看出扩容的大小是之前的1.5倍。使用Arrays.copyOf重新赋值到长度为newCapacity的 elementData数组。
add(int index, E element)
其中还有一个add(int index, E element)方法,这个add方法是将指定元素插入其中的指定位置,将当前位于该位置(如果有)的元素移动,并移动右边的任何后续元素(将一个元素添加到它们的索引中)。

  1. public void add(int index, E element) {
  2. rangeCheckForAdd(index);
  3. ensureCapacityInternal(size + 1); // Increments modCount!!
  4. System.arraycopy(elementData, index, elementData, index + 1,
  5. size - index);
  6. elementData[index] = element;
  7. size++;
  8. }

先判断是否要扩容,然后用System.arraycopy的方法对elementData其重新赋值,它的意思是把从elementData的第index的元素向elementData的第index+1的元素开始赋值,也就是index后(包括index)的元素都向后移动一位了。
addAll(Collection<? extends E> c)
这个方法是用来向现有的ArrayList后面添加传入的ArrayList。

  1. public boolean addAll(Collection<? extends E> c) {
  2. Object[] a = c.toArray();
  3. int numNew = a.length;
  4. ensureCapacityInternal(size + numNew); // Increments modCount
  5. System.arraycopy(a, 0, elementData, size, numNew);
  6. size += numNew;
  7. return numNew != 0;
  8. }

主要是先获取传入进来ArrayList中的数组,然后获取它的长度,再对其扩容判断,再用 System.arraycopy把a数组向elementData数组后面进行赋值。

ArrayList的remove方法
remove(int index)

  1. public E remove(int index) {
  2. rangeCheck(index);
  3. modCount++;
  4. E oldValue = elementData(index);
  5. int numMoved = size - index - 1;
  6. if (numMoved > 0)
  7. System.arraycopy(elementData, index+1, elementData, index,
  8. numMoved);
  9. elementData[--size] = null; // clear to let GC do its work
  10. return oldValue;
  11. }

这个也简单,就是保存要删除索引的元素的值,然后计算要移动的元素数量,就是index后面的元素都要向前移动一位。然后最后面的 elementData[—size] = null。

ArrayList的遍历
forEach
在JDK7之前,ArrayList的遍历主要用到是Iterable接口的Iterator<T> iterator();而JDK8后Iterable接口也增加了forEach这个默认方法。

  1. default void forEach(Consumer<? super T> action) {
  2. Objects.requireNonNull(action);
  3. for (T t : this) {
  4. action.accept(t);
  5. }
  6. }

ArrayList重载了这个方法

  1. @Override
  2. public void forEach(Consumer<? super E> action) {
  3. Objects.requireNonNull(action);
  4. final int expectedModCount = modCount;
  5. @SuppressWarnings("unchecked")
  6. final E[] elementData = (E[]) this.elementData;
  7. final int size = this.size;
  8. for (int i=0; modCount == expectedModCount && i < size; i++) {
  9. action.accept(elementData[i]);
  10. }
  11. if (modCount != expectedModCount) {
  12. throw new ConcurrentModificationException();
  13. }
  14. }

forEach这个默认方法,也是对这个列表进行for循环,然后调用Consumer这个接口的accept的方法,所以我们的逻辑可以写在Consumer接口的这个accept方法里,又因为Consumer接口只有一个抽象方法accept,所以我们可以用lombda表达式,如:

  1. List list =new ArrayList();
  2. list.add(1);
  3. list.add(2);
  4. list.add(3);
  5. list.forEach(System.out::print);

更多的lombda表达式使用方法可以看这篇文章:从Java匿名内部类深入到JDK8的Lombda表达式
当然也可以用匿名内部类

  1. List list =new ArrayList();
  2. list.add(1);
  3. list.add(2);
  4. list.add(3);
  5. list.forEach(new Consumer() {
  6. @Override
  7. public void accept(Object o) {
  8. System.out.print(o);
  9. }
  10. });

其他方法

这些方法很简单,看源码就懂,其实最关键的方法就是

  1. public static native void arraycopy(Object src, int srcPos, Object dest, int destPos,int length);
  2. public int size() {
  3. return size;
  4. }
  5. public boolean isEmpty() {
  6. return size == 0;
  7. }
  8. public boolean contains(Object o) {
  9. return indexOf(o) >= 0;
  10. }
  11. public int indexOf(Object o) {
  12. if (o == null) {
  13. for (int i = 0; i < size; i++)
  14. if (elementData[i]==null)
  15. return i;
  16. } else {
  17. for (int i = 0; i < size; i++)
  18. if (o.equals(elementData[i]))
  19. return i;
  20. }
  21. return -1;
  22. }
  23. public int lastIndexOf(Object o) {
  24. if (o == null) {
  25. for (int i = size-1; i >= 0; i--)
  26. if (elementData[i]==null)
  27. return i;
  28. } else {
  29. for (int i = size-1; i >= 0; i--)
  30. if (o.equals(elementData[i]))
  31. return i;
  32. }
  33. return -1;
  34. }
  35. public Object[] toArray() {
  36. return Arrays.copyOf(elementData, size);
  37. }
  38. public <T> T[] toArray(T[] a) {
  39. if (a.length < size)
  40. // Make a new array of a's runtime type, but my contents:
  41. return (T[]) Arrays.copyOf(elementData, size, a.getClass());
  42. System.arraycopy(elementData, 0, a, 0, size);
  43. if (a.length > size)
  44. a[size] = null;
  45. return a;
  46. }
暗锚,解决锚点偏移

文章评论

嘿,来试试登录吧!