PriorityBlockingQueue は、Java でヒープ データ構造を実装する、スレッドセーフな境界付きブロッキング キューです。マルチスレッドのシナリオで要素を安全に追加、削除、取得でき、優先度に従って要素を並べ替えることができます。
PriorityBlockingQueue クラスは BlockingQueue インターフェイスを実装しており、AbstractQueue クラスを継承するスレッドセーフ キューであり、AbstractQueue クラスが Queue インターフェイスを実装します。 PriorityBlockingQueue は、コンストラクターで容量を指定できる有界キューです。指定しない場合、デフォルトのサイズは Integer.MAX_VALUE です。同時に、PriorityBlockingQueue は内部的にヒープ データ構造を実装しているため、要素の優先順位に応じたソートもサポートしています。
PriorityBlockingQueue は内部的にオブジェクト型の配列キューを使用して要素を格納し、また int 型の変数サイズを使用して要素を格納します. 要素の数を記録します。以下は、PriorityBlockingQueue クラスの定義です:
private transient Object[] queue; private transient int size;
PriorityBlockingQueue は、要素の優先順位に従って並べ替えることができます。これは、PriorityBlockingQueue が小さなルート ヒープまたは大きなルートを維持するためです。内部的にヒープします。コンストラクターでは、要素の並べ替えに要素独自の比較メソッドまたはカスタム コンパレーターの使用を選択できます。コンパレータが指定されていない場合、PriorityBlockingQueue は並べ替えに要素独自の比較方法を使用します。
private final Comparator<? super E> comparator;
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; }
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; }
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; }
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 サイトの他の関連記事を参照してください。