Анализ исходного кода PriorityQueue мертвой java-коллекции

Java

вопрос

(1) Что такое приоритетная очередь?

(2) Как реализовать приоритетную очередь?

(3) Является ли PriorityQueue потокобезопасным?

(4) Заказывается ли PriorityQueue?

Введение

Очередь с приоритетом представляет собой набор из 0 или более элементов, каждый элемент в наборе имеет значение веса, а элемент с наивысшим или наименьшим приоритетом извлекается каждый раз, когда он удаляется из очереди.

Как правило, приоритетные очереди реализуются с использованием кучи.

Помните знания о кучах? Прямая ссылка【Пожалуйста, не просите меня снова складывать (сортировать) в интервью!].

Так как же Java реализует приоритетную очередь через структуру данных «куча»?

Давайте учиться вместе.

Анализ исходного кода

главный атрибут

// 默认容量
private static final int DEFAULT_INITIAL_CAPACITY = 11;
// 存储元素的地方
transient Object[] queue; // non-private to simplify nested class access
// 元素个数
private int size = 0;
// 比较器
private final Comparator<? super E> comparator;
// 修改次数
transient int modCount = 0; // non-private to simplify nested class access

(1) Емкость по умолчанию — 11;

(2) очередь, элементы хранятся в массиве, что согласуется с общим использованием массивов для хранения в куче, как мы говорили ранее;

(3) компаратор, компаратор, в приоритетной очереди также есть два способа сравнения элементов, один — естественный порядок элементов, а другой — сравнение через компаратор;

(4) modCount, количество модификаций, этот атрибут указывает на то, что PriorityQueue также является отказоустойчивым;

Не знаете о быстром сбое, проверьте эту статьюпасхальные яйцачасть:【Анализ исходного кода HashSet мертвой коллекции Java].

присоединиться к команде

Существует два метода постановки в очередь, add(E e) и offer(E e), оба из которых непротиворечивы, а add(E e) также является вызовом offer(E e).

public boolean add(E e) {
    return offer(e);
}

public boolean offer(E e) {
    // 不支持null元素
    if (e == null)
        throw new NullPointerException();
    modCount++;
    // 取size
    int i = size;
    // 元素个数达到最大容量了，扩容
    if (i >= queue.length)
        grow(i + 1);
    // 元素个数加1
    size = i + 1;
    // 如果还没有元素
    // 直接插入到数组第一个位置
    // 这里跟我们之前讲堆不一样了
    // java里面是从0开始的
    // 我们说的堆是从1开始的
    if (i == 0)
        queue[0] = e;
    else
        // 否则，插入元素到数组size的位置，也就是最后一个元素的下一位
        // 注意这里的size不是数组大小，而是元素个数
        // 然后，再做自下而上的堆化
        siftUp(i, e);
    return true;
}

private void siftUp(int k, E x) {
    // 根据是否有比较器，使用不同的方法
    if (comparator != null)
        siftUpUsingComparator(k, x);
    else
        siftUpComparable(k, x);
}

@SuppressWarnings("unchecked")
private void siftUpComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>) x;
    while (k > 0) {
        // 找到父节点的位置
        // 因为元素是从0开始的，所以减1之后再除以2
        int parent = (k - 1) >>> 1;
        // 父节点的值
        Object e = queue[parent];
        // 比较插入的元素与父节点的值
        // 如果比父节点大，则跳出循环
        // 否则交换位置
        if (key.compareTo((E) e) >= 0)
            break;
        // 与父节点交换位置
        queue[k] = e;
        // 现在插入的元素位置移到了父节点的位置
        // 继续与父节点再比较
        k = parent;
    }
    // 最后找到应该插入的位置，放入元素
    queue[k] = key;
}

(1) Пустые элементы не допускаются в очередь;

(2) Если массива недостаточно, сначала расширьте его;

(3) Если элемента еще нет, вставьте позицию нижнего индекса 0;

(4) Если есть элемент, он вставляется в позицию после последнего элемента (на самом деле он не вставляется);

(5) Скопируйте кучу снизу вверх и сравните ее с родительским узлом до самого верха;

(6) Если он меньше родительского узла, обмениваться позициями с родительским узлом, пока он не станет больше родительского узла;

(7) Видно, что PriorityQueue — это небольшая верхняя куча.

Расширение

private void grow(int minCapacity) {
    // 旧容量
    int oldCapacity = queue.length;
    // Double size if small; else grow by 50%
    // 旧容量小于64时，容量翻倍
    // 旧容量大于等于64，容量只增加旧容量的一半
    int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                     (oldCapacity + 2) :
                                     (oldCapacity >> 1));
    // overflow-conscious code
    // 检查是否溢出
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
        
    // 创建出一个新容量大小的新数组并把旧数组元素拷贝过去
    queue = Arrays.copyOf(queue, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

(1) Когда массив относительно мал (менее 64), емкость каждого расширения удваивается;

(2) Когда массив относительно велик, каждое расширение увеличивает емкость только вдвое;

вне команды

Существует два метода удаления из очереди: remove() и poll(). remove() также называется poll(), но при отсутствии элементов выдается исключение.

public E remove() {
    // 调用poll弹出队首元素
    E x = poll();
    if (x != null)
        // 有元素就返回弹出的元素
        return x;
    else
        // 没有元素就抛出异常
        throw new NoSuchElementException();
}

@SuppressWarnings("unchecked")
public E poll() {
    // 如果size为0，说明没有元素
    if (size == 0)
        return null;
    // 弹出元素，元素个数减1
    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;
}

private void siftDown(int k, E x) {
    // 根据是否有比较器，选择不同的方法
    if (comparator != null)
        siftDownUsingComparator(k, x);
    else
        siftDownComparable(k, x);
}

@SuppressWarnings("unchecked")
private void siftDownComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>)x;
    // 只需要比较一半就行了，因为叶子节点占了一半的元素
    int half = size >>> 1;        // loop while a non-leaf
    while (k < half) {
        // 寻找子节点的位置，这里加1是因为元素从0号位置开始
        int child = (k << 1) + 1; // assume left child is least
        // 左子节点的值
        Object c = queue[child];
        // 右子节点的位置
        int right = child + 1;
        if (right < size &&
            ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
            // 左右节点取其小者
            c = queue[child = right];
        // 如果比子节点都小，则结束
        if (key.compareTo((E) c) <= 0)
            break;
        // 如果比最小的子节点大，则交换位置
        queue[k] = c;
        // 指针移到最小子节点的位置继续往下比较
        k = child;
    }
    // 找到正确的位置，放入元素
    queue[k] = key;
}

(1) Вытолкнуть первый элемент очереди;

(2) Переместите элемент в конце очереди в начало очереди;

(3) Соберите кучу сверху вниз и сравните ее с наименьшим дочерним узлом до конца;

(4) Если он больше, чем наименьший дочерний узел, поменяйте местами и продолжите сравнение с наименьшим дочерним узлом;

(5) Если он меньше наименьшего дочернего узла, нет необходимости обмениваться позициями, и нагромождение заканчивается;

(6) Это удаление верхнего элемента в куче;

Получить первый элемент очереди

Есть два метода получения первого элемента очереди: element() и peek().

public E element() {
    E x = peek();
    if (x != null)
        return x;
    else
        throw new NoSuchElementException();
}
public E peek() {
    return (size == 0) ? null : (E) queue[0];
}

(1) Если есть элемент, взять элемент с индексом 0;

(3) Если элемента нет, возвращается null, а element() генерирует исключение;

Суммировать

(1) Приоритеткую представляет собой небольшую точку сваи;

(2) PriorityQueue не является потокобезопасным;

(3) PriorityQueue не упорядочена, только вершина кучи хранит наименьший элемент;

(4) Постановка в очередь — это реализация элемента вставки кучи;

(5) Dequeue — реализация удаления элементов кучи;

(6) Все еще не понимаете кучу? Взгляните на эту статью【Пожалуйста, не просите меня снова складывать (сортировать) в интервью!].

пасхальные яйца

(1) Об этих методах в Queue?

Очередь — это интерфейс верхнего уровня всех очередей, он определяет ряд методов, в чем разница между ними?

действовать Выбросить исключение вернуть конкретное значение
присоединиться к команде add(e) предложение (д) - ложь
вне команды remove() опрос () - ноль
экзамен element() заглянуть () - ноль

(2) Почему метод add(e) в PriorityQueue не проверяется на наличие исключений?

Поскольку PriorityQueue — это бесконечно растущая очередь, она будет расширяться, когда элементов будет недостаточно, поэтому добавление элементов не приведет к сбою.

Добро пожаловать, чтобы обратить внимание на мою общедоступную учетную запись «Брат Тонг читает исходный код», проверить больше статей из серии исходного кода и поплавать в океане исходного кода с братом Тонгом.

qrcode

Категории