なぜCollections.synchronizedList（list）は内部的にinstanceofチェックを使用していますか？

Question

クラスのソースコードをチェックしています。 私はリストがランダム・タイプのものであるならば、我々がチェックしている理由をundestandに失敗し

public static <T> List<T> synchronizedList(List<T> list) { 
    return (list instanceof RandomAccess ? 
      new SynchronizedRandomAccessList<>(list) : 
      new SynchronizedList<>(list)); 
} 

方法Collections.synchronizedList（リスト）に出くわしました。 ArrayListはこのインターフェイスを実装しており、LinkedListは実装していないことを理解しています。

はまた、SynchronizedRandomAccessListはSynchronizedListを継承します。 このチェックのポイントは何ですか？ 説明してください

Answer 1

あなたはほとんどあります。 Collections.synchronizedList(list)はRandomAccessをチェックします。リストの中にはRandomAccessが実装されているものもあれば、そうでないものもあります。

このRandomAccessは、のように、marker interfaceです。それは、リスト内の項目にランダムにアクセスできるかどうかを示します。私。 ArrayListから、同じ計算コストを持つアイテムをすべて取り出すことができます。一方、n番目の要素に到達するには、LinkedListを通過する必要があります。

だから、Collections.synchronizedList(list)ではどうなりますか？ RandomAccessList -sをRandomAccess同期リストにラップし、RandomAccessリストを非同期リストRandomAccessにラップします。そうでなければ、それらのリストは同一です。以下はSynchronizedRandomAccessListのコードです。これは、programming by differenceの良い例です。 2つのクラスはほぼ同じです。

static class SynchronizedRandomAccessList<E> 
    extends SynchronizedList<E> 
    implements RandomAccess { 

    SynchronizedRandomAccessList(List<E> list) { 
     super(list); 
    } 

    SynchronizedRandomAccessList(List<E> list, Object mutex) { 
     super(list, mutex); 
    } 

    public List<E> subList(int fromIndex, int toIndex) { 
     synchronized (mutex) { 
      return new SynchronizedRandomAccessList<>(
       list.subList(fromIndex, toIndex), mutex); 
     } 
    } 

    private static final long serialVersionUID = 1530674583602358482L; 

    /** 
    * Allows instances to be deserialized in pre-1.4 JREs (which do 
    * not have SynchronizedRandomAccessList). SynchronizedList has 
    * a readResolve method that inverts this transformation upon 
    * deserialization. 
    */ 
    private Object writeReplace() { 
     return new SynchronizedList<>(list); 
    } 
} 

RandomAccessインターフェイスのポイントは何ですか？ Holgerが指摘しているように、Collections.binarySearch()はこのインターフェイスに基づいて決定を下します。別の例はCollections.reverse()です。

Answer 2

RandomAccessマーカーインターフェイスの元の目的を思い出す必要があります。別の方法にListを渡す場合、ランダムアクセスまたはシーケンシャルリストに適したアルゴリズムを選択できる必要があります。適切なアルゴリズムを選択するには、list instanceof RandomAccessを介してマーカーインターフェイスのテストが必要です。あなただけのListインタフェースを実装する別のオブジェクトにリストをラップすると、すべてのそのような方法は、参照、今

（もreverse、shuffle、copy、およびfillを参照してください）one example

public static <T> 
int binarySearch(List<? extends Comparable<? super T>> list, T key) { 
    if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD) 
     return Collections.indexedBinarySearch(list, key); 
    else 
     return Collections.iteratorBinarySearch(list, key); 
} 

を表示するには

がラッパーオブジェクトであるため、この情報は失われます。しかし、同期リストのようなラッパーは、getのようなランダムアクセスメソッドの時間の複雑さを変更しません。したがって、ラップされたリストがランダムアクセスリストである場合、ラッパーはRandomAccessも実装する必要があるため、そのようなラッパーを受信するメソッドは高速ランダムアクセスが使用可能かどうかを検出できます。

あなたはimplementation of SynchronizedRandomAccessListを見れば、あなたはそれがないすべては、SynchronizedListを拡張し、動作を継承するために、RandomAccess実装し、高速なランダムアクセスを持つものとして自分自身をマーキングされていることがわかります。オーバーライドする唯一の方法は、まったく同じ理由でsubListです。リストに効率的なランダムアクセスがある場合、そのサブリストも同様に実装されるので、RandomAccessも実装する必要があります。

static class SynchronizedRandomAccessList<E> 
    extends SynchronizedList<E> 
    implements RandomAccess { 

    SynchronizedRandomAccessList(List<E> list) { 
     super(list); 
    } 

    SynchronizedRandomAccessList(List<E> list, Object mutex) { 
     super(list, mutex); 
    } 

    public List<E> subList(int fromIndex, int toIndex) { 
     synchronized (mutex) { 
      return new SynchronizedRandomAccessList<>(
       list.subList(fromIndex, toIndex), mutex); 
     } 
    } 

checkedListのような他のラッパーファクトリは同じパターンに従います。だから、工場を組み合わせたときに、これはでも動作します：

System.out.println(
    Collections.synchronizedList(Collections.checkedList(new ArrayList<>(), String.class)) 
    instanceof RandomAccess); 

→真

System.out.println(
    Collections.synchronizedList(Collections.checkedList(new LinkedList<>(), String.class)) 
    instanceof RandomAccess); 

偽