jdk優先級隊列源碼分析

文章目錄

• • 1 jdk PriorityQueue簡述
  • 2 jdk PriorityQueue基本組成
  • 3 入隊操作-offer分析
  • 4 出隊操作-push分析
  • 5 本文小結

1 jdk PriorityQueue簡述

上文講述了netty優先級隊列的實作方式,本文将jdk1.8源碼實作的優先級隊列,做進一步比較和分析.

從下圖繼承關系可知,netty實作與jdk實作優先級隊列原理類似,隻是netty針對task做了更多特定的封裝,而dk實作的PriorityQueue通用性更強;

2 jdk PriorityQueue基本組成

與netty實作類似,這裡也是以數組實作堆結構來存儲優先級隊列!同樣也存在比較器,友善使用者靈活定義比較功能;

3 入隊操作-offer分析

jdk實作的入隊操作比netty實作更具有通用性,假如内置比較器為null,則會使用節點,強制轉換為Comparable類型,使用該類型進行比較,其他具體操作除了部分細節不同外,基本上和netty的優先級隊列實作差别不大!

//offer實作
    public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        modCount++;
        int i = size;
        if (i >= queue.length)
            grow(i + 1);
        size = i + 1;
        if (i == 0)
            queue[0] = e;
        else
            siftUp(i, e);
        return true;
    }
//siftUp實作
    private void siftUp(int k, E x) {
        if (comparator != null)
            siftUpUsingComparator(k, x);
        else
            siftUpComparable(k, x);
    }
//從下往上堆化
    @SuppressWarnings("unchecked")
    private void siftUpUsingComparator(int k, E x) {
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = queue[parent];
            if (comparator.compare(x, (E) e) >= 0)
                break;
            queue[k] = e;
            k = parent;
        }
        queue[k] = x;
    }
           

4 出隊操作-push分析

出隊操作原理與netty實作基本類似,也是先取堆頂元素,然後取最後一個節點,自頂而下與子節點進行比較,進行堆化操作!

//poll實作
@SuppressWarnings("unchecked")
    public E poll() {
        if (size == 0)
            return null;
        int s = --size;
        modCount++;
        E result = (E) queue[0];
        E x = (E) queue[s];
        queue[s] = null;
        if (s != 0)
            siftDown(0, x);
        return result;
    }
//siftDown實作
    private void siftDown(int k, E x) {
        if (comparator != null)
            siftDownUsingComparator(k, x);
        else
            siftDownComparable(k, x);
    }
//從上往下堆化
    @SuppressWarnings("unchecked")
    private void siftDownUsingComparator(int k, E x) {
        int half = size >>> 1;
        while (k < half) {
            int child = (k << 1) + 1;
            Object c = queue[child];
            int right = child + 1;
            if (right < size &&
                comparator.compare((E) c, (E) queue[right]) > 0)
                c = queue[child = right];
            if (comparator.compare(x, (E) c) <= 0)
                break;
            queue[k] = c;
            k = child;
        }
        queue[k] = x;
    }
           

5 本文小結

jdk實作的優先級隊列本質與netty實作基本一緻,均是使用數組建構小頂堆,插入則從下網上比較堆化,删除則取最後一個元素從上往下進行堆化處理!

總結一下,這裡有如下幾點值得學習的:

1. 感受netty與jdk的優先級隊列實作思路:基本思路一緻,netty定制了scheculeTask的一些特殊行為,而jdk則在通用性下了更多的功夫;
2. jdk實作中同樣存在擴容問題,這裡思路也與netty實作吻合;
3. 為了保證容錯性,當比較器為空時候,jdk實作會使用比較器接口強制轉換隊列的存儲對象,這裡的選擇值得商榷,必須保證如果比較器未初始化,存儲節點必須繼承實作可比較接口!