JDK8 PriorityBlockingQueue(Collection＜? extends E＞c)구조 기 소스 코드 분석

머리말PriorityBlockingQueue 의 이 (Collection extends E> c) 리 로드 버 전 구조 기의 소스 코드 는 몇 가지 이해 하기 어렵 지만 본 고 는 내용 이 PriorityBlockingQueue 의 중점 적 인 이해 내용 이 아니 기 때문에 본 고 는 단독으로 설명 한다.

    public PriorityBlockingQueue(Collection<? extends E> c) {
        this.lock = new ReentrantLock();
        this.notEmpty = lock.newCondition();
        boolean heapify = true; //  true          
        boolean screen = true;  //  true          ，      null  （     null  ）
        if (c instanceof SortedSet<?>) {
            SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
            this.comparator = (Comparator<? super E>) ss.comparator();
            heapify = false;//SortedSet               ，        
        }
        else if (c instanceof PriorityBlockingQueue<?>) {
            PriorityBlockingQueue<? extends E> pq =
                (PriorityBlockingQueue<? extends E>) c;
            this.comparator = (Comparator<? super E>) pq.comparator();
            screen = false;//PriorityBlockingQueue     null  
            if (pq.getClass() == PriorityBlockingQueue.class) //    
                heapify = false;
        }
        Object[] a = c.toArray();
        int n = a.length;

        if (a.getClass() != Object[].class) //    
            a = Arrays.copyOf(a, n, Object[].class);
        if (screen && (n == 1 || this.comparator != null)) {//    
            for (int i = 0; i < n; ++i)
                if (a[i] == null)//    null  ，      
                    throw new NullPointerException();
        }
        this.queue = a;
        this.size = n;
        if (heapify)//  
            heapify();
    }

if (pq.getClass() == PriorityBlockingQueue.class),왜 유형 이 Priority BlockingQueue 자체 일 때 만 hepify 를 false 로 설정 할 수 있 습 니까?

if (a.getClass() != Object[].class).왜 배열 유형 이 Object[].class 이 아니라면 반드시 새로운 배열 을 복사 해 야 합 니까?설령 두 배열 의 모든 요소 가 똑 같 더 라 도?

if (screen && (n == 1 || this.comparator != null)),왜 뒤의 조건 을 (n == 1 || this.comparator != null) 으로 썼 습 니까?

if (pq.getClass() == PriorityBlockingQueue.class) c instanceof PriorityBlockingQueue> 은 c 가 Priority BlockingQueue 의 하위 클래스 임 을 증명 할 수 있 지만 c 의 실제 유형 이 Priority BlockingQueue 자체 일 때 만 c 의 내부 배열 이 논리 적 으로 이미 쌓 인 구조 임 을 설명 할 수 있 기 때문이다.Priority BlockingQueue 의 하위 클래스 의 실현 은 불확실 하기 때문이다.
또한 저 는 screen = false 이라는 말 도 if (pq.getClass() == PriorityBlockingQueue.class) 의 판단 에 넣 어야 한다 고 생각 합 니 다.이것 은 Priority BlockingQueue 의 하위 클래스 가 offer(이 함수 가 null 요 소 를 판단 했다)을 다시 쓰 지 않 았 다 고 가정 하 는 방법 일 수도 있 습 니 다.Priority BlockingQueue 의 하위 클래스 가 offer 을 다시 써 서 내부 배열 에 null 요 소 를 가지 게 하 더 라 도 마지막 으로 heapify() 은 모든 null 요 소 를 발견 하고 이상 을 던 집 니 다(나중에 다시 말 합 니 다).
if (a.getClass() != Object[].class)
Collection.toArray() spec should be explicit about returning precisely an Object[]
위의 bug 소개 에서 알 수 있 듯 이 Collection.toArray() 에서 돌아 오 는 배열 의 실제 유형 은 Object[] 이지 만 배열 의 협 변 으로 인해 실제 유형 은 다른 것 일 수 있 습 니 다.
그래서 우리 가 이런 상황 을 발견 하면 Object[].class 의 배열 을 새로 만 들 고 모든 요 소 를 간단하게 복사 합 니 다.
if (screen && (n == 1 || this.comparator != null))
screen 은 true 대표 로 배열 의 null 요 소 를 스 캔 해 야 합 니 다.문 제 는 뒤에 && (n == 1 || this.comparator != null) 이 왜 이렇게 쓰 여 있 느 냐 하 는 것 이다.
입력 매개 변수 c 은 세 가지 상황 이 있 습 니 다.

c 은 비 교 를 지원 하 는 집합 으로 비교 방식 은 Comparable 이기 때문에 Comparator 의 구성원 은 null 이다.

c 은 비 교 를 지원 하 는 집합 으로 비교 방식 은 Comparator 이기 때문에 Comparator 의 구성원 은 null 이 아니다.

c 은 비 교 를 지원 하지 않 는 집합 으로 Comparator 구성원 이 전혀 없다.

Note that null is not an instance of any class, and e.compareTo(null) should throw a NullPointerException even though e.equals(null) returns false. n == 1 이 성립 되면 원 소 는 하나 밖 에 없다 는 뜻 이다.비교 방식 이 Comparable 이 더 라 도 하나의 요소 만 있 기 때문에 비교 행 위 는 발생 하지 않 을 수 있 기 때문에 처음에 null 요 소 를 넣 었 을 때 오히려 빈 지침 이상 을 던 지지 않 았 다.구체 적 으로 이 bugAdding null key to empty TreeMap without Comparator should throw NPE 를 볼 수 있 습 니 다.그래서 원소 의 개수 가 1 인 것 을 발견 하면 바로 스 캔 한다.
Unlike Comparable, a comparator may optionally permit comparison of null arguments, while maintaining the requirements for an equivalence relation.
만약 에 this.comparator != null) 이 성립 된다 면 c 는 비 교 를 지원 하 는 집합 일 것 이다.Comparator 의 실현 은 null 을 비교 할 수 있 기 때문에 Comparator 의 구성원 이 null 이 아니 라 c 의 내부 배열 은 null 을 포함 할 수 있다.그래서 스 캔 도 필요 해.
대부분의 경우 size 가 1 보다 크 고 this.comparator 이 null 인 경우 스 캔 을 하지 않 을 것 이 라 고 말 할 수 있 습 니 다.그러면 문제 가 없 을까요?아니요.heapify() 은 모든 원 소 를 검사 하기 때문이다.
heapify()

    private void heapify() {
        Object[] array = queue;
        int n = size;
        int half = (n >>> 1) - 1;//            
        Comparator<? super E> cmp = comparator;
        if (cmp == null) {
            for (int i = half; i >= 0; i--)
                siftDownComparable(i, (E) array[i], array, n);
        }
        else {
            for (int i = half; i >= 0; i--)
                siftDownUsingComparator(i, (E) array[i], array, n, cmp);
        }
    }

heapify() 함 수 는 마지막 비 잎 노드 의 색인 에서 0 으로 옮 겨 다 니 며 각 색인 은 침하 함 수 를 한 번 씩 실행 합 니 다.위의 this.comparator 이 null 이라는 가설 에 따라 호출 된 침하 함 수 는 siftDownComparable 입 니 다.

    private static <T> void siftDownComparable(int k, T x, Object[] array,
                                               int n) {
        if (n > 0) {
            Comparable<? super T> key = (Comparable<? super T>)x;
            int half = n >>> 1;  //             ，     k         ，        
            while (k < half) {
                int child = (k << 1) + 1; 
                Object c = array[child];
                int right = child + 1;
                if (right < n &&
                    ((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;
        }
    }

siftDownComparable 함수 가 침하 논 리 를 집행 하고 while (k < half) 은 k 가 한 잎 노드 에 도 착 했 을 때 더 이상 가라앉 을 수 없다 는 것 을 의미한다.그러나 k 가 한 잎 노드 의 지난 순환 에 도 착 했 을 때 k 는 비 잎 노드 에 머 물 렀 을 것 이다.그리고 이번 순환 에서 두 아이 가 null 요소 인지 확인 하 는 것 을 책임 질 것 이다(왼쪽 아 이 는 반드시 존재 하고 오른쪽 아이 가 right < n 이 존재 하면 검사 할 것 이다).
Note that null is not an instance of any class, and e.compareTo(null) should throw a NullPointerException even though e.equals(null) returns false.
compare To 에 따 르 면 (Comparable super T>) c).compareTo((T) array[right]) 은 오른쪽 아 이 를 검사 하 는 일 을 맡 고 있 으 며,국 지적 변수 c 이 null 이면 이상 을 던 지기 때문에 이 말 도 왼쪽 아 이 를 검사 할 수 있다.
오른쪽 아이 가 존재 하지 않 으 면 (Comparable super T>) c).compareTo((T) array[right]) 은 집행 되 지 않 지만 괜찮아 요.key.compareTo((T) c) 은 왼쪽 아 이 를 검사 하 는 일 을 맡 았 다.
종합 적 으로 heapify() 은 모든 비 잎 노드 를 옮 겨 다 니 며 침하 함 수 를 수행 합 니 다.siftDownComparable 침하 함 수 는 마지막 순환 에서 두 개의 잎 노드 를 검사 하기 때문에 최종 적 으로 모든 요 소 는 null 인지 여 부 를 검사 합 니 다.
총결산
screen 스 캔 null 요소 가 실행 되 었 든 안 되 었 든 최종 heapify() 은 모든 요소 가 null 인지 확인 하 는 김 에.