Java 동시 프로그래밍에서 PriorityBlockingQueue 사용에 대한 자세한 설명

PriorityBlockingQueue는 Java에서 힙 데이터 구조를 구현하는 스레드로부터 안전한 경계 차단 큐입니다. 다중 스레드 시나리오에서 요소를 안전하게 추가, 삭제 및 얻을 수 있으며 우선 순위에 따라 요소를 정렬할 수 있습니다.

1. PriorityBlockingQueue 개요

PriorityBlockingQueue 클래스는 BlockingQueue 인터페이스를 구현하며 AbstractQueue 클래스에서 상속되어 Queue 인터페이스를 구현합니다. PriorityBlockingQueue는 생성자에서 용량을 지정할 수 있는 제한된 큐입니다. 지정하지 않은 경우 기본 크기는 Integer.MAX_VALUE입니다. 동시에 PriorityBlockingQueue는 요소의 우선순위에 따른 정렬도 지원합니다. 이는 PriorityBlockingQueue가 내부적으로 힙 데이터 구조를 구현하기 때문입니다.

2. PriorityBlockingQueue 소스 코드 분석

1. Container

PriorityBlockingQueue는 내부적으로 Object 유형의 배열 큐를 사용하여 요소를 저장하고 int 유형의 변수 크기를 사용하여 요소 수를 기록합니다. 다음은 PriorityBlockingQueue 클래스의 정의입니다.

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

2. Comparator

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를 사용하여 힙 필터링 및 Filtered를 구현합니다. 아래에. PriorityBlockingQueue가 Comparator를 지정하지 않으면 요소 자체의 Comparable을 사용하여 힙의 상위 및 하위 필터링을 구현합니다.

위 내용은 Java 동시 프로그래밍에서 PriorityBlockingQueue 사용에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!