java容器类分析:Collection,List,ArrayList
1、 Iterable 与 Iterator
Iterable 是个接口,实现此接口使集合对象可以通过迭代器遍历自身元素.
public interface Iterable<T>
修饰符和返回值 | 方法名 | 描述 |
Iterator<T> | iterator() | 返回一个内部元素为T类型的迭代器 |
default void | forEach(Consumer<? super T> action) | 对内部元素进行遍历,并对元素进行指定的操作 |
default Spliterator<T> | spliterator() | 创建并返回一个可分割迭代器 |
第一个接口iterator()是jdk1.5引入的,需要子类实现一个内部迭代器Iterator遍历元素。
后两个接口是JDK1.8后新添加的,forEach(Consumer action)是为了方便遍历操作集合内的元素,spliterator()则提供了一个可以并行遍历元素的迭代器,以适应现在cpu多核时代并行遍历的需求.
其中我们可以看下default修饰符,这也是Java 8后新出现的,我们知道,如果我们给一个接口新添加一个方法,那么所有他的具体子类都必须实现此方法,为了能给接口拓展新功能,而又不必每个子类都要实现此方法,Java 8新加了default关键字,被其修饰的方法可以不必由子类实现,并且由dafault修饰的方法在接口中有方法体,这打破了Java之前对接口方法的规范.
Iterator 为迭代器类,用于遍历容器。
public interface Iterator<E>
修饰符和返回值 | 方法名 | 描述 |
boolean | hasNext() | 判断迭代器所指元素是否为最后一个 |
E | next() | 下一个元素 |
default Void | remove() | 移除迭代器只想的当前元素 |
default Void | forEachRemaining(Consumer<? super E> action) | 遍历迭代器指向元素后面的所有元素 |
AbstartList中实现了Iterator类作为List内部的迭代器,用于访问内部元素,其代码如下:
1 private class Itr implements Iterator<E> { 2 /** 3 * Index of element to be returned by subsequent call to next. 4 */ 5 int cursor = 0; 6 7 /** 8 * Index of element returned by most recent call to next or 9 * previous. Reset to -1 if this element is deleted by a call 10 * to remove. 11 */ 12 int lastRet = -1; 13 14 /** 15 * The modCount value that the iterator believes that the backing 16 * List should have. If this expectation is violated, the iterator 17 * has detected concurrent modification. 18 */ 19 int expectedModCount = modCount; 20 21 public boolean hasNext() { 22 return cursor != size(); 23 } 24 25 public E next() { 26 checkForComodification(); 27 try { 28 int i = cursor; 29 E next = get(i); 30 lastRet = i; 31 cursor = i + 1; 32 return next; 33 } catch (IndexOutOfBoundsException e) { 34 checkForComodification(); 35 throw new NoSuchElementException(); 36 } 37 } 38 39 public void remove() { 40 if (lastRet < 0) 41 throw new IllegalStateException(); 42 checkForComodification(); 43 44 try { 45 AbstractList.this.remove(lastRet); 46 if (lastRet < cursor) 47 cursor--; 48 lastRet = -1; 49 expectedModCount = modCount; 50 } catch (IndexOutOfBoundsException e) { 51 throw new ConcurrentModificationException(); 52 } 53 } 54 55 final void checkForComodification() { 56 if (modCount != expectedModCount) 57 throw new ConcurrentModificationException(); 58 } 59 } 60
2、Collection
Collection 是容器类的接口,里面可以存放很多Elements,很多容器都实现了该接口。
public interface Collection<E> extends Iterable<E>
修饰符和返回值 | 方法名 | 描述 |
int | size() | 判断容器的大小 |
boolean | isEmpty() | 判空 |
boolean | contains(Object o) | 是否包含某元素 |
Object[] | toArray() | 转化为数组 |
<T> T[] | toArray(T[] a) | 将容器中所有元素拷贝到a中,如果a不够大,则拷贝到返回的数组中。(见AbstactCollection中实现) |
boolean | add(E e) | 添加元素 |
boolean | remove(Object o) | 移除容器中第一个出现Object对象,如果Object为null,则移除第一个出现的null。如果没有Object对象返回false |
boolean | containsAll(Collection<?> c) | 包含c中所有元素 |
boolean | addAll(Collection<? extends E> c); | 将c中所有元素添加到容器中 |
boolean | removeAll(Collection<?> c) | 如果容器中包含c中的元素,删除。(调用remove(Object)) |
default boolean | removeIf(Predicate<? super E> filter) | 移除所有符合条件的元素(JDK1.8中引入) |
boolean | retainAll(Collection<?> c) | 保留在c中出现的元素,其它全部移除 |
boolean | clear() | |
boolean | equals(Object o) | 与o中所有元素都相等则相等 |
int | hashCode() | c1.equals(c2) 那么他们的hashCode()一定相等,反之不成立 |
default Spliterator<E> | spliterator() | 在所有元素之上创建一个Spliterator |
default Stream<E> | stream() | |
default Stream<E> | parallelStream() |
上述很多函数的实现可以参考 AbstactList中的实现。
3. List
List是一个接口,继承了Collection中的所有接口,并且添加了自身相关接口和具体实现。
由上图可以看出,Collection分成了三个分支,List就是其中一个,下面我们具体分析一下增加的接口。
public interface List<E> extends Collection<E>
修饰符和返回值 | 方法名 | 描述 |
Collection中的所有接口 | ||
default void | replaceAll(UnaryOperator<E> operator) | 将运算操作后的结果替换List中原有元素 |
default void | sort(Comparator<? super E> c) | 将List中所有元素排序 |
E | get(int index); | |
E | set(int index, E element) | |
E | remove(int index) | |
int | indexOf(Object o) | o在List中第一次出现的位置 |
int | lastIndexOf(Object o) | o在List中最后一次出现的位置 |
ListIterator<E> | listIterator() | 获取List的迭代器 |
ListIterator<E> | listIterator(int index) | 获取从某个位置开始的迭代器,index为迭代器起始位置 |
List<E> | subList(int fromIndex, int toIndex) | 子List |
上表可以看出,增加了 和index相关的接口,根据index对List进行的get、set、remove等操作。另一类添加的接口是ListIteator相关的,获取List的迭代器。
3.1 ListIterator
public interface ListIterator<E> extends Iterator<E>
ListIterator 不光包含Iterator中的三个接口还增加了作为一个List迭代器应该有的接口,如 next(),previous()等
修饰符和返回值 | 方法名 | 描述 |
Iterator中的所有接口 | ||
boolean | hasNext() | |
E | next() | |
boolean | hasPrevious() | |
E | previous() | |
int | nextIndex() | |
int | previousIndex() | |
void | remove() | 删除next()返回元素 |
void | set(E e) | 替换next()返回的元素 |
void | add(E e) | 在nextIndex()后插入元素 |
首先需要明确ListIterator迭代器的作用:
- 允许我们向前、向后两个方向遍历 List;
- 在遍历时修改 List 的元素;
- 遍历时获取迭代器当前游标所在位置。
注意,迭代器 没有当前所在元素一说,它只有一个游标( cursor )的概念,这个游标总是在元素之间,比如这样:
迭代器的初始位置:
调用next()后迭代器的位置
调用 previous() 游标就会回到之前位置。当向后遍历完元素,游标就会在元素 N 的后面
也就是说长度为 N 的集合会有 N+1 个游标的位置。
3.2 AbstractCollection / AbstractList
在上面的继承关系图中并没有显示出AbstractCollect和AbstractList的存在,但是在阅读源码的时候经常遇到这两个类,下面讲一下这两个类的作用。
首先需要明确的一点是AbstractCollect和AbstractList都是抽象类而不是接口,它们分别实现了Collection和List接口中的部分函数。这样继承者直接继承AbstractXXXX 而不需要自己重复实现里面的所有接口。这两个抽象类抽离了公共部分,进行了实现,减少后续类的工作量。
ArrayList 和LinkedList都直接或者间接继承了AbstartList类。下图为这两个类的继承关系:
具体这两个类里面实现了哪些接口,请自己阅读源码不再讲解。
3.3 ArrayList
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable我们看到ArrayList的定义的时候很可能会出现一个疑问,为什么它已经继承了AbstractList了还需要去实现List<E>接口? 答案是,后面的List<E>可以去掉,这里只是让阅读者明白ArrayList是个List。 终于好不容易到了开发者常用的类了,有点窃喜:transient Object[] elementData;这个很重要的成员变量elementData数组用来存放ArrayList中的元素,当第一个元素添加进来后,它的默认长度变为10。(java中“transient”关键字修饰的成员变量在类序列化的过程中不会被持久化到文件中,保证该成员变量保存信息的安全。)
ArrayList的构造函数中可以直接指定elementData数组的长度,那么问题来了,当数组已经完全被占用再向ArrayList中添加元素时,如何再分配更大长度的数组?如何把旧数据拷贝到新数组中?答案见下面这段源码
1 private void grow(int minCapacity) { //最少需要的容量 2 // overflow-conscious code 3 int oldCapacity = elementData.length; 4 int newCapacity = oldCapacity + (oldCapacity >> 1); // 分配最小容量的 1.5倍 5 if (newCapacity - minCapacity < 0) 6 newCapacity = minCapacity; 7 if (newCapacity - MAX_ARRAY_SIZE > 0) 8 newCapacity = hugeCapacity(minCapacity); // 最大容量比较(Inter.MAX_VALUE) 9 // minCapacity is usually close to size, so this is a win: 10 elementData = Arrays.copyOf(elementData, newCapacity); // 将旧数据拷贝到新数组中 11 }
其它接口不再细说。
参考:https://www.cnblogs.com/bushi/p/6647006.html
上一篇: 04_JavaSE之OOP--面向对象(封装、继承)
下一篇: 课时28.假链接(掌握)
推荐阅读
-
Java多线程并发编程中并发容器第二篇之List的并发类讲解
-
java容器类分析:Collection,List,ArrayList
-
Java容器类源码分析之Iterator与ListIterator迭代器(基于JDK8)
-
java【集合类】源代码分析--ArrayList
-
java 容器集合类的区别用法(Vector ArrayList Map)
-
Java的collection集合/set容器/list容器/map容器
-
关于 Java List 容器的源码分析的补充
-
java容器类分析:Collection,List,ArrayList
-
Java容器类源码分析之Iterator与ListIterator迭代器(基于JDK8)
-
Java中的集合(Collection接口、List接口、List接口的三种实现类、List接口的集合迭代)