Java並發程式設計中PriorityBlockingQueue的使用方法詳解

PriorityBlockingQueue是Java中實作了堆疊資料結構的執行緒安全的有界阻塞佇列。它可以在多執行緒場景下安全地進行元素新增、刪除和取得操作，並且可以根據元素的優先順序進行排序。

一、PriorityBlockingQueue概述

PriorityBlockingQueue類實作了BlockingQueue接口，它是一個執行緒安全的佇列，繼承自AbstractQueue類，而AbstractQueue類又實作了Queue介面。 PriorityBlockingQueue是一個有界的佇列，其容量可以在建構函式中進行指定，若不指定則預設大小為Integer.MAX_VALUE。同時，PriorityBlockingQueue也支援根據元素的優先權進行排序，這是由於PriorityBlockingQueue內部實作了一個堆疊資料結構。

二、PriorityBlockingQueue原始碼解析

1.容器

PriorityBlockingQueue內部使用了一個Object類型的陣列queue來儲存元素，同時使用了一個int型別的變數。記錄元素的數量。以下是PriorityBlockingQueue類別中的定義：

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

2.比較器

PriorityBlockingQueue可以根據元素的優先權進行排序，這是由於PriorityBlockingQueue內部維護了一個小根堆或大根堆。在建構函數中，我們可以選擇使用元素本身的比較方式或自訂比較器來進行元素的排序。若未指定比較器，則PriorityBlockingQueue將使用元素本身的比較方式進行排序。

private final Comparator<? super E> comparator;

3.建構子

PriorityBlockingQueue提供了多個建構函數，我們可以選擇使用無參構造函數來建立一個預設容量為Integer.MAX_VALUE的PriorityBlockingQueue，或使用帶有初始容量或自訂比較器的建構函數。以下是PriorityBlockingQueue類別的兩個建構子：

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()方法，它們是使用Comparator來實作堆的上濾和下濾的。當PriorityBlockingQueue沒有指定Comparator時，會使用元素本身的Comparable來實現堆的上濾與下濾。

以上是Java並發程式設計中PriorityBlockingQueue的使用方法詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章！