Java Deque

发表于 2018-10-25 更新于 2021-02-21

Java Deque

Deque 双端队列,内部有双端队列的相关方法,同时也有Stack,Queue和Colleciton的相关操作方法.

Deque内部有两个迭代器,一个是递减迭代器.

public Deque<E> extends Queue<E>{
  void addFirst();
  void addLast();
  boolean offerFirst();
  boolean offerLast();
  E removeFirst();
  E removeLast();
  E pollFirst();
  E pollLast();
  E getLast();
  E peekFirst();
  E peekLast();

  boolean removeFirstOccurence(Object o);
  boolean removeLastOccurence(Object o);

  // Queue Methods
  boolean add(E e);
  boolean offer(E e);
  E remove();
  E poll();
  E element();
  E peek();

  // Stack Methods
  void push(E e);
  E pop();


  // Collection Methods
  boolean remove(Object o);
  boolean contains(Object o);
  public int size();

  Iterator<E> iterator();

  Iterator<E> descendingIterator();

}

Java AbstractSequentialList

发表于 2018-10-25 更新于 2021-02-21

Java AbstractSequentialList

这次源码比较短2333

可以看到,在AbstractSequentialList中实现了AbstractList中的抽象方法get和抛出UnsupportedOperationException的方法set,add,remove.

同时这些方法都通过listIterator()返回的迭代器实现,但是在AbstractSequentialList中的listIterator()是一个抽象方法,并没有实现.

源码

public abstract class AbstractSequentialList<E> extends AbstractList<E>{
  protected AbstractSequentialList{

  }

  public E get(int index){
    try{
      return listIterator(index).next();
    } catch(NuSuchElementException exc){
      throw new IndexOutOfBoundsException("index: "+index);
    }
  }

  public E set(int index, E element){
    try{
      ListIterator<E> e =listIterator(index);
      E oldVal = e.next();
      e.set(element);
      return oldVal;
    } catch(NoSuchElementException exc){
      throw new IndexOutOfBoundsException("index : "+index);
    }
  }

  public void add(int index, E element ){
    try{
      listIterator(index).add(element);
    } catch(NoSuchElementException exc){
      throw new IndexOutOfBoundsException("index: "+index);
    }
  }

  public E remove(int index){
    try{
      ListIterator<E> e = listIterator(index);
      E outCast = e.next();
      e.remove();
      return outCast;
    } catch(NoSuchElementException exc){
      throw new IndexOutOfBoundsException("index: "+index);
    }
  }

  public boolean addAll(int index, Collection<? extends E> c){
    try{
      boolean modified = false;
      ListIterator<E> e1 = listIterator(index);
      Iterator<? extends E> e2 = c.Iterator();
      while( e2.hasNext()){
        e1.add(e2.next());
        modified = true;
      }
      return modified;
    } catch(NoSuchElementException exc){
      throw new IndexOutOfBoundsException("index : "+index);
    }
  }

  public Iterator<E> iterator(){return listIterator();}

  public abstract ListIterator<E> listIterator(int index);
}

Java Queue

发表于 2018-10-25 更新于 2021-02-21

Java Queue

源码

public interface Queue<E> extends Collection<E>{
  boolean add(E e);

  boolean offer(E e);

  E remove();

  E poll();

  E element();

  E peek();
}

分析

Queue 定义了一些队列操作所需要的方法

插入操作
- add
- offer
取出并去除操作
- remove
- poll
取出不删除操作
- element
- peek

每个操作的不同方法基本上就是是否会抛出异常的区别

Java ArrayList

发表于 2018-10-24 更新于 2021-02-21

Java ArrayList

介绍

ArrayList 内部维护了一个

1	transient Object[] elementData;

调用构造函数的时候把内部的静态空数组赋值给elementData.或者根据长度赋值一个新的数组

add,get等操作通过调用elementData来实现, 如果elementData的长度不足,则经过一连串跳转之后调用native方法将数组复制到一个size比原先大1的新数组中.

ArrayList

1
2
3

ArrayList<E> extends AbstractList<E> implements List<E> ,RandomAccess,Cloneable,java.io.Serializable{
  ...
}

ArrayList类实现了4个interface

List
RandomAccess
Cloneable
java.io.Serializable

除了List接口之外,其余的三个接口都是空的

public interface RandomAccess{

}

public interface Cloneable{

}

public interface Serializable {
}

RandomAccess

表示实现了该接口的类使用for循环迭代比使用迭代器更快

Cloneable

实现了该接口的类就需要重写Object.clone()方法

API原文为:

By convention, classes that implement this interface should override
Object.clone (which is protected) with a public method.

Serializable

表示该类可序列化,需要自定义一个序列号的uid作为识别

1	private static final long serialVersionUID = 8683452581122892189L;

Java AbstractList

发表于 2018-10-24 更新于 2021-02-21

Java AbstractList

介绍

AbstractList文件的内部结构是这样的

AbstractList.java
- class AbstractList
  - class Itr
  - class ListItr
- class SubList
- class RandomAccess

AbstractCollection

AbstractList 继承 AbastractCollection

AbstractCollection 内部具体实现了

isEmpty
contains
toArray
T[] toArray
remove
containsAll
addAll
removeAll
retainAll
clear
toString

这些方法,只有 iterator和size 作为抽象方法交由子类实现

AbstractList

AbstractList extends AbstractCollection implements List

这个类只是实现了

indexOf
lastIndexOf
clear
addAll

同时,AbstractList内部还有两个子类

Itr
ListItr

Itr & ListItr

其中 Itr 有下面这两个方法

next
remove

而 ListItr extends Itr implements ListIterator
实现了

previous
previousIndex
nextIndex
set
add
equals
..
等方法.

总结

到这一步为止,nextIndex,previousIndex这些方法通过迭代器中的cursor变量得以实现.equals方法也是通过迭代器的hasNext()+next()完成.但是get,set,add等方法还未曾有具体的实现.

目前为止AbstractList是一个抽象类,SubList继承了AbstractList,
在SubList中,set,get方法会调用SubList内部的private AbstractList 变量实现. 但是AbstractList内部,并没有对set,get方法进行实现.

set 方法会抛出异常,而get方法还是一个抽象方法.

源码

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
  protected AbstractList(){

  }

  public boolean add(E e){
    add(size(), e);
    return true;
  }

  abstract public E get(int index);

  public E set(int index , E elemnt ){
    throw new UnsupportedOperationException();
  }

  public void add(int index, E element){
    throw new UnsupportedOperationException();
  }

  public E remove(int index ){
    throw new UnsupportedOperationException();
  }

  public int indexOf(Object o){
    ListIterator<E> it = listIterator();
    if(o == null){
      while(it.hasNext()){
        if(it.next() == null)
          return it.previousIndex();
      }
    } else {
      while(it.hasNext()){
        if(o.equals(it.next()))
          return it.previousIndex();
      }
    }

    return -1;
  }

  public int lastIndexOf(Object o ){
    ListIterator<E> it = listIterator();
    if( o == null){
      while(it.hasPrevious()){
        if(it.previous() == null)
          return it.nextIndex();
      }
    } else {
      while(it.hasPrevious()){
        if(o.equals(it.previous()))
          return it.nextIndex();
      }
    }
    return -1;
  }

  public void clear(){
    removeRange(0,size());
  }

  public boolean addAll(int index, Collection<? extends E> c){
    rangeCheckForAdd(index);
    boolean modified = false;
    for(E e : c){
      add(index++,e);
      mmodified = true;
    }

    return modified;
  }

  public ListIterator<E> listIterator(){
    return listIterator(0);
  }

  public ListIterator<E> listIterator(final int index){
    rangeCheckForAdd(index);
    return new ListItr(index);
  }

  private class Itr implements Iterator<E> {
    int cursor = 0;

    int lastRet = -1 ;

    int expectedModCount = modCount;

    public E next(){
      checkForComodification();
      try{
        int i = cursor;
        E next = get(i);
        lastRet = i;
        cursor = i +1 ;
        return next;
      } catch(IndexOutofBoundsException e){
        checkForComodification();
        throw new NoSuchElementException();
      }
    }

    public void remove(){
      if(lastRet <0)
        throw new IllegalStateException();
      checkForComodification();

      try{
        AbstractList.this.remove(lastRet);
        if(lastRet < cursor)
          cursor--;
        lastRet = -1;
        expectedModCount = modCount;
      } catch(IndexOutofBoundsException e) {
        throw new ConcurrentModificationException();
      }
    }

    final void checkForComodification(){
      if(modCount != expectedModCount)
        throw new ConcurrentModificationException();
    }
  }

  private class ListItr extends   Itr implements ListIterator<E>{
    ListItr(int index ) { cursor = index;}

    public boolean hasPrevious{ return cursor != 0;}

    public E previous(){
      checkForComodification();
      try{
        int i = cursor -1;
        E previous = get(i);
        lastRet = cursor = i;
        return previous;
      } catch(IndexOutofBoundsException e){
        checkForComodification();
        throw new NoSuchElementException();
      }
    }

    public int nextIndex(){
      return cursor;
    }

    public int previousIndex(){
      return cursor -1;
    }

    public set(E e){
      if(lastRet < 0)
        throw new IllegalStateException();
      checkForComodification();

      try{
        AbastractList.this.set(lastRet,e);
        expectedModCount = modCount;
      } catch( IndexOutofBoundsException ex){
        throw new ConcurrentModificationException();
      }
    }

    public void add(E e){
      checkForComodification();

      try{
        int i = cursor;

        AbstractList.this.add(i,e);
        lastRet = -1;
        cursor  =i+1;
        expectedModCount = modCount;
      } catch(IndexOutofBoundsException ex){
        throw new ConcurrentModificationException();
      }
    }

    public List<E> subList(int fromIndex, int toIndex){
      return (this instanceof RandomAccess ? new RandomAccessSubList<>(this,fromIndex,toIndex) : new SubList<>(this,fromIndex,toIndex));
    }

    public boolean equals(Object c){
      if( o == this){
        return true;
      }

      if (!(o instanceof List))
        return false;

      ListIterator<E> e1 = listIterator();
      ListIterator<?> e2 = ((List<?>) o).listIterator();

      while(e1.hasNext() && e2.hasNext()){
        E o1 =  e1.next();
        Object o2 = e2.next();
        if(!(o1 == null ? o2 == null : o1.equals(o2)))
          return false;
      }

      return !(e1.hasNext() || e2.hasNext());
    }

    public int hashCode(){
      int hashCode = 1;
      for (E e : this){
        hashCode = 31* hashCode + (e == null ?  0 : e.hashCode());
      }
      return hashCode;
    }

    protected void removeRange(int fromIndex, int toIndex){
      ListIterator<E> it = listIterator(fromIndex)
      for(int i =0, n  = toIndex- fromIndex; i<n;i++){
        it.next();
        it.remove();
      }
    }

    protected transient int modCount = 0;

    private void rangeCheckForAdd(int index){
      if(index<0 || index > size)
        throw new IndexOutofBoundsException(outOfBoundsMsg(index));
    }

    private String outOfBoundsMsg(int index){
      return "index " + index+ ", size :"+ size();
    }
  }

}

class SubList<E> extends AbstractList<E>{
  private final AbstractList<E> l;
  private final int offset;

  private int size;


      SubList(AbstractList<E> list, int fromIndex, int toIndex) {
          if (fromIndex < 0)
              throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
          if (toIndex > list.size())
              throw new IndexOutOfBoundsException("toIndex = " + toIndex);
          if (fromIndex > toIndex)
              throw new IllegalArgumentException("fromIndex(" + fromIndex +
                                                 ") > toIndex(" + toIndex + ")");
          l = list;
          offset = fromIndex;
          size = toIndex - fromIndex;
          this.modCount = l.modCount;
      }

      public E set(int index, E element) {
          rangeCheck(index);
          checkForComodification();
          return l.set(index+offset, element);
      }

      public E get(int index) {
          rangeCheck(index);
          checkForComodification();
          return l.get(index+offset);
      }

      public int size() {
          checkForComodification();
          return size;
      }

      public void add(int index, E element) {
          rangeCheckForAdd(index);
          checkForComodification();
          l.add(index+offset, element);
          this.modCount = l.modCount;
          size++;
      }

      public E remove(int index) {
          rangeCheck(index);
          checkForComodification();
          E result = l.remove(index+offset);
          this.modCount = l.modCount;
          size--;
          return result;
      }

      protected void removeRange(int fromIndex, int toIndex) {
          checkForComodification();
          l.removeRange(fromIndex+offset, toIndex+offset);
          this.modCount = l.modCount;
          size -= (toIndex-fromIndex);
      }

      public boolean addAll(Collection<? extends E> c) {
          return addAll(size, c);
      }

      public boolean addAll(int index, Collection<? extends E> c) {
          rangeCheckForAdd(index);
          int cSize = c.size();
          if (cSize==0)
              return false;

          checkForComodification();
          l.addAll(offset+index, c);
          this.modCount = l.modCount;
          size += cSize;
          return true;
      }

      public Iterator<E> iterator() {
          return listIterator();
      }

      public ListIterator<E> listIterator(final int index) {
          checkForComodification();
          rangeCheckForAdd(index);

          return new ListIterator<E>() {
              private final ListIterator<E> i = l.listIterator(index+offset);

              public boolean hasNext() {
                  return nextIndex() < size;
              }

              public E next() {
                  if (hasNext())
                      return i.next();
                  else
                      throw new NoSuchElementException();
              }

              public boolean hasPrevious() {
                  return previousIndex() >= 0;
              }

              public E previous() {
                  if (hasPrevious())
                      return i.previous();
                  else
                      throw new NoSuchElementException();
              }

              public int nextIndex() {
                  return i.nextIndex() - offset;
              }

              public int previousIndex() {
                  return i.previousIndex() - offset;
              }

              public void remove() {
                  i.remove();
                  SubList.this.modCount = l.modCount;
                  size--;
              }

              public void set(E e) {
                  i.set(e);
              }

              public void add(E e) {
                  i.add(e);
                  SubList.this.modCount = l.modCount;
                  size++;
              }
          };
      }

      public List<E> subList(int fromIndex, int toIndex) {
          return new SubList<>(this, fromIndex, toIndex);
      }

      private void rangeCheck(int index) {
          if (index < 0 || index >= size)
              throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
      }

      private void rangeCheckForAdd(int index) {
          if (index < 0 || index > size)
              throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
      }

      private String outOfBoundsMsg(int index) {
          return "Index: "+index+", Size: "+size;
      }

      private void checkForComodification() {
          if (this.modCount != l.modCount)
              throw new ConcurrentModificationException();
      }
}

class RandomAccessSubList<E> extends SubList<E> implements RandomAccess {
    RandomAccessSubList(AbstractList<E> list, int fromIndex, int toIndex) {
        super(list, fromIndex, toIndex);
    }

    public List<E> subList(int fromIndex, int toIndex) {
        return new RandomAccessSubList<>(this, fromIndex, toIndex);
    }
}

Java ListIterator

发表于 2018-10-24 更新于 2021-02-21

Java ListIterator

ListIterator extends Iterator,比起Iterator主要只有forEach方法,而ListIterator增加了大量的List处理的方法

源码

public ListIterator<E>  extends Iterator<E>{
  boolean hasNext();

  E next();

  boolean hasPrevious();

  E previous();

  int nextIndex();

  int previousIndex();

  void remove();

  void set(E e);

  void add(E e);
}

显而易见,

Java Comparator

发表于 2018-10-24 更新于 2021-02-21

Java Comparator

源码

@FunctionalInterface
public interface Comparator<T>{

  int compare(T o1, T o2);

  boolean equals(Object obj);

  default Comparator<T> reversed(){
    return Collections.reverseOrder(this);
  }

  default Comparator<T> thenComparing(Comparator<? super T> other){
    Objects.requireNonNull(other);
    return (Comparator<T> & Serializable)(c1,c2)->{
      int res = compare(c1,c2);
      return (res != 0) > ? res :other.compare(c1,c2);  
    }
  }

  default <U> Comparator<T> thenComparing(Function<? super T, ? extends U> keyExtractor,  Comparator<? super U> keyComparator){
      return thenComparing(comparing(keyExtractor,keyComparator));
  }


  default <U extends Comparable<? super U>> Comparator<T> thenComparing( Function<? super T, ? extends U> keyExtractor){
    return thenComparing(comparing(keyExtractor));
  }

  default Comparator<T> thenComparing(ToIntFunction<? super T> keyExtractor){
    return thenComparing(comparingInt(keyExtractor));
  }

  default Comparator<T> thenComparingLong(ToLongFunction<? super T> keyExtractor) {
    return thenComparing(comparingLong(keyExtractor));
  }

  default Comparator<T> thenComparingDouble(ToDoubleFunction<? super T> keyExtractor) {
    return thenComparing(comparingDouble(keyExtractor));
  }

  public static <T extends Comparable<? super T>> Comparator<T> reverseOrder() {
      return Collections.reverseOrder();
  }

  public static <T extends Comparable<? super T>> Comparator<T> naturalOrder(){
    return (Comparator<T>) Comparators.NaturalOrderComparator.INSTANCE;
  }

  public static <T> Comparator<T> nullsFirst(Comparator<? super T> comparator){
    return new Comparators.NullComparator<>(true,comparator);
  }

  public static <T> Comparator<T> nullsLast(Comparator<? super T> comparator){
    return new Comparators.NullComparator<>(false,comparator);
  }

  public static <T,U> Comparator<T> comparing(Function<? super T, ? extends U> keyExtractor,Comparator<? super U> keyComparator){
    Objects.requireNonNull(keyExtractor);
    Objects.requireNonNull(keyComparator);
    return (Comparator<T> & Serializable)(c1,c2) ->keyComparator.compare(keyExtractor.apply(c1),keyExtractor.apply(c2));
  }

  public static <T> Comparator<T> comparingInt(ToIntFunction<? super T> keyExtractor) {
       Objects.requireNonNull(keyExtractor);
       return (Comparator<T> & Serializable)
           (c1, c2) -> Integer.compare(keyExtractor.applyAsInt(c1), keyExtractor.applyAsInt(c2));
   }

  public static <T> Comparator<T> comparingLong(ToLongFunction<? super T> keyExtractor) {
      Objects.requireNonNull(keyExtractor);
      return (Comparator<T> & Serializable)
          (c1, c2) -> Long.compare(keyExtractor.applyAsLong(c1), keyExtractor.applyAsLong(c2));
  }


  public static<T> Comparator<T> comparingDouble(ToDoubleFunction<? super T> keyExtractor) {
       Objects.requireNonNull(keyExtractor);
       return (Comparator<T> & Serializable)
           (c1, c2) -> Double.compare(keyExtractor.applyAsDouble(c1), keyExtractor.applyAsDouble(c2));
   }

}

解析

首先,Comparator的源码中出现了大量的

1	(Comparator<T> & Serializable)

这个表示强制类型转换为 Comparator 和 Serializable[1]

[1](Comparator & Serializable)

Java @FunctionalInterface Function

发表于 2018-10-23 更新于 2021-02-21

Java @FunctionalInterface Function

[TOC]

源码

@FunctionalInterface
public interface Function<T,R>{
  R apply(T t);

  default <V> Function<V,R> compose(Function<? extends V,? extends T> before){
    Objects.requireNonNull(before);
    return (V v)-> apply(before.apply);
  }


  default <V> Function<T,V> andThen(Function<? super R,? superOb V> after){
    Objects.requireNonNull(after);
    return (T t)-> after.apply(apply(t));
  }

  static <T> Function<T, T> identity(){ return t -> t;}
}

介绍

Function<T,R> ,这里我翻译一下api上的内容

Type Parameters

T 函数的输入类型
R 函数的输出类型

All Known Subinterface

UnaryOperator

Functional Interface

这是一个函数式接口,因此可以作为lambda表达式或者方法引用的赋值对象

方法

apply 实现执行处理
compose 构建一个新的Function, 将before的输出作为新Function的apply的输入,新apply的实现同当前
andThen 同理

java @FunctionalInterface UnaryOperator

发表于 2018-10-23 更新于 2021-02-21

Java @FunctionalInterface UnaryOperator

源码

@FunctionalInterface
public interface UnaryOperator<T> extends Function<T,T> {

  static <T> UnaryOperator<T> identity(){return t -> t;}

}

介绍

其实就是一个输入输出类型相同的Function<T,E>.此时T 同 E.

Java Interface List

发表于 2018-10-23 更新于 2021-02-21

List

实现了List接口的方法:

AbstractList, AbstractSequentialList, ArrayList, AttributeList, CopyOnWriteArrayList, LinkedList, RoleList, RoleUnresolvedList, Stack, Vector

解析

可以看到 List 继承了 Collection 接口.比起Collection而言List多了很多方法,同时还重写了Spliterator方法.以及默认实现了部分方法.

默认实现的方法
- replaceAll
- sort
没有实现的方法
- 很多很多

下面先看一看已经默认实现了的方法

replaceAll

可以看到,replaceAll的实现方式是:

传入一个UnaryOperator
调用this.listIterator();
如果迭代器有下一个元素
- 将下一个元素的值赋值为UnaryOperator.apply的结果
如果没有
- 结束

使用demo

public class Main {

    public static void main(String[] args){

        List list = new ArrayList<Integer>();
        for(int i = 0; i < 10 ; i++){
            list.add(i);
        }


        for(int i =0 ; i < list.size();i++){
            System.out.print(list.get(i));
        }

        System.out.println();

        list.replaceAll(new UnaryOperator<Integer>() {
            @Override
            public Integer apply(Integer integer) {
                return integer <= 4 ? integer : 4;
            }
        });

        for(int i =0 ; i < list.size();i++){
            System.out.print(list.get(i));
        }

        System.out.println();
    }


}

输出结果

1 2	0123456789 0123444444

用lambda表达式

1	list.replaceAll(o -> (Integer) o > 4? 4:o);

结果一样

sort

default void sort(Comparator<? extends 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 );
  }
}


``` java
  public interface List<E> extends Collection<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 addAll(int index, Collection<? extends E> c);

    boolean removeAll(Collection<?> c);

    boolean retainAll(Collection<?> 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()));
      }
    }

    default void sort(Comparator<? extends 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 );
      }
    }

    void clear();

    boolean equals(Object o);

    int hashCode();

    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转换成数组
- 然后通过Arrays的静态方法传入数组和Comparator进行排序
- 获取迭代器,调用迭代器的next(),set()方法按序赋值

### Arrays

是一个工具类,包含了控制数组的各个方法