List，Collection，Iterable源码简单分析
集合是个庞大的家族。层次关系如下：（图片取自：https://www.cnblogs.com/leeplogs/p/5891861.html）
经常用List集合来存取数据，底层代码是怎么写的呢，开始看看，简单分析一下。
public interface List<E> extends Collection<E>{}
List是个泛型接口，继承Collection，看一下Collection。
public interface Collection<E> extends Iterable<E> {}
Collection继承Iterable<E>。
一、Iterable
Iterable<T>接口的作用呢，也就是继承了Iterable类的接口或者类都可以进行 “foreach”来循环遍历。看一下Iterable的源码。
public interface Iterable<T> {
//1 Iterator<T> iterator(); //2 default void forEach(Consumer<? super T> action) {
Objects.requireNonNull(action); for (T t : this) { action.accept(t); } } //3 default Spliterator<T> spliterator() { return Spliterators.spliteratorUnknownSize(iterator(), 0); } }
其中API如下：
1. 返回类型为 T元素的迭代器。
2. 对Iterable的每个元素执行给定的操作，直到所有元素都被处理或动作引发异常。 除非实现类另有规定，否则按照迭代的顺序执行操作（如果指定了迭代顺序）。 动作抛出的异常被转发给呼叫者。
3. 在Iterable描述的元素上创建一个Iterable 。百度一下Spliterator是java8中的新的迭代器，具体以后Spliterator单独分析。（没看懂…）
注：JDK1.8中为了加强接口的能力，使得接口可以存在具体的方法，前提是方法需要被default或static关键字所修饰，接口可以有一些默认的方法。
二、Collection（集合）
package java.util;
import java.util.function.Predicate;
import java.util.stream.Stream;
import java.util.stream.StreamSupport;
public interface Collection<E> extends Iterable<E> { int size(); boolean isEmpty(); boolean contains(Object o); Iterator<E> iterator(); Object[] toArray(); <T> T[] toArray(T[] a); boolean add(E e); boolean remove(Object o); boolean containsAll(Collection<?> c); boolean addAll(Collection<? extends E> c); boolean removeAll(Collection<?> c); //2 default boolean removeIf(Predicate<? super E> filter) { Objects.requireNonNull(filter); boolean removed = false; final Iterator<E> each = iterator(); while (each.hasNext()) { if (filter.test(each.next())) { each.remove(); removed = true; } } return removed; } //1 boolean retainAll(Collection<?> c); void clear(); boolean equals(Object o); int hashCode(); //3 @Override default Spliterator<E> spliterator() { return Spliterators.spliterator(this, 0); } //4 default Stream<E> stream() { return StreamSupport.stream(spliterator(), false); } //5 default Stream<E> parallelStream() { return StreamSupport.stream(spliterator(), true); } }
Collection是集合，它相当于可以容纳相同类型的元素的一个容器，提供了存，取，删除容器中元素的方法。
其中大部分方法都是大多数java工程师比较熟悉的方法。具体方法的区别或者重写在具体的实现类中区分。
1.retainAll 这个方法有些陌生。
这个方法在实现类里有具体的实现。大概意思是 A集合调用该方法，参数传入B集合。
那么 （1）.A集合与 A和B的交集相同 ，则返回true，否则返回false。（2）.A集合变为A与B的交集。
其中有一些方法是java1.8的新方法：
2.removeIf
描述：删除满足给定谓词的此集合的所有元素，删除了返回true，否则返回false。其中可以Predicate可以用lambda表达式，例如：
Predicate<String> predicateTestOne = value-> value.equals(3);
Predicate<Integer> predicateTestTwo = value-> value > 0;
System.out.println(predicateTestOne.test(“12345”));
System.out.println(predicateTestTwo.test(1));
输出true和false。
调用removeIf方法，删除集合中满足条件的元素。
3.spliterator
4.stream 5.parallelStream
大概是可以将数组通过一些条件来转化为流，或某些功能可以作为流来使用。
java8中的新特性以后单独看书学习。
三、List（有序集合）
List接口继承了Collection接口。以下源码的方法显示不同的部分。
package java.util; import java.util.function.UnaryOperator; public interface List<E> extends Collection<E> {
.......................
.......................
//在集合中指定位置插入一个集合
boolean addAll(int index, Collection<? extends E> c);
default void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);
final ListIterator<E> li = this.listIterator();
while (li.hasNext()) {
li.set(operator.apply(li.next()));
}
}
@SuppressWarnings({“unchecked”, “rawtypes”})
default void sort(Comparator<? super E> c) {
Object[] a = this.toArray();
Arrays.sort(a, (Comparator) c);
ListIterator<E> i = this.listIterator();
for (Object e : a) {
i.next();
i.set((E) e);
}
}
E get(int index);
E set(int index, E element);
void add(int index, E element);
E remove(int index); int indexOf(Object o);
int lastIndexOf(Object o);
ListIterator<E> listIterator();
ListIterator<E> listIterator(int index);
List<E> subList(int fromIndex, int toIndex);
@Override
default Spliterator<E> spliterator() {
return Spliterators.spliterator(this, Spliterator.ORDERED);
}
}List是有序集合（又称为序列）；
List可以精确的控制每个元素的位置，包括插入，搜索，移除等。
List允许重复的元素，允许有多个空元素。
List接口提供 ListIterator这个特殊的迭代器，来进行元素的插入和更换。
其中有些特殊的陌生的方法如下：
1.replaceAll 将该列表的每个元素替换为将该运算符应用于该元素的结果。方法很简单，就是利用ListIterator迭代器循环遍历进行修改值。其中涉及了UnaryOperator这个接口，这个接口的中文翻译为是一元运算符。继承了Function接口。
可以使用lambda表达式的例子来简单说明。
List<Integer> testOne = new ArrayList<>(); testOne.add(2); testOne.add(3); testOne.replaceAll(t -> t + 2); System.out.println(testOne);
输出 [4,5].
2.sort 根据Comparator中的排序规则重新排序该集合。
关键代码
Arrays.sort(a, (Comparator) c);
下面来一点儿一点儿分析代码的执行逻辑。
public class Arrays {
...
public static <T> void sort(T[] a, Comparator<? super T> c) { if (c == null) {
//（1） sort(a); } else {
//（2） if (LegacyMergeSort.userRequested)
//（3） legacyMergeSort(a, c); else
//（4） TimSort.sort(a, 0, a.length, c, null, 0, 0); } }
...
}
如果比较器为空，则进行（1），如下：
public static void sort(Object[] a) {
//（2） if (LegacyMergeSort.userRequested)
//（5） legacyMergeSort(a); else
//（6） ComparableTimSort.sort(a, 0, a.length, null, 0, 0);//java8 }
private static void legacyMergeSort(Object[] a) {
Object[] aux = a.clone();
mergeSort(aux, a, 0, a.length, 0);
}
接下来判断（2）中的表达式，LegacyMergeSort是内部类（将来会废除的类）。
static final class LegacyMergeSort { private static final boolean userRequested = java.security.AccessController.doPrivileged( new sun.security.action.GetBooleanAction( "java.util.Arrays.useLegacyMergeSort")).booleanValue(); }
其中的含义具体参考了API注释和博客 https://blog.csdn.net/xuhailiang0816/article/details/79541681。
但是怎么控制是否使用老版，还是jdk1.8新的排序，以及设置参数的意义，以及其中AccessController.doPrivileged的安全检查在开发中的意义还是没有理解。表达式为true执行legacyMergeSort()进行归并排序或者为false执行java8中新提供的ComparableTimSort.sort()来采用优化更好的归并排序算法进行排序。
所以有序集合的sort()方法参数为null的话，默认用归并算法进行正序排列。如果sort()中的参数不为空，则按照Comparator比较器中的规则来进行排序。
相关文章