6.9 clear()方法
/** * Removes all of the elements from this list. The list will * be empty after this call returns. 从列表中删除所有元素。该调用返回后,列表将为空。 */ public void clear() { modCount++; // clear to let GC do its work for (int i = 0; i < size; i++) elementData[i] = null; size = 0; }
这里我们做一个小demo:
package com.uncle; import java.lang.reflect.Field; import java.util.ArrayList; import java.util.HashMap; public class Main { public static void main(String[] args) throws Exception { HashMap hashMap = new HashMap(); ArrayList arrayList = new ArrayList(); Main main = new Main(); arrayList.add(main); arrayList.add(main); arrayList.add(main); arrayList.add(main); arrayList.add(main); arrayList.add(main); arrayList.add(main); arrayList.add(main); arrayList.add(main); arrayList.add(main); arrayList.add(main); Class<? extends ArrayList> aClass = arrayList.getClass(); Field elementData = aClass.getDeclaredField("elementData"); elementData.setAccessible(true); Object[] objects = (Object[]) elementData.get(arrayList); arrayList.clear(); System.out.println(objects.length); System.out.println(arrayList.size()); } }
显然,容量虽然扩容了,但是里面的有效元素全部清空了。
七、ArrayList与迭代器模式
迭代器模式(Iterator Pattern):提供一种方法来访问聚合对象中的各个元素,而不用暴露这个对象的内部表示。
在Java中,ArrayList的迭代器有两种:Iterator和ListIterator。
7.1 Iterator
迭代器是一个用来遍历并选择序列中的对象。Java的Iterator的只能单向移动。
案例
在写如何实现之前,先看一个使用迭代器Iterator小例子:
import java.util.ArrayList; import java.util.Iterator; import java.util.List; public class Test { @org.junit.Test public void test() { List list = new ArrayList<>(); list.add("1"); list.add("2"); list.add("3"); list.add("4"); Iterator iterator = list.iterator(); while (iterator.hasNext()) { String str = (String) iterator.next(); System.out.println(str); iterator.remove(); } System.out.println(list.size()); } }
运行结果
1 2 3 4 0 • 1 • 2 • 3 • 4 • 5
方法
iterator(),list.iterator()用来从容器对象中返回一个指向list开始处的迭代器。
next(),获取序列中的下个元素。
hasNext(),检查序列中向下是否还有元素。
remove(),将迭代器最近返回的一个元素删除。这也意味着调用remove()前需要先调用next()。
实现
迭代器模式中有四个角色:
抽象聚合类Aggregate。在ArrayList的Iterator迭代器实现中,没有抽象聚合类。虽然它实现了AbstractList,实现了List,但它向外部提供的创建迭代器的方法iterator()是它自己的。
具体聚合类ConcreteAggregate。在ArrayList的Iterator迭代器实现中,指的是ArrayList。
抽象迭代器Iterator。在ArrayList的Iterator迭代器实现中,指的是Iterator接口。
具体迭代器ConcreteIterator。在ArrayList中的Iterator迭代器实现中,指的是Itr。
ArrayList代码片段
public class ArrayList<E> { /** * 保存添加到ArrayList中的元素。 * ArrayList的容量就是该数组的长度。 * 该值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA 时,当第一次添加元素进入ArrayList中时,数组将扩容值DEFAULT_CAPACITY。 * 被标记为transient,在对象被序列化的时候不会被序列化。 */ transient Object[] elementData; // ArrayList的实际大小(数组包含的元素个数)。 private int size; /** * 返回一个用来遍历ArrayList元素的Iterator迭代器 */ public Iterator<E> iterator() { return new Itr(); } /** * AbstractList.Itr的最优化的版本 */ private class Itr implements Iterator<E> { int cursor; // 下一个要返回的元素的索引 int lastRet = -1; // 最近的被返回的元素的索引; 如果没有返回-1。 int expectedModCount = modCount; /** * 判断是否有下一个元素 */ public boolean hasNext() { //如果下一个要返回的元素的索引不等于ArrayList的实际大小,则返回false return cursor != size; } /** * 返回下一个元素 */ @SuppressWarnings("unchecked") public E next() { checkForComodification(); int i = cursor; if (i >= size) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new ConcurrentModificationException(); cursor = i + 1; return (E) elementData[lastRet = i]; } /** * 删除最近的一个被返回的元素 */ public void remove() { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.remove(lastRet); cursor = lastRet; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } @Override @SuppressWarnings("unchecked") public void forEachRemaining(Consumer<? super E> consumer) { Objects.requireNonNull(consumer); final int size = ArrayList.this.size; int i = cursor; if (i >= size) { return; } final Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) { throw new ConcurrentModificationException(); } while (i != size && modCount == expectedModCount) { consumer.accept((E) elementData[i++]); } // update once at end of iteration to reduce heap write traffic cursor = i; lastRet = i - 1; checkForComodification(); } final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } } }
Iterator
import java.util.function.Consumer; public interface Iterator<E> { boolean hasNext(); E next(); default void remove() { throw new UnsupportedOperationException("remove"); } default void forEachRemaining(Consumer<? super E> action) { Objects.requireNonNull(action); while (hasNext()) action.accept(next()); } }
Itr.java
ArrayList的内部类
7.2 ListIterator
ListIterator是一个更加强大的Iterator的子类型。它只能用于各种List类的访问。它最大的优点是可以双向移动。它还可以产生相对于迭代器在列表中指向的当前位置的前一个和后一个元素的索引,并且可以使用set()方法替换它访问过的最后一个元素。
案例
在写如何实现之前,先看一个使用列表迭代器ListIterator的小例子:
import java.util.ArrayList; import java.util.List; import java.util.ListIterator; public class Test { @org.junit.Test public void test() { List list = new ArrayList<>(); list.add("0"); list.add("1"); list.add("2"); list.add("3"); ListIterator iterator = list.listIterator(); System.out.println("--------------------向下遍历--------------------"); while (iterator.hasNext()) { int nextIndex = iterator.nextIndex(); String next = (String) iterator.next(); //int previousIndex = iterator.previousIndex(); System.out.println("当前元素:"+next+",当前元素索引:"+nextIndex/*+",前一个元素的索引"+previousIndex*/); } System.out.println("--------------------向上遍历--------------------"); while (iterator.hasPrevious()) { int previousIndex = iterator.previousIndex(); String previous = (String) iterator.previous(); System.out.println("当前元素:"+previous+",当前元素索引:"+previousIndex); } System.out.println("-----------测试set()和listIterator(n)----------"); System.out.println(list); iterator = list.listIterator(3); while(iterator.hasNext()){ iterator.next(); iterator.set("5"); } System.out.println(list); } }
运行结果
-------向下遍历------- 当前元素:0,当前元素索引:0 当前元素:1,当前元素索引:1 当前元素:2,当前元素索引:2 当前元素:3,当前元素索引:3 -------向上遍历------- 当前元素:3,当前元素索引:3 当前元素:2,当前元素索引:2 当前元素:1,当前元素索引:1 当前元素:0,当前元素索引:0 -------测试set()和listIterator(n)------- [0, 1, 2, 3] [0, 1, 2, 5]
方法
listIterator(),list.iterator()用来从容器对象中返回一个指向list开始处的迭代器。
listIterator(n),list.iterator()用来从容器对象中返回一个指向列表索引为n的迭代器。
next(),获取序列中的下个元素,运行后索引+1。
previous(),获取序列中的上个元素,运行后索引-1。
nextIndex,获取序列中的下个元素的索引。
previousIndex,获取序列中的下个元素的索引。
hasNext(),检查序列中向下是否还有元素。
hasPrevious(),检查序列中向上是否还有元素。
remove(),从列表中删除next()或previous()返回的最后一个元素。这也意味着调用remove()前需要先调用next()或者previous()。
add(E e): 将指定的元素插入列表,插入位置为迭代器当前位置之前。
set(E e):从列表中将next()或previous()返回的最后一个元素返回的最后一个元素更改为指定元素e。
实现
迭代器模式中有四个角色:
抽象聚合类Aggregate。在ArrayList的ListIterator迭代器实现中,没有抽象聚合类。虽然它实现了AbstractList,实现了List,但它向外部提供的创建迭代器的方法listIterator()是它自己的。
具体聚合类ConcreteAggregate。在ArrayList的ListIterator迭代器实现中,指的是ArrayList。
抽象迭代器Iterator。在ArrayList的ListIterator迭代器实现中,指的是ListIterator。
具体迭代器ConcreteIterator。在ArrayList中的ListIterator迭代器实现中,指的是ListItr。
ArrayList代码片段
public class ArrayList<E> { /** * 保存添加到ArrayList中的元素。 * ArrayList的容量就是该数组的长度。 * 该值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA 时,当第一次添加元素进入ArrayList中时,数组将扩容值DEFAULT_CAPACITY。 * 被标记为transient,在对象被序列化的时候不会被序列化。 */ transient Object[] elementData; // ArrayList的实际大小(数组包含的元素个数)。 private int size; /** * 返回一个一开始就指向列表索引为index的元素处的ListIterator * * @throws IndexOutOfBoundsException */ public ListIterator<E> listIterator(int index) { if (index < 0 || index > size) throw new IndexOutOfBoundsException("Index: "+index); return new ListItr(index); } /** * 返回一个一开始就指向列表索引为0的元素处的ListIterator * * @see #listIterator(int) */ public ListIterator<E> listIterator() { return new ListItr(0); } /** * AbstractList.ListItr的最优化版本 */ private class ListItr extends Itr implements ListIterator<E> { //用来从list中返回一个指向list索引为index的元素处的迭代器 ListItr(int index) { super(); cursor = index; } //获取list中的上个元素 public boolean hasPrevious() { return cursor != 0; } //获取list中的下个元素的索引 public int nextIndex() { return cursor; } //获取list中的上个元素的索引 public int previousIndex() { return cursor - 1; } //获取list中的上个元素 @SuppressWarnings("unchecked") public E previous() { checkForComodification(); int i = cursor - 1; if (i < 0) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new ConcurrentModificationException(); cursor = i; return (E) elementData[lastRet = i]; } //从列表中将next()或previous()返回的最后一个元素返回的最后一个元素更改为指定元素e public void set(E e) { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.set(lastRet, e); } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } //将指定的元素插入列表,插入位置为迭代器当前位置之前。 public void add(E e) { checkForComodification(); try { int i = cursor; ArrayList.this.add(i, e); cursor = i + 1; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } } }
Iterator
import java.util.function.Consumer; public interface Iterator<E> { boolean hasNext(); E next(); default void remove() { throw new UnsupportedOperationException("remove"); } default void forEachRemaining(Consumer<? super E> action) { Objects.requireNonNull(action); while (hasNext()) action.accept(next()); } }
ListItr.java
ArrayList的内部类。
八、阿里面试实战
7.1 ArrayList如何删除指定元素?
这是一个很麻烦的面试题,很考验对源码的认识和理解,我们来慢慢的剖析一下。
为了大家能够更好的理解ArrayList,以及这道面试题,推荐大家看一下这篇文章:
如果使用常规的思想:
public class TestListMain { public static void main(String[] args) { List<String> result = new ArrayList<>(); result.add("a"); result.add("b"); result.add("c"); result.add("d"); for (String s : result) { if ("b".equals(s)) { result.remove("b"); } } } }
真正抛异常的地方是这个检测方法, 当modCount与expectedModCount不相等的时候直接抛出异常了。那我们要看下modCount以及expectedModCount分别是什么。这里的modCount代表ArrayList的修改次数,而expectedModCount代表的是迭代器的修改次数,在创建Itr迭代器的时候,将modCount赋值给了expectedModCount,因此在本例中一开始modCount和expectedModCount都是4(添加了四次String元素)。但是在获取到b元素之后,ArrayList进行了remove操作,因此modCount就累加为5了。因此在进行检查的时候就出现了不一致,最终导致了异常的产生。到此我们找到了抛异常的原因,循环使用迭代器进行循环,但是操作元素却是使用的ArrayList操作,因此迭代器在循环的时候发现元素被修改了所以抛出异常。
我们再来思考下,为什么要有这个检测呢?这个异常到底起到什么作用呢?我们先来开下ConcurrentModificationException的注释是怎么描述的。简单理解就是不允许一个线程在修改集合,另一个线程在集合基础之上进行迭代。一旦检测到了这种情况就会通过fast-fail机制,抛出异常,防止后面的不可知状况。
/** *** * For example, it is not generally permissible for one thread to modify a Collection * while another thread is iterating over it. In general, the results of the * iteration are undefined under these circumstances. Some Iterator * implementations (including those of all the general purpose collection implementations * provided by the JRE) may choose to throw this exception if this behavior is * detected. Iterators that do this are known as <i>fail-fast</i> iterators, * as they fail quickly and cleanly, rather that risking arbitrary, * non-deterministic behavior at an undetermined time in the future. *** **/ public class ConcurrentModificationException extends RuntimeException { ... }
7.3 为啥线程不安全还使用ArrayList呢?
因为在我们正常得使用场景中,都是用来查询的,不会涉及太频繁的增删,如果涉及到频繁的增删,可以使用LinkedList,如果需要线程安全的就是可以使用Vector,CopyOrWriteArrayList
7.4 1.7和1.8版本初始化的区别
1.7的时候是初始化就创建一个容量为10的数组,1.8后是初始化先创建一个空数组,第一次add时才扩容为10
7.5 ArrayList在增删的时候是怎么做的?(为什么慢)
//尾插add方法 public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } //index(索引)插入,指定位置新增的时候,在校验之后的操作很简单,就是数组的copy 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++; } //真正扩容 private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } //删除 public E remove(int 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; }
7.6 ArrayList是线程安全的么?
不是,可以用Vector,Collections.synchronizedList(),原理都是給方法套个synchronized,
CopyOnWriteArrayList
7.7 ArrayList⽤来做队列合适么?
队列⼀般是FIFO(先⼊先出)的,如果⽤ArrayList做队列,就需要在数组尾部追加数据,数组头部删除数组,反过来也可以。但是⽆论如何总会有⼀个操作会涉及到数组的数据搬迁,这个是⽐较耗费性能的。
结论:ArrayList不适合做队列。
7.8 那数组适合⽤来做队列么?
数组是⾮常合适的。 ⽐如ArrayBlockingQueue内部实现就是⼀个环形队列,它是⼀个定⻓队列,内部是⽤⼀个定⻓数组来实现的。
另外著名的Disruptor开源Library也是⽤环形数组来实现的超⾼性能队列,具体原理不做解释,⽐较复杂。
7.9 ArrayList的遍历和LinkedList遍历性能⽐较如何?
ArrayList要比LinkedList快得多,ArrayList遍历最大的优势在于内存的连续性,CPU的内部缓存结构会缓存连续的内存片段,可以大幅降低读取内存的性能开销。
7.10 再理解ArrayList数组扩容
7.11 Java如何获取ArrayList的容量(elementData)大小?
相信你深入解读ArrayList源码之后,一定会知道ArrayList是这样的:
package com.uncle; import java.lang.reflect.Field; import java.util.ArrayList; public class Main { public static void main(String[] args) throws Exception { ArrayList arrayList = new ArrayList(); Main main = new Main(); arrayList.add(main); Class<? extends ArrayList> aClass = arrayList.getClass(); Field elementData = aClass.getDeclaredField("elementData"); elementData.setAccessible(true); Object[] objects = (Object[]) elementData.get(arrayList); System.out.println(objects.length);//10 } }
我们通过无参构造方法创建ArrayList集合,默认容量为10。
案例二
package com.uncle; import java.lang.reflect.Field; import java.util.ArrayList; public class Main { public static void main(String[] args) throws Exception { ArrayList arrayList = new ArrayList(3); Main main = new Main(); arrayList.add(main); Class<? extends ArrayList> aClass = arrayList.getClass(); Field elementData = aClass.getDeclaredField("elementData"); elementData.setAccessible(true); Object[] objects = (Object[]) elementData.get(arrayList); System.out.println(objects.length);//3 } }
我们通过有参构造方法创建ArrayList集合,默认容量为3。
案例三
package com.uncle; import java.lang.reflect.Field; import java.util.ArrayList; public class Main { public static void main(String[] args) throws Exception { ArrayList arrayList = new ArrayList(); Main main = new Main(); arrayList.add(main); arrayList.add(main); arrayList.add(main); arrayList.add(main); arrayList.add(main); arrayList.add(main); arrayList.add(main); arrayList.add(main); arrayList.add(main); arrayList.add(main); arrayList.add(main); Class<? extends ArrayList> aClass = arrayList.getClass(); Field elementData = aClass.getDeclaredField("elementData"); elementData.setAccessible(true); Object[] objects = (Object[]) elementData.get(arrayList); System.out.println(objects.length);//15 } }
我们通过无参构造方法创建ArrayList集合,默认容量为10,当我们新增11个时候,数组扩容默认容量10的1.5倍,结果为15。