Penjelasan terperinci tentang penggunaan PriorityBlockingQueue dalam pengaturcaraan serentak Java

PriorityBlockingQueue ialah baris gilir sekatan sempadan selamat benang yang melaksanakan struktur data timbunan dalam Java. Ia boleh menambah, memadam dan mendapatkan elemen dalam senario berbilang benang dengan selamat dan boleh mengisih elemen mengikut keutamaannya.

1. Gambaran Keseluruhan PriorityBlockingQueue

Kelas PriorityBlockingQueue melaksanakan antara muka BlockingQueue Ia adalah baris gilir selamat benang yang mewarisi daripada kelas AbstractQueue, yang seterusnya melaksanakan antara muka Queue. PriorityBlockingQueue ialah baris gilir terikat yang kapasitinya boleh ditentukan dalam pembina. Jika tidak dinyatakan, saiz lalai ialah Integer.MAX_VALUE. Pada masa yang sama, PriorityBlockingQueue juga menyokong pengisihan mengikut keutamaan elemen Ini kerana PriorityBlockingQueue melaksanakan struktur data timbunan secara dalaman.

2. Analisis kod sumber PriorityBlockingQueue

1 Container

PriorityBlockingQueue secara dalaman menggunakan baris gilir jenis Objek untuk menyimpan elemen, dan juga menggunakan saiz pembolehubah jenis int untuk menyimpan elemen. Rekod bilangan elemen. Berikut ialah definisi dalam kelas PriorityBlockingQueue:

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

2. Comparator

PriorityBlockingQueue boleh mengisih mengikut keutamaan elemen Ini kerana PriorityBlockingQueue mengekalkan timbunan akar kecil atau besar secara dalaman. Dalam pembina, kita boleh memilih untuk menggunakan kaedah perbandingan elemen sendiri atau pembanding tersuai untuk mengisih elemen. Jika tiada pembanding dinyatakan, PriorityBlockingQueue akan menggunakan kaedah perbandingan elemen itu sendiri untuk mengisih.

private final Comparator<? super E> comparator;

3. Constructor

PriorityBlockingQueue menyediakan berbilang pembina Kita boleh memilih untuk menggunakan pembina tanpa parameter untuk mencipta PriorityBlockingQueue dengan kapasiti lalai Integer.MAX_VALUE, atau menggunakannya dengan Constructor untuk kapasiti awal. atau pembanding tersuai. Berikut ialah dua pembina kelas 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 Tambah elemen

Kaedah untuk menambah elemen dalam PriorityBlockingQueue ialah kaedah offer() terlebih dahulu mencukupi. Jika kapasiti tidak mencukupi Maka operasi pengembangan akan dilakukan. Kemudian, ia menambah elemen baharu pada penghujung baris gilir dan menapis elemen ke kedudukan yang sesuai melalui kaedah siftUp() untuk mengekalkan sifat timbunan.

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 Dapatkan elemen

Kaedah untuk mendapatkan elemen dalam PriorityBlockingQueue ialah kaedah take() Ia akan menyemak sama ada baris gilir kosong, urutan semasa akan disekat sehingga Satu elemen ditambahkan pada baris gilir. Kemudian, ia akan mendapat elemen kepala baris gilir dan memindahkan elemen terakhir baris gilir ke kepala melalui kaedah siftDown() untuk mengekalkan sifat timbunan.

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. Kekalkan sifat timbunan

PriorityBlockingQueue menggunakan timbunan akar yang kecil atau timbunan akar yang besar untuk mengekalkan keutamaan elemen Di sini kita mengambil timbunan akar yang kecil sebagai contoh. Ciri timbunan akar kecil ialah nilai nod induk adalah kurang daripada atau sama dengan nilai nod anak kiri dan kanan Timbunan dalam PriorityBlockingQueue dilaksanakan melalui tatasusunan. Apabila elemen ditambah, elemen baharu ditambahkan pada penghujung baris gilir dan ditapis sehingga ke kedudukan yang sesuai melalui kaedah siftUp() untuk mengekalkan sifat timbunan. Apabila elemen diperolehi, elemen kepala baris gilir diperoleh, dan elemen akhir baris gilir dipindahkan ke kepala melalui kaedah siftDown() untuk mengekalkan sifat timbunan. Berikut ialah pelaksanaan kod kaedah siftUp() dan 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; 
}

kaedah siftUp() dan kaedah siftDown() kedua-duanya menggunakan kaedah siftUpUsingComparator() dan kaedah siftDownUsingComparator(), yang menggunakan Comparator untuk melaksanakan timbunan Penapis atas dan penapis bawah. Apabila PriorityBlockingQueue tidak menentukan Comparator, Comparable elemen itu sendiri akan digunakan untuk melaksanakan penapisan atas dan bawah timbunan.

Atas ialah kandungan terperinci Penjelasan terperinci tentang penggunaan PriorityBlockingQueue dalam pengaturcaraan serentak Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!