Detaillierte Erläuterung der Verwendung von PriorityBlockingQueue in der gleichzeitigen Java-Programmierung

PriorityBlockingQueue ist eine threadsichere begrenzte Blockierungswarteschlange, die eine Heap-Datenstruktur in Java implementiert. Es kann Elemente in Multithread-Szenarien sicher hinzufügen, löschen und abrufen und Elemente nach ihrer Priorität sortieren.

1. Übersicht über PriorityBlockingQueue

Die PriorityBlockingQueue-Klasse implementiert die BlockingQueue-Schnittstelle. Es handelt sich um eine threadsichere Warteschlange, die von der AbstractQueue-Klasse erbt, die wiederum die Queue-Schnittstelle implementiert. PriorityBlockingQueue ist eine begrenzte Warteschlange, deren Kapazität im Konstruktor angegeben werden kann. Wenn nicht angegeben, ist die Standardgröße Integer.MAX_VALUE. Gleichzeitig unterstützt PriorityBlockingQueue auch die Sortierung nach der Priorität von Elementen. Dies liegt daran, dass PriorityBlockingQueue intern eine Heap-Datenstruktur implementiert.

2. PriorityBlockingQueue-Quellcode-Analyse

PriorityBlockingQueue verwendet intern eine Array-Warteschlange vom Typ Object zum Speichern von Elementen und verwendet eine Variablengröße vom Typ int, um die Anzahl der Elemente aufzuzeichnen. Das Folgende ist die Definition in der PriorityBlockingQueue-Klasse:

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

2. Comparator

PriorityBlockingQueue kann nach der Priorität der Elemente sortiert werden, da PriorityBlockingQueue intern einen kleinen oder großen Root-Heap verwaltet. Im Konstruktor können wir wählen, ob wir zum Sortieren der Elemente die eigene Vergleichsmethode des Elements oder einen benutzerdefinierten Komparator verwenden möchten. Wenn kein Komparator angegeben ist, verwendet PriorityBlockingQueue die eigene Vergleichsmethode des Elements zum Sortieren.

private final Comparator<? super E> comparator;

3. PriorityBlockingQueue bietet mehrere Konstruktoren, um einen PriorityBlockingQueue mit einer Standardkapazität von Integer.MAX_VALUE zu erstellen, oder einen mit der Anfangskapazität oder einen benutzerdefinierten Konstruktor. Im Folgenden sind die beiden Konstruktoren der PriorityBlockingQueue-Klasse aufgeführt:

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. Die Methode zum Hinzufügen von Elementen in PriorityBlockingQueue ist die Methode offer(). Sie prüft zunächst, ob die Kapazität ausreicht. Die Kapazität wird erweitert. Die Methode besteht darin, die Länge des ursprünglichen Arrays um die Hälfte zu erhöhen. Anschließend fügt es das neue Element am Ende der Warteschlange hinzu und filtert das Element mithilfe der siftUp()-Methode an die entsprechende Position, um die Eigenschaften des Heaps beizubehalten.

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. Elemente abrufen Die Methode zum Abrufen von Elementen in PriorityBlockingQueue prüft zunächst, ob die Warteschlange leer ist, und der aktuelle Thread wird blockiert, bis ein Element hinzugefügt wird in die Warteschlange. Anschließend wird das Kopfelement der Warteschlange abgerufen und das letzte Element der Warteschlange über die Methode siftDown() an den Kopf verschoben, um die Eigenschaften des Heaps beizubehalten.

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. Heap-Eigenschaften beibehalten

PriorityBlockingQueue verwendet einen kleinen Root-Heap oder einen großen Root-Heap, um die Priorität von Elementen aufrechtzuerhalten. Das Merkmal des kleinen Root-Heaps besteht darin, dass der Wert des übergeordneten Knotens kleiner oder gleich dem Wert des linken und rechten untergeordneten Knotens ist. Der Heap in PriorityBlockingQueue wird über ein Array implementiert. Wenn ein Element hinzugefügt wird, wird das neue Element am Ende der Warteschlange hinzugefügt und durch die Methode siftUp() an die entsprechende Position gefiltert, um die Eigenschaften des Heaps beizubehalten. Wenn ein Element abgerufen wird, wird das Kopfelement der Warteschlange abgerufen und das Endelement der Warteschlange wird über die Methode siftDown () an den Kopf verschoben, um die Art des Heaps beizubehalten. Das Folgende ist die Code-Implementierung der Methoden siftUp() und 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; 
}

Die Methoden siftUp() und siftDown() verwenden beide die Methode siftUpUsingComparator() und die Methode siftDownUsingComparator(), die Comparator verwenden, um Heap-Filterung und Filtered zu implementieren runter. Wenn PriorityBlockingQueue keinen Comparator angibt, wird das eigene Comparable des Elements verwendet, um die obere und untere Filterung des Heaps zu implementieren.

Das obige ist der detaillierte Inhalt vonDetaillierte Erläuterung der Verwendung von PriorityBlockingQueue in der gleichzeitigen Java-Programmierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!