Java 並行プログラミングでの PriorityBlockingQueue の使用方法の詳細な説明

PriorityBlockingQueue は、Java でヒープ データ構造を実装する、スレッドセーフな境界付きブロッキング キューです。マルチスレッドのシナリオで要素を安全に追加、削除、取得でき、優先度に従って要素を並べ替えることができます。

1. PriorityBlockingQueue の概要

PriorityBlockingQueue クラスは BlockingQueue インターフェイスを実装しており、AbstractQueue クラスを継承するスレッドセーフ キューであり、AbstractQueue クラスが Queue インターフェイスを実装します。 PriorityBlockingQueue は、コンストラクターで容量を指定できる有界キューです。指定しない場合、デフォルトのサイズは Integer.MAX_VALUE です。同時に、PriorityBlockingQueue は内部的にヒープ データ構造を実装しているため、要素の優先順位に応じたソートもサポートしています。

2. PriorityBlockingQueue のソースコード分析

1. コンテナ

PriorityBlockingQueue は内部的にオブジェクト型の配列キューを使用して要素を格納し、また int 型の変数サイズを使用して要素を格納します. 要素の数を記録します。以下は、PriorityBlockingQueue クラスの定義です:

private transient Object[] queue;
private transient int size;

2. Comparator

PriorityBlockingQueue は、要素の優先順位に従って並べ替えることができます。これは、PriorityBlockingQueue が小さなルート ヒープまたは大きなルートを維持するためです。内部的にヒープします。コンストラクターでは、要素の並べ替えに要素独自の比較メソッドまたはカスタム コンパレーターの使用を選択できます。コンパレータが指定されていない場合、PriorityBlockingQueue は並べ替えに要素独自の比較方法を使用します。

private final Comparator<? super E> comparator;

3. コンストラクター

PriorityBlockingQueue は複数のコンストラクターを提供します。パラメーターなしのコンストラクターを使用して、デフォルトの容量 Integer.MAX_VALUE を持つ PriorityBlockingQueue を作成するか、初期容量のコンストラクターと一緒に使用するかを選択できます。またはカスタムコンパレータ。以下は、PriorityBlockingQueue クラスの 2 つのコンストラクターです:

public PriorityBlockingQueue() {
    this(DEFAULT_INITIAL_CAPACITY, null);
}
public PriorityBlockingQueue(int initialCapacity, Comparator<? super E> comparator) {
    if (initialCapacity < 1)
        throw new IllegalArgumentException();
    this.queue = new Object[initialCapacity];
    this.comparator = comparator;
}

4. 要素の追加

PriorityBlockingQueue に要素を追加するメソッドは、offer() メソッドです。最初に、容量が十分であるかどうかを確認します。容量が足りない場合は、元の配列の長さを半分にする拡張操作が実行されます。次に、新しい要素をキューの最後に追加し、siftUp() メソッドを通じて要素を適切な位置にフィルタリングして、ヒープのプロパティを維持します。

public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();
    final ReentrantLock lock = this.lock;
    lock.lock();
    int n, cap;
    Object[] array;
    while ((n = size) >= (cap = (array = queue).length))
        tryGrow(array, cap);
    try {
        Comparator<? super E> cmp = comparator; 
        if (n == 0) { array[0] = e; } 
        else { siftUp(n, e, array, cmp); } 
        size = n + 1; notEmpty.signal(); 
    } finally { 
        lock.unlock(); 
    } 
    return true; 
}

5. 要素の取得

PriorityBlockingQueue の要素を取得するメソッドは take() メソッドです。最初にキューが空かどうかがチェックされます。キューが空の場合は、現在のスレッドが要素がキューに追加されるまでブロックされます。次に、キューの先頭要素を取得し、 siftDown() メソッドを通じてキューの最後の要素を先頭に移動して、ヒープのプロパティを維持します。

public E take() throws InterruptedException { 
    final ReentrantLock lock = this.lock; 
    lock.lockInterruptibly(); 
    E result; 
    try { 
        while (size == 0) notEmpty.await(); 
        result = extract(); 
    } finally {
        lock.unlock(); 
    } 
    return result; 
}
private E extract() { 
    final Object[] array = queue; 
    final E result = (E) array[0]; 
    final int n = --size; 
    final E x = (E) array[n]; 
    array[n] = null; 
    if (n != 0) 
    siftDown(0, x, array, comparator); 
    return result; 
}

6. ヒープ プロパティの維持

PriorityBlockingQueue は、要素の優先順位を維持するために小さなルート ヒープまたは大きなルート ヒープを使用します。ここでは例として小さなルート ヒープを取り上げます。小さなルート ヒープの特徴は、親ノードの値が左右の子ノードの値以下であることです。PriorityBlockingQueue のヒープは配列を通じて実装されます。要素が追加されると、新しい要素はキューの最後に追加され、ヒープのプロパティを維持するために siftUp() メソッドを通じて適切な位置までフィルタリングされます。要素を取得するとキューの先頭要素が取得され、ヒープの性質を維持するために siftDown() メソッドによってキューの末尾要素が先頭に移動されます。以下は、siftUp() メソッドと siftDown() メソッドのコード実装です。

private static <T> 
void siftUp(int k, T x, Object[] array, Comparator<? super T> cmp) { 
    if (cmp != null) 
    siftUpUsingComparator(k, x, array, cmp); 
    else siftUpComparable(k, x, array); 
}
@SuppressWarnings("unchecked") 
private static <T> 
void siftUpUsingComparator(int k, T x, Object[] array, Comparator<? super T> cmp) { 
    while (k > 0) { 
        int parent = (k - 1) >>> 1; 
        Object e = array[parent]; 
        if (cmp.compare(x, (T) e) >= 0) 
        break; 
        array[k] = e; 
        k = parent; 
    } 
    array[k] = x; 
}
@SuppressWarnings("unchecked") 
private static <T> 
void siftUpComparable(int k, T x, Object[] array) { 
    Comparable<? super T> key = (Comparable<? super T>) x; 
    while (k > 0) { 
        int parent = (k - 1) >>> 1; 
        Object e = array[parent]; 
        if (key.compareTo((T) e) >= 0) 
        break; 
        array[k] = e; 
        k = parent; 
    } 
    array[k] = key; 
}
private static <T> 
void siftDown(int k, T x, Object[] array, Comparator<? super T> cmp) { 
    if (cmp != null) 
    siftDownUsingComparator(k, x, array, cmp); 
    else siftDownComparable(k, x, array); 
}
@SuppressWarnings("unchecked") 
private static <T> 
void siftDownUsingComparator(int k, T x, Object[] array, Comparator<? super T> cmp) { 
    int half = size >>> 1; 
    while (k < half) { 
        int child = (k << 1) + 1; 
        Object c = array[child]; 
        int right = child + 1; 
        if (right < size && cmp.compare((T) c, (T) array[right]) > 0) 
        c = array[child = right]; 
        if (cmp.compare(x, (T) c) <= 0) 
        break; 
        array[k] = c; 
        k = child; 
    } 
    array[k] = x; 
}
@SuppressWarnings("unchecked") 
private static <T> 
void siftDownComparable(int k, T x, Object[] array) { 
    Comparable<? super T> key = (Comparable<? super T>) x; 
    int half = size >>> 1; 
    while (k < half) { 
        int child = (k << 1) + 1; 
        Object c = array[child]; 
        int right = child + 1; 
        if (right < size && ((Comparable<? super T>) c).compareTo((T) array[right]) > 0) 
        c = array[child = right]; 
        if (key.compareTo((T) c) <= 0) 
        break; 
        array[k] = c; 
        k = child; 
    } 
    array[k] = key; 
}

siftUp() メソッドと siftDown() メソッドはどちらも siftUpUsingComparator() メソッドと siftDownUsingComparator() メソッドを使用します。ヒープの上部フィルターと下部フィルターを実装します。 PriorityBlockingQueue が Comparator を指定しない場合、要素自体の Comparable を使用してヒープの上位および下位のフィルタリングが実装されます。

以上がJava 並行プログラミングでの PriorityBlockingQueue の使用方法の詳細な説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。