Rumah > Java > javaTutorial > Penjelasan terperinci tentang penggunaan PriorityBlockingQueue dalam pengaturcaraan serentak Java

Penjelasan terperinci tentang penggunaan PriorityBlockingQueue dalam pengaturcaraan serentak Java

王林
Lepaskan: 2023-05-08 08:43:07
ke hadapan
1434 orang telah melayarinya

    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;
    Salin selepas log masuk

    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;
    Salin selepas log masuk

    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;
    }
    Salin selepas log masuk

    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; 
    }
    Salin selepas log masuk

    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; 
    }
    Salin selepas log masuk

    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; 
    }
    Salin selepas log masuk

    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!

    Label berkaitan:
    Kenyataan Laman Web ini
    Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
    Isu terkini
    Bolehkah java digunakan sebagai bahagian belakang web?
    daripada 1970-01-01 08:00:00
    0
    0
    0
    Tidak dapat memasang java
    daripada 1970-01-01 08:00:00
    0
    0
    0
    Pasang JAVA
    daripada 1970-01-01 08:00:00
    0
    0
    0
    Bagaimanakah php melaksanakan penyulitan sha1 java?
    daripada 1970-01-01 08:00:00
    0
    0
    0
    Tutorial Popular
    Lagi>
    Muat turun terkini
    Lagi>
    kesan web
    Kod sumber laman web
    Bahan laman web
    Templat hujung hadapan