Explication détaillée de l'utilisation de PriorityBlockingQueue dans la programmation simultanée Java

PriorityBlockingQueue est une file d'attente de blocage limitée thread-safe qui implémente une structure de données de tas en Java. Il peut ajouter, supprimer et obtenir des éléments en toute sécurité dans des scénarios multithread, et trier les éléments en fonction de leur priorité.

1. Présentation de PriorityBlockingQueue

La classe PriorityBlockingQueue implémente l'interface BlockingQueue. Il s'agit d'une file d'attente thread-safe qui hérite de la classe AbstractQueue, qui à son tour implémente l'interface Queue. PriorityBlockingQueue est une file d'attente limitée dont la capacité peut être spécifiée dans le constructeur. Si elle n'est pas spécifiée, la taille par défaut est Integer.MAX_VALUE. Dans le même temps, PriorityBlockingQueue prend également en charge le tri en fonction de la priorité des éléments, car PriorityBlockingQueue implémente une structure de données en tas en interne.

2. Analyse du code source de PriorityBlockingQueue

1. Container

PriorityBlockingQueue utilise en interne une file d'attente de tableau de type objet pour stocker les éléments et utilise une taille de variable de type int pour enregistrer le nombre d'éléments. Voici la définition de la classe PriorityBlockingQueue :

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

2. Comparateur

PriorityBlockingQueue peut être trié en fonction de la priorité des éléments. En effet, PriorityBlockingQueue maintient un tas racine petit ou grand en interne. Dans le constructeur, nous pouvons choisir d'utiliser la propre méthode de comparaison de l'élément ou un comparateur personnalisé pour trier les éléments. Si aucun comparateur n'est spécifié, PriorityBlockingQueue utilisera la propre méthode de comparaison de l'élément pour le tri.

private final Comparator<? super E> comparator;

3. Constructor

PriorityBlockingQueue fournit plusieurs constructeurs. Nous pouvons choisir d'utiliser le constructeur sans argument pour créer une PriorityBlockingQueue avec une capacité par défaut de Integer.MAX_VALUE, ou d'en utiliser un avec une capacité initiale ou un comparateur personnalisé. Voici les deux constructeurs de la classe 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. Ajouter des éléments

La méthode d'ajout d'éléments dans PriorityBlockingQueue est la méthode offer(). Elle vérifiera d'abord si la capacité est suffisante. la capacité sera étendue. La méthode consiste à augmenter la longueur du réseau d’origine de moitié. Ensuite, il ajoutera le nouvel élément à la fin de la file d'attente et filtrera l'élément jusqu'à la position appropriée via la méthode siftUp() pour conserver les propriétés du tas.

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. Obtenir des éléments

La méthode pour obtenir des éléments dans PriorityBlockingQueue est la méthode take(). Elle vérifiera d'abord si la file d'attente est vide, le thread actuel sera bloqué jusqu'à ce qu'un élément soit ajouté. à la file d'attente. Ensuite, il obtiendra l'élément de tête de la file d'attente et déplacera le dernier élément de la file d'attente vers la tête via la méthode siftDown() pour conserver les propriétés du tas.

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. Conserver les propriétés du tas

PriorityBlockingQueue utilise un petit tas racine ou un grand tas racine pour maintenir la priorité des éléments. Ici, nous prenons le petit tas racine comme exemple. La caractéristique du petit tas racine est que la valeur du nœud parent est inférieure ou égale à la valeur des nœuds enfants gauche et droit. Le tas dans PriorityBlockingQueue est implémenté via un tableau. Lorsqu'un élément est ajouté, le nouvel élément est ajouté à la fin de la file d'attente et filtré jusqu'à la position appropriée via la méthode siftUp() pour conserver les propriétés du tas. Lorsqu'un élément est obtenu, l'élément de tête de la file d'attente est obtenu et l'élément de fin de la file d'attente est déplacé vers la tête via la méthode siftDown() pour conserver la nature du tas. Voici l'implémentation du code des méthodes siftUp() et 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; 
}

La méthode siftUp() et la méthode siftDown() utilisent toutes deux la méthode siftUpUsingComparator() et la méthode siftDownUsingComparator(), qui utilisent Comparator pour implémenter le filtrage de tas et Filtered. vers le bas. Lorsque PriorityBlockingQueue ne spécifie pas de Comparator, le propre Comparable de l'élément sera utilisé pour implémenter le filtrage supérieur et inférieur du tas.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!