List,Collection,Iterable源码简单分析

2019-08-09 00:00:00 分析 简单 源码

  集合是个庞大的家族。层次关系如下:(图片取自:https://www.cnblogs.com/leeplogs/p/5891861.html)

     《List,Collection,Iterable源码简单分析》

 

  经常用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。

   《List,Collection,Iterable源码简单分析》

    但是怎么控制是否使用老版,还是jdk1.8新的排序,以及设置参数的意义,以及其中AccessController.doPrivileged的安全检查在开发中的意义还是没有理解。表达式为true执行legacyMergeSort()进行归并排序或者为false执行java8中新提供的ComparableTimSort.sort()来采用优化更好的归并排序算法进行排序。

    所以有序集合的sort()方法参数为null的话,默认用归并算法进行正序排列。如果sort()中的参数不为空,则按照Comparator比较器中的规则来进行排序。

相关文章