Spliterator是java8新增的接口,意思為分割器或者分離器,作用是周遊元素或者将資料源的資料分割成幾個部分。
Spliterator的實作類非常多,這也展現了該接口的重要性。下圖Stream中比較重要的幾個類的繼承體系:
綠框表示實作類,藍框表示接口。
因為Integer、Long、Double比較特殊且常用,是以單獨提供了Spliterator的實作類,不過原理與類ArraySpliterator都是一樣的。
上圖中Spliterator的直接實作類分為四個,主要原因是它們的資料源不同。
- ArraySpliterator:資料源為數組;
- IteratorSpliterator:資料源為疊代器;
- ConcatSpliterator:資料源為Spliterator,該類的作用是将兩個Spliterator拼接成一個Spliterator;
- InfiniteSupplyingSpliterator:資料源為生成函數。
除了上面這些實作類之外,java8還提供了工具類Spliterators,ArraySpliterator和IteratorSpliterator就是在該類中定義的,類中提供了建立ArraySpliterator對象和IteratorSpliterator對象的方法。
接下來,本文首先介紹Spliterator接口中各個方法作用及特征值,然後介紹Spliterator與Iterator接口的差別,最後介紹上面這四個實作類的原理。
一、Spliterator接口
1、接口方法
下面是Spliterator接口中的方法:
public interface Spliterator<T> {
//嘗試讀取下一個元素,并使用action對象處理該元素
//如果元素已經周遊完,傳回false
boolean tryAdvance(Consumer<? super T> action);
//周遊資料源中剩餘的所有元素
default void forEachRemaining(Consumer<? super T> action) {
do { } while (tryAdvance(action));
}
//對元素進行拆分,被拆分出去的元素組成一個新的Spliterator對象,剩餘的元素
//還在目前Spliterator對象中
Spliterator<T> trySplit();
//計算所有元素的個數,
//如果無法計算、計算成本太高或者元素是無限的,那麼可以傳回Long.MAX_VALUE,
//否則傳回精确值
long estimateSize();
//傳回确切元素個數,如果無法計算,則傳回-1
default long getExactSizeIfKnown() {
return (characteristics() & SIZED) == 0 ? -1L : estimateSize();
}
//傳回目前Spliterator的特征值
int characteristics();
//檢查Spliterator是否有此特征
default boolean hasCharacteristics(int characteristics) {
return (characteristics() & characteristics) == characteristics;
}
//傳回比較器,當對元素排序時,會使用到比較器
default Comparator<? super T> getComparator() {
throw new IllegalStateException();
}
}
2、特征值
Spliterator還提供了一些靜态常量,它們是Spliterator的特征值,用于表示該Spliterator是否具有某種特征。
//表示資料源中元素的周遊順序(encounter order)是固定好的,不會發生改變,比如數組,
//forEachRemaining()方法也是按照這一順序周遊元素
//代碼注釋中稱這一順序為encounter order,
//我了解是目前元素的前一個元素和後一個元素在資料源中就已經定義好了,無論周遊還是拆分,它們之間的順序是不會發生改變的。
public static final int ORDERED = 0x00000010;
//表示資料源中的元素都是不相等的,
//也就是任意兩個元素下面表達式都傳回true:!x.equals(y)
public static final int DISTINCT = 0x00000001;
//表示資料源中的元素是有序的,
//如果具有該特征,getComparator()方法可以傳回相關的比較器對象,
//如果getComparator()方法傳回null,表示是按照自然序排序的
public static final int SORTED = 0x00000004;
//表示元素個數是可以精确計算的
public static final int SIZED = 0x00000040;
//表示不存在為null的元素
public static final int NONNULL = 0x00000100;
//表示在周遊的過程中,元素不可以新增、删除、替換
public static final int IMMUTABLE = 0x00000400;
//表示資料源中的元素可以被多線程并行的修改、替換、新增,而不需要外部的同步處理
public static final int CONCURRENT = 0x00001000;
//使用trySplit()拆分元素後形成的子Spliterator對象中的元素個數也是可以精确計算的
public static final int SUBSIZED = 0x00004000;
3、Spliterator與Iterator差別
兩個接口的作用都是周遊元素,不過Spliterator提供的功能更為豐富。
下面先看一下Iterator接口的方法都有哪些:
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());
}
}
下面介紹一下兩者之間的不同:
- 使用Iterator更常用的場景是從資料源中擷取元素,然後在外部對元素做更加複雜的加工處理,而Spliterator隻能使用Consumer處理,無法直接得到資料源中的元素,隻能由内部周遊;
- Iterator可以删除資料源中的元素,不過這個依賴于資料源的實作,有些資料源是不支援的;
- Spliterator可以得到元素個數,而Iterator不可以;
- Spliterator提供了很多特征值,可以直接獲知元素的特征;
- Spliterator提供了拆分方法,可以在并行流中使用。
二、實作類原理
本小節隻介紹實作類中trySplit()方法,其他的方法比較簡單不做介紹。
1、ArraySpliterator
該類的資料源為數組,預設特征值是Spliterator.SIZED | Spliterator.SUBSIZED。
下面看一下trySplit()方法:
public Spliterator<T> trySplit() {
//index表示目前已經周遊到的位置,如果還沒開始周遊,那麼index表示起始位置
//fence表示最後一個元素的位置+1
int lo = index, mid = (lo + fence) >>> 1;
return (lo >= mid)
? null
: new ArraySpliterator<>(array, lo, index = mid, characteristics);
}
從代碼中可以很明顯的看出,每調用一次trySplit()都是将元素平均的一分為二,将左半部分的元素建立一個ArraySpliterator對象。
2、IteratorSpliterator
該類的資料源為疊代器。
下面看一下trySplit()方法:
public Spliterator<T> trySplit() {
Iterator<? extends T> i;
long s;
if ((i = it) == null) {
i = it = collection.iterator();
s = est = (long) collection.size();
}
else
s = est;//est表示元素個數,可能是一個精确值,也可能是不精确的
if (s > 1 && i.hasNext()) {
//batch 初始值是0
int n = batch + BATCH_UNIT;//BATCH_UNIT = 1 << 10=1024
if (n > s)
n = (int) s;
if (n > MAX_BATCH)//MAX_BATCH = 1 << 25
n = MAX_BATCH;
Object[] a = new Object[n];
int j = 0;
do { a[j] = i.next(); } while (++j < n && i.hasNext());
batch = j;
if (est != Long.MAX_VALUE)
est -= j;
return new ArraySpliterator<>(a, 0, j, characteristics);
}
return null;
}
從代碼可以看出,如果元素足夠多,第一次拆分時,将BATCH_UNIT個元素拆分出來,第二次拆分,需要拆分出batch + BATCH_UNIT個元素,也就是2*BATCH_UNIT個元素,第三次拆分也是一樣。
這裡要注意,trySplit()傳回的是ArraySpliterator,我猜測這可能是為了性能的考慮。
3、ConcatSpliterator
該類的資料源為Spliterator。
ConcatSpliterator是将兩個Spliterator對象組合成一個,是以ConcatSpliterator提供了兩個屬性aSpliterator和bSpliterator,同時使用beforeSplit表示aSpliterator是否已經通路結束,如果為true,表示沒有。
public T_SPLITR trySplit() {
@SuppressWarnings("unchecked")
//beforeSplit為true,表示先通路aSpliterator
T_SPLITR ret = beforeSplit ? aSpliterator : (T_SPLITR) bSpliterator.trySplit();
beforeSplit = false;
return ret;
}
如果beforeSplit為true,那麼直接将aSpliterator傳回,作為拆分結果,之後的拆分,都是調用bSpliterator.trySplit()完成。
4、InfiniteSupplyingSpliterator
InfiniteSupplyingSpliterator是抽象類,它有四個實作類:OfRef、OfDouble、OfInt、OfLong,分别用于處理對象、Double、Integer、Long類型的元素。
InfiniteSupplyingSpliterator的資料源為生成函數,隻有一個特征值IMMUTABLE。它的trySplit()方法是在子類中實作的。下面以OfRef為例做介紹:
public Spliterator<T> trySplit() {
//estimate表示元素個數,一般情況下将其設定為Long.MAX_VALUE
if (estimate == 0)
return null;
//s表示生成函數
return new InfiniteSupplyingSpliterator.OfRef<>(estimate >>>= 1, s);
}
trySplit()方法沒有調用生成函數擷取元素的動作,隻是設定元素個數為目前剩餘元素的一半,然後建立一個OfRef對象。