Collection/Executor

PriorityBlockingQueue【源码】》学习过程/多有漏误/仅作参考/不再更新《Java

Collection/Executor

PriorityBlockingQueue【总结】》学习总结/最新最准/持续更新《Java

Collection/Executor

PriorityBlockingQueue【问题】》学习解答/持续更新

涉及内容

PriorityBlockingQueue优先级阻塞队列类源码及机制详解

PriorityBlockingQueue优先级阻塞队列类是BlockingQueue阻塞队列接口的实现类之一基于数组实现。

优先级阻塞队列类不是标准的FIFO队列元素会以小顶堆的规则被排序并存放在数组的相应位置中。

因此当在实际开发中对元素的顺序有特定要求时可以使用优先级阻塞队列类。

所谓的小顶堆本质是一类特殊的完全二叉树其规则是父元素一定小于/等于两个子元素子元素之间不要求大小比对。

类似的当父元素大于/等于两个子元素时就是所谓的大顶堆。

在优先级阻塞队列类中小顶堆以数组的形式保存。

之所以可以使用数组来模拟小顶堆是因为元素索引会以以下规则分布在数组上

左/右子元素索引

优先级阻塞队列类必须定义比较器或元素必须实现比较能力。

优先级阻塞队列类是具备排序能力的队列而众所周知比较是排序的基础条件为了实现这一点优先级阻塞队列类设计了两种方式进行元素间的比较一是使用比较器即Comparator比较器接口对象二是通过元素自身的比较能力即元素类必须实现Comparable比较能力接口。

开发者必须至少实现两者当中的一个否则将会在使用过程中抛出类转换异常。

比较器相比比较能力而言拥有更高的优先级通俗的说就是当两种比较方式都满足的情况下会优先使用比较器进行比较。

延迟队列类是无界队列意味着其最大容量理论上只受限于堆内存的大小。

延迟队列类底层使用优先级队列类实现由于其扩容机制的存在延迟队列类也被纳入无界队列的范围中。

但虽说如此优先级队列类在实现中还受到数组实现与int类型影响因此延迟队列的最大容量实际上为Integer.MAX_VALUE。

由于其无界队列的定义为了掩盖实际实现中受到的限制当其保存的元素总数触达上限时会模拟堆内存不足的场景手动抛出内存溢出错误。

优先级阻塞队列类是真正意义上的无界队列即容量理论上只受限于堆内存的大小。

基于数组实现的原因及出于节省内存的目的优先级阻塞队列类内部存在扩容机制以使得元素数组的长度能够更加贴合实际所需故而优先级阻塞队列类存在初始容量的说法可在创建时显式指定。

如果在创建优先级阻塞队列时未显式指定初始容量则会隐式设置其为默认初始容量11。

当元素总数触达优先级阻塞数组的当前容量时会触发扩容。

扩容的本质是创建长度更大的新元素数组来代替旧元素数组并将旧元素数组中的元素迁移至新元素数组。

容量的具体增长规则如下

旧容量

由于在具体实现上受到int类型的物理限制因此虽说优先级阻塞队列类是无界队列但实际最大容量仅可扩容至Integer.MAX_VALUE

8。

减8的原因是因为有些虚拟机会在数组中保存源数据header

words故而特意留出了这部分空间。

但话虽如此优先级阻塞队列最多依然可能保存Integer.MAX_VALUE个元素。

因为优先级阻塞队列类虽然限制了通过常规单插入使得容量超过Integer.MAX_VALUE

8的可能但却可以通过批量插入来突破这个限制。

为了兼容使用元素总数超过Integer.MAX_VALUE

8的集进行批量插入及创建优先级阻塞队列的情况优先级阻塞队列类是允许这么做的但后果是可能抛出内存溢出错误。

优先级阻塞队列类不允许存null或者说阻塞队列接口的所有实现类都不允许存null。

null被poll()及peek()方法作为优先级阻塞队列不存在元素的标记值因此所有的阻塞队列接口实现类都不允许存null。

优先级阻塞队列类是线程安全的或者说阻塞队列接口的所有实现类都是线程安全的其接口定义中强制要求实现类必须线程安全。

优先级阻塞队列类采用“单锁”线程安全机制即使用单个ReentrantLock可重入锁锁来保证整体的线程安全。

但与此同时其还添加了“无锁”线程安全机制来辅助扩容即在元素数组扩容时使用CAS乐观锁保证线程安全的同时不阻塞移除方法的执行该知识点会在下文详述。

由于CAS乐观锁并不是真正意义上的锁因此被称为“无锁”线程安全机制。

优先级阻塞队列类的迭代器是弱一致性的即可能迭代到已移除的元素或迭代不到新插入的元素。

优先级阻塞队列类的迭代器实现非常直接或者说归于直接了其会直接将数据拷贝一份快照存入生成的迭代器中以进行迭代。

这么做的好处是迭代器的实现非常的简单但缺点也明显当优先级阻塞队列的元素总数较大或生成的迭代器数量较多时对内存的消耗会非常严重。

优先级阻塞队列类使用快照来实现迭代器的原因是元素会因为排序而难以追踪其位置上变化因此使用不变的快照是最好的做法。

优先级阻塞队列类虽然与阻塞队列接口一样都被纳入Executor执行器框架的范畴但同时也是Collection集框架的成员。

/***

一个使用与优先级队列相同排序规则的阻塞队列并且提供可阻塞的找回操作。

尽管队列是逻辑上的无界尝试新增也可能由于造成内存*

溢出错误资源耗尽而失败。

这个类不允许null元素。

一个优先级队列依赖比较自然排序并且不允许插入非比较对象这么做可能会导致类*

型转换异常*

这个类及它的迭代器实现了集接口与迭代器接口所有的可能方法。

这个迭代器由iterator()方法提供以保证按任意特定的顺序遍历优先级*

阻塞队列的元素。

如果你需要有序的遍历考虑使用Arrays.sort(pq.toArray())进行排序。

并且drainTo()方法会移除一些元素在其*

Operations

对该类的操作无法保证元素按优先级排序。

如果你需要强制排序可以定义使用辅助键来打破主优先级值的自定义类或比较器。

例如这个*

类打破了可比较元素的FIFO。

要使用它你需要插入一个{code

new

FIFOEntry(anEntry)}而不是一个普通的条目对象。

通俗的说就是*

pre

href{docRoot}/../technotes/guides/collections/index.html

Java

该实现使用了一个基于数组的二进制堆公共操作受保护于一个单锁。

但是在调整大小期间分配即在容量满了之后重新分配一个*

新的数组准确的说应该称为扩容更加合适使用一个简单的自旋锁只在未持有主锁的情况下使用为了允许拿取与分配并发地操*

作。

这避免了等待中的消费者重复延迟如果使用单锁在扩容期间消费者将无法消费造成拿取者堆积和随之而来的元素积聚。

*/...

}字段

分配数组的最大大小。

一些虚拟机会在数组中保留一些头字所以专门预留了8个空位来进行保存数组的最大可用空间就是int的最大值*

-8。

试图分配更大的数组可能导致内存溢出错误请求数组大小超过虚拟机限制。

*/private

static

优先级队列表示为一个平衡二进制堆元素queue[n]的两个孩子是元素queue[2*n1]和元素queue[2*(n1)]这是一种通过数组来模拟完全*

二叉树的做法。

数组n位置表示的节点的两个子节点恰好是2*n1和2*(n1)。

优先级队列通过比较排序或通过元素自然排序。

如果比较器*

为null为每个堆中的节点n和每个n的子孙d。

最小的元素值在queue[0]假设队列不为空即默认是小顶堆的实现即父节点比子节点小*

因此根节点queue[0]是最小的而大顶堆是父节点比子节点大因此根节点queue[0]是最大的通过修改比较器是可以实现小顶堆到大顶*

Description:

比较器用于进行比较排序如果是元素的自然排序则为null。

*/private

transient

notEmpty;allocationSpinLock分配自旋锁

/***

分配自旋锁当进行扩容时保证扩容与移除/拿取可以同时执行。

*/private

transient

用于在序列化/反序列化时保证当前版本与之前版本的共存因此也只在序列化/反序列化期间有值。

/***

serialization/deserialization.*

一个只在序列化时使用的普通的优先级队列来维持类先前版本的共存。

只在序列化和反序列化是不为空。

**

Description:

优先级队列用于在序列化/反序列化时保证当前版本与之前版本的共存因此也只在序列化/反序列化期间有值。

*/private

PriorityQueueE

创建一个默认初始容量的优先级阻塞队列按元素自身的比较器自然排序。

/***

创建一个默认初始容量11的优先级阻塞队列其元素根据它们元素的比较器进行自然排序。

**

Description:

创建一个默认初始容量的优先级阻塞队列按元素自身的比较器自然排序。

*/public

{this(DEFAULT_INITIAL_CAPACITY,

null);}public

创建一个指定初始容量的优先级阻塞队列按元素自身的比较器自然排序。

/***

创建一个指定初始容量的优先级阻塞队列其元素根据它们元素的比较器进行自然排序。

**

param

创建一个指定初始容量的优先级阻塞队列按元素自身的比较器自然排序。

*/public

initialCapacity)

创建一个指定初始容量的优先级阻塞队列其元素根据指定的比较器进行排序。

/***

创建一个指定初始容量的优先级阻塞队列其元素根据指定的比较器进行排序。

**

param

该比较器将用于排序这个优先级队列。

如果为null则使用元素的比较能力进行排序*

throws

Object[initialCapacity];}public

PriorityBlockingQueue(Collection?

extends

创建一个包含指定集中元素的优先级阻塞队列。

如果指定集是一个排序集合或者优先级队列该优先级队列将按相同的顺序进行排序。

否则该优先级队列将根据元素的比较能力进行排序因此在元素在优先级阻塞队列中的排序可能与指定集中的不同。

/***

创建一个包含指定集中元素的优先级阻塞队列。

如果指定集是一个排序集合或者优先级队列该优先级队列将按相同的顺序进行排序。

否则该*

优先级队列将根据元素的比较能力进行排序因此在元素在优先级阻塞队列中的排序可能与指定集中的不同。

**

param

如果指定集的元素无法与根据优先级队列的顺序进行比较如果有某个元素没有实现比较能力接口就会出现*

throws

空指针异常如果指定集或集中的任意元素为null*/public

PriorityBlockingQueue(Collection?

extends

如果指定集是一个排序集合则将排序集合的比较器作为优先级阻塞队列的比较器。

SortedSet?

extends

如果指定集是一个优先级阻塞队列则将其比较器作为优先级阻塞队列的比较器。

PriorityBlockingQueue?

extends

精确匹配instanceof只能判断传入的指定集是优先级阻塞队列的子类包含本身而只有通过类型的具体判断才能判断是否真的是优//

先级阻塞队列。

如果指定集是优先级阻塞队列的子类则单纯获取到比较器是无法判断具体的排序的因为谁也不知道子类的实现是怎样//

(pq.getClass()

PriorityBlockingQueue.class)heapify

false;}//

如果指定集的类型不是数组列表则返回的元素数组拷贝可能因为协变的原因不是Object因此需要再进行一次拷贝确保没有问题。

if

(c.getClass()

如果需要筛选null值并且元素总数为1或者比较为不为null则直接进行null值的扫描。

screen为true说明指定集中可能包含null元素需要//

进行筛选。

如果指定集中只有一个元素则该元素很有可能因为无需进行比较而遗漏了空检查从而使的一个null元素加入了优先级阻塞队列。

//

如果比较器不为null则由于比较其本身是可能允许null元素的比较的因此也需要进行筛选。

if

(screen

将数据进行堆化本质就是进行排序。

该操作是针对那些没有强制性排序需求的集的。

if

private

对元素数组进行扩容。

扩容可以分为三步分配新元素数组、赋值新元素数组及数据迁移。

其中新元素数组会在乐观锁的保护下进行以避免阻塞正常的移除/拿取和插入/放置。

而赋值新元素数组及数据迁移这两部则必须在主锁悲观锁的的保护下进行。

/***

尝试成长数组以容纳最少一个更多元素但是通常会拓展50%竞争时放弃允许重试我们认为这种竞争情况很少见

param

尝试成长对元素数组进行扩容。

扩容可以分为三步分配新元素数组、赋值新元素数组及数据迁移。

其中新元素数组会在乐*

Description:

观锁的保护下进行以避免阻塞正常的移除/拿取和插入/放置。

而赋值新元素数组及数据迁移这两部则必须在主锁悲观锁的*

Description:

加乐观锁即通过CAS操作将allocationSpinLock从0修改1。

如果成功则分配新元素数组否则说明有其它线程在分配新元素数组直接跳过//

(allocationSpinLock

如果小就快速成长如果元素数组的大小小于64则直接在原来的基础上新增一倍否则新增0.5倍int

newCap

0说明新容量已经超过了最大数组大小甚至有可能已经超过了int类型的最大值在这种情况下要判//

断旧容量能否继续增大即旧容量是否小于最大数组大小。

如果是则直接增大至最大数组大小否则直接抛出内存溢出异常。

if

(newCap

0说明旧容量本身就已经达到了int类型的最大值。

这确实是可能的虽然一般不会出现这种情况。

但如果在创建优先级阻塞//

队列的时候使用的是集构造方法并且参数集中包含的元素数量等于int类型的最大值那确实能产生这种情况。

因此对于旧容量能否//

对于第一种情况如果旧容量已经达到了最大数组大小则就不允许在增大了要抛出内存溢出异常否则增大至最大数组大小。

//

对于第二种情况由于旧容量本身已经大于最大数组大小因此不允许在增大了抛出内存溢出异常。

if

(minCap

如果当前线程没有获得分配新元素数组的权限即获取乐观锁失败或者因为旧容量成长后超过了int类型的最大值又或者是在此期间已经//

有线程完成了扩容。

总之只要分配新元素数组失败则放弃当前线程持有的CPU资源。

目的是为了让完成了新元素数组分配的线程可以优先//

(newArray

将锁重新加起。

在分配元素数组期间由于并不涉及原元素数组的替换与数据的迁移因此理论上不应该阻塞拿取者/放置者的并发也因此//

分配新元素数组这个操作会在一个乐观锁的保护下进行并不会在主锁的保护下进行因此新元素数组的分配并不会阻塞移除/拿取操作。

lock.lock();//

如果新元素数组分配成功并且在此期间没有其它线程完成扩容分配新元素数组

赋值新元素数组

newArray;System.arraycopy(array,

newArray,

移除/拿取元素数组中的第一个元素也是排序最小的元素。

元素移除后会取元素数组的最后一个元素进行首位填充并进行下排序以保证整个元素排序及分布的正确性。

/***

出队移除/拿取元素数组中的第一个元素也是排序最小的元素。

元素移除后会取元素数组的最后一个元素进行首位填充并进*

Description:

获取元素数组的最后一个元素用于填充在首个索引位置以被进行下排序。

E

(E)

获取比较器判断是通过比较器进行比较还是通过元素本身的比较能力进行比较。

Comparator?

super

通过元素本身的比较能力进行下排序。

siftDownComparable(0,

array,

通过比较器进行下排序。

siftDownUsingComparator(0,

array,

本质是循环性的上排序。

所谓上排序就是判断指定索引位置的元素是否大于父元素如果不是则将之与父元素进行交换。

然后将原父元素的索引位置作为新的指定索引位置重复这个过程。

如果指定元素比两父元素要大或者指定索引位置根节点说明已经排序完毕结束这个循环性的上排序。

/***

在k位置插入一个项x通过在树中对x进行提升直至其大于它的父节点或称为根节点来维持堆的不变性。

*

simplify

简化和加速强制和比较。

比较能力和比较器版本分离成不同的方法其它完全一样。

类似于下排序。

这些方式是静态的堆被声明为参数以*

param

筛选上可比较的本质是循环性的上排序。

所谓上排序就是判断指定索引位置的元素是否大于父元素如果不是则将之与父元素*

Description:

进行交换。

然后将原父元素的索引位置作为新的指定索引位置重复这个过程。

如果指定元素比两父元素要大或者指定索引位置根*

Description:

节点说明已经排序完毕结束这个循环性的上排序。

*/private

static

array)完全相同只是元素之间的比较变为了采用比较器的方式完成而不是元素自身的比较能力。

/***

本质是循环性的下排序。

所谓下排序就是判断指定索引位置的元素是否小于两个孩子元素如果不是则将之与两个孩子元素之中较小的一个进行交换。

然后将较小孩子节点的索引位置作为新的指定索引位置重复这个过程。

如果指定元素比两孩子元素都要小或者指定索引位置是一个叶子节点说明已经排序完毕结束这个循环性的下排序。

/***

在k的位置插入项x通过重复地将x从树中降级直至其小于或等于它的孩子或是一个叶子节点。

**

param

筛选下可比较的本质是循环性的下排序。

所谓下排序就是判断指定索引位置的元素是否小于两个孩子元素如果不是则将之与*

Description:

两个孩子元素之中较小的一个进行交换。

然后将较小孩子节点的索引位置作为新的指定索引位置重复这个过程。

如果指定元素比两*

Description:

孩子元素都要小或者指定索引位置是一个叶子节点说明已经排序完毕结束这个循环性的下排序。

*/private

static

获取左孩子的索引值不用担心孩子的索引会超出范围方法在调用前只会选择元素数组的前半段元素。

int

child

将两个孩子中更小的那个与指定元素进行比较如果指定元素更小说明已无法进行下排序排序结束否则继续循环进行下排序直//

(key.compareTo((T)

将更小的那个孩子元素存放于指定的位置随后将原孩子元素的索引位置作为下次下排序的指定位置该操作就相当于进行了一次下排序。

array[k]

c;k

n)完全相同只是元素之间的比较变为了采用比较器的方式完成而不是元素自身的比较能力。

/***

筛选下使用比较器该方法的逻辑与siftDownComparable(int

Object[]

采用比较器的方式完成而不是元素自身的比较能力。

*/private

static

不用担心孩子的索引会超出范围方法在调用前只会选择元素数组的前半段元素进行降级。

Object

array[child];int

在整个树中建立堆不变量如上所述在调用之前不假设元素的顺序即该方法调用之前无需判断元素数组本身的顺序。

**

Description:

堆化即按照比较器或元素的比较能力进行顶堆排序。

*/private

void

获取元素总数的中间值因为对整个元素数组进行堆化排序只需要排序前一半元素即可后一半会在前一半的排序中自动完成。

int

half

如果没有比较器则通过元素自身的比较能力进行堆化排序。

siftDownComparable(i,

(E)

向向优先级阻塞队列的队尾添加指定元素优先级阻塞队列会根据排序规则通过上排序将指定元素排序到队列中合适的位置。

该方法是插入/放置方法中异常形式的实现当优先级阻塞队列存在空余容量时插入/放置成功并返回true否则会抛出非法状态异常。

虽说定义如此但实际由于优先级阻塞队列作为无界队列的实现与链接阻塞队列不同是动态扩容的方式因此最大容量理论上只受限于堆内存的大小故而不会抛出常规的非法状态异常而只会在堆内存不足时抛出内存溢出异常。

在真正的实现中由于size字段的存在因此容量实际上还受int类型的限制。

为了与理论达成一致容量只受限于堆内存的大小当元素总数大于等于指定的数量上限时下次扩容会直接抛出内存溢出错误而不是正常的非法状态异常以造成堆内存不足的假象。

/***

类转换异常如果指定元素无法在优先级队列中根据优先级队列的排序与元素正确的比较一般是因为没有实现比较能力接口。

*

throws

新增向优先级阻塞队列的队尾添加指定元素优先级阻塞队列会根据排序规则通过上排序将指定元素排序到队列中合适的位置。

*

Description:

该方法是插入/放置方法中异常形式的实现当优先级阻塞队列存在空余容量时插入/放置成功并返回true否则会抛出非法状态*

Description:

异常。

虽说定义如此但实际由于优先级阻塞队列作为无界队列的实现与链接阻塞队列不同是动态扩容的方式因此最大容量*

Description:

理论上只受限于堆内存的大小故而不会抛出常规的非法状态异常而只会在堆内存不足时抛出内存溢出异常。

*

Description:

在真正的实现中由于size字段的存在因此容量实际上还受int类型的限制。

为了与理论达成一致容量只受限于堆内存的大小*

Description:

当元素总数大于等于指定的数量上限时下次扩容会直接抛出内存溢出错误而不是正常的非法状态异常以造成堆内存不足的*

Description:

由于优先级阻塞队列是一个无界队列因此理论上不会出现容量不足的情况因此该方法不会因为容量不足而出现异常...//

事实上虽然都是无界队列优先级阻塞队列的实现与链接阻塞队列显然是完全不同的。

链接阻塞队列的无界用法是有真正意义上的容量的//

因此方法运行都与有界队列无异。

但是优先级阻塞队列则是可扩容的实现理论上可以无限增大唯一的限制是堆内存的大小。

但在实际实//

现中显然不可能因为它还受大小字段int类型的限制。

因此当优先级阻塞队列保存的元素总数达到上限时需要给开发者营造出是因为堆//

内存的限制而无法继续存放的假象故而当元素总数达到上限在下一次扩容时会直接抛出内存溢出错误而不是正常的非法状态异常。

return

offer(e);}public

向优先级阻塞队列的队尾添加指定元素优先级阻塞队列会根据排序规则通过上排序将指定元素排序到队列中合适的位置。

该方法是插入/放置方法中特殊值形式的实现当优先级阻塞队列存在空余容量时插入/放置成功并返回true否则失败返回false。

虽说定义如此但实际由于优先级阻塞队列作为无界队列的实现与链接阻塞队列不同是动态扩容的方式因此最大容量理论上只受限于堆内存的大小故而永远不会返回false而只会在堆内存不足时抛出内存溢出异常。

在真正的实现中由于size字段的存在因此容量实际上还受int类型的限制。

为了与理论达成一致容量只受限于堆内存的大小当元素总数大于等于指定的数量上限时下次扩容会直接抛出内存溢出错误而不是正常的返回false以造成堆内存不足的假象。

/***

新增指定元素至优先级队列。

由于队列时无界的该方法永远不会返回false。

**

param

类转换异常如果指定元素无法在优先级队列中根据优先级队列的排序与元素正确的比较一般是因为没有实现比较能力接口。

*

throws

提供向优先级阻塞队列的队尾添加指定元素优先级阻塞队列会根据排序规则通过上排序将指定元素排序到队列中合适的位置。

*

Description:

该方法是插入/放置方法中特殊值形式的实现当优先级阻塞队列存在空余容量时插入/放置成功并返回true否则失败返回false。

*

Description:

虽说定义如此但实际由于优先级阻塞队列作为无界队列的实现与链接阻塞队列不同是动态扩容的方式因此最大容量理论上*

Description:

只受限于堆内存的大小故而永远不会返回false而只会在堆内存不足时抛出内存溢出异常。

*

Description:

在真正的实现中由于size字段的存在因此容量实际上还受int类型的限制。

为了与理论达成一致容量只受限于堆内存的大小*

Description:

当元素总数大于等于指定的数量上限时下次扩容会直接抛出内存溢出错误而不是正常的返回false以造成堆内存不足的假象。

*/public

boolean

将新的元素插入数组的末尾并通过比较能力或比较器进行元素的上排序维持整个数组的排序。

Comparator?

super

array);elsesiftUpUsingComparator(n,

array,

向优先级阻塞队列的队尾添加指定元素优先级阻塞队列会根据排序规则通过上排序将指定元素排序到队列中合适的位置。

该方法是插入/放置方法中阻塞形式的实现当优先级阻塞队列存在空余容量时插入/放置成功并返回true否则阻塞至有空余容量。

虽说定义如此但实际由于优先级阻塞队列作为无界队列的实现与链接阻塞队列不同是动态扩容的方式因此最大容量理论上只受限于堆内存的大小故而永远阻塞而只会在堆内存不足时抛出内存溢出异常。

在真正的实现中由于size字段的存在因此容量实际上还受int类型的限制。

为了与理论达成一致容量只受限于堆内存的大小当元素总数大于等于指定的数量上限时下次扩容会直接抛出内存溢出错误而不是正常的阻塞以造成堆内存不足的假象。

/***

插入指定元素至优先级队列。

由于队列是无界的该方法永远不会阻塞。

**

param

类转换异常如果指定元素无法在优先级队列中根据优先级队列的排序与元素正确的比较一般是因为没有实现比较能力接口。

*

throws

放置向优先级阻塞队列的队尾添加指定元素优先级阻塞队列会根据排序规则通过上排序将指定元素排序到队列中合适的位置。

*

Description:

该方法是插入/放置方法中阻塞形式的实现当优先级阻塞队列存在空余容量时插入/放置成功并返回true否则阻塞至有空余*

Description:

容量。

虽说定义如此但实际由于优先级阻塞队列作为无界队列的实现与链接阻塞队列不同是动态扩容的方式因此最大容量*

Description:

理论上只受限于堆内存的大小故而永远阻塞而只会在堆内存不足时抛出内存溢出异常。

*

Description:

在真正的实现中由于size字段的存在因此容量实际上还受int类型的限制。

为了与理论达成一致容量只受限于堆内存的大小*

Description:

当元素总数大于等于指定的数量上限时下次扩容会直接抛出内存溢出错误而不是正常的阻塞以造成堆内存不足的假象。

*/public

void

向优先级阻塞队列的队尾添加指定元素优先级阻塞队列会根据排序规则通过上排序将指定元素排序到队列中合适的位置。

该方法是插入/放置方法中超时形式的实现当优先级阻塞队列存在空余容量时插入/放置成功并返回true否则在指定的等待时间内阻塞至有空余容量超出等待时间则返回false。

虽说定义如此但实际由于优先级阻塞队列作为无界队列的实现与链接阻塞队列不同是动态扩容的方式因此最大容量理论上只受限于堆内存的大小故而永远不会阻塞或返回false而只会在堆内存不足时抛出内存溢出异常。

在真正的实现中由于size字段的存在因此容量实际上还受int类型的限制。

为了与理论达成一致容量只受限于堆内存的大小当元素总数大于等于指定的数量上限时下次扩容会直接抛出内存溢出错误而不是正常的阻塞或返回false以造成堆内存不足的假象。

/***

插入指定元素至优先级队列。

由于队列是无界的该方法永远不会阻塞或返回false。

**

param

类转换异常如果指定元素无法在优先级队列中根据优先级队列的排序与元素正确的比较一般是因为没有实现比较能力接口。

*

throws

提供向优先级阻塞队列的队尾添加指定元素优先级阻塞队列会根据排序规则通过上排序将指定元素排序到队列中合适的位置。

*

Description:

该方法是插入/放置方法中超时形式的实现当优先级阻塞队列存在空余容量时插入/放置成功并返回true否则在指定的等待*

Description:

时间内阻塞至有空余容量超出等待时间则返回false。

虽说定义如此但实际由于优先级阻塞队列作为无界队列的实现与链接阻*

Description:

塞队列不同是动态扩容的方式因此最大容量理论上只受限于堆内存的大小故而永远不会阻塞或返回false而只会在堆内存*

Description:

在真正的实现中由于size字段的存在因此容量实际上还受int类型的限制。

为了与理论达成一致容量只受限于堆内存的大小*

Description:

当元素总数大于等于指定的数量上限时下次扩容会直接抛出内存溢出错误而不是正常的阻塞或返回false以造成堆内存不足*

Description:

从优先级阻塞队列的队头移除元素后将队尾元素将之填充并通过下排序维护优先级阻塞队列中的元素顺序。

该方法是移除/拿取方法中特殊值形式的实现当优先级阻塞队列存在元素时移除/拿取成功并返回元素否则返回null。

/***

轮询从优先级阻塞队列的队头移除元素后将队尾元素将之填充并通过下排序维护优先级阻塞队列中的元素顺序。

该方法是*

Description:

移除/拿取方法中特殊值形式的实现当优先级阻塞队列存在元素时移除/拿取成功并返回元素否则返回null。

*/public

poll()

从优先级阻塞队列的队头移除元素后将队尾元素将之填充并通过下排序维护优先级阻塞队列中的元素顺序。

该方法是移除/拿取方法中阻塞形式的实现当优先级阻塞队列存在元素时移除/拿取成功并返回元素否则阻塞至有元素。

/***

拿取从优先级阻塞队列的队头移除元素后将队尾元素将之填充并通过下排序维护优先级阻塞队列中的元素顺序。

该方法是*

Description:

移除/拿取方法中阻塞形式的实现当优先级阻塞队列存在元素时移除/拿取成功并返回元素否则阻塞至有元素。

*/public

take()

this.lock;lock.lockInterruptibly();E

result;try

当优先级阻塞队列中不存在元素时将拿取者进行挂起直至被放置者唤醒。

while

((result

从优先级阻塞队列的队头移除元素后将队尾元素将之填充并通过下排序维护优先级阻塞队列中的元素顺序。

该方法是移除/拿取方法中超时形式的实现当优先级阻塞队列存在元素时移除/拿取成功并返回元素否则阻塞指定的等待时间至有元素超出等待时间则返回null。

/***

轮询从优先级阻塞队列的队头移除元素后将队尾元素将之填充并通过下排序维护优先级阻塞队列中的元素顺序。

该方法是*

Description:

移除/拿取方法中超时形式的实现当优先级阻塞队列存在元素时移除/拿取成功并返回元素否则阻塞指定的等待时间至有元*

Description:

this.lock;lock.lockInterruptibly();E

result;try

获取优先级阻塞队列的队头获取元素。

该方法是检查方法中特殊值形式的实现当优先级阻塞队列存在元素时返回元素否则返回null。

/***

窥视获取优先级阻塞队列的队头获取元素。

该方法是检查方法中特殊值形式的实现当优先级阻塞队列存在元素时返回元素*

Description:

获取剩余容量。

由于优先级阻塞队列是无界队列因此会永远返回Integer.MAX_VALUE。

由于延迟队列是无界队列容量理论上只受限于堆内存的大小实际上还有int类型的限制因此永远返回Integer.MAX_VALUE。

/***

永远返回Integer.MAX_VALUE因为优先级阻塞队列不受容量限制。

**

return

剩余容量获取剩余容量。

由于优先级阻塞队列是无界队列因此会永远返回Integer.MAX_VALUE。

*/public

int

流失将优先级阻塞队列中所有的元素都迁移到指定集中。

*/public

int

流失将优先级阻塞队列中最多指定数量的元素都迁移到指定集中。

*/public

int

将允许按优先级阻塞队列的出队顺序依次加入指定集中每次移除一个元素都要通过下排序重新对优先级阻塞队列进行排序。

for

(int

返回在队列中用于排序元素的比较器如果队列使用它元素的比较能力则返回null**

return

返回在队列中用于排序元素的比较器如果队列使用它元素的比较能力则返回null*

Description:

索引关于获取指定元素在元素数组中的索引值如果不存在则返回-1。

*/private

int

将指定索引位置的元素移除并通过下排序和上排序维护整个元素数组的顺序。

/***

移除所在将指定索引位置的元素移除并通过下排序和上排序维护整个元素数组的顺序。

*/private

void

获取优先级阻塞队列的最后元素该元素时用于填充被移除的元素的。

E

moved

将最后元素覆盖至指定索引位置随后通过比较器或比较能力进行下排序以维护整个元素数组的顺序。

Comparator?

super

n);elsesiftDownUsingComparator(i,

moved,

如果在下排序后指定索引位置的元素就是覆盖的最后元素则说明并没有发生移动。

则该元素很有可能比指定索引位置的父节点要小//

(array[i]

array);elsesiftUpUsingComparator(i,

moved,

移除一个指定元素的单例移除成功返回true否则返回false。

/***

如果存在从队列中移除一个指定元素的单例。

更正式的应该通过o.equals(e)来判断队列包含一个或更多指定元素来进行移除。

当且仅当*

队列包含指定元素或等效地如果调用的结果是队列发生改变时返回true。

**

param

移除移除一个指定元素的单例移除成功返回true否则返回false。

*/public

boolean

移除指定索引位置的元素并通过上排序和下排序来维护整个元素数组的顺序。

removeAt(i);return

true;}

遍历整个元素数组找到指定元素进行移除并通过上/下排序来维护整个元素数组的顺序。

Object[]

array

判断优先级阻塞队列是否包含指定元素是则返回true否则返回false。

/***

如果队列包含指定元素则返回true。

更正式的当且仅当通过o.equals(e)判断队列包含最少一个指定元素是返回true。

**

param

包含判断优先级阻塞队列是否包含指定元素是则返回true否则返回false。

*/public

boolean

遍历数组将所有的元素置null并将大小设置为0。

Object[]

array

返回一个包含优先级阻塞队列所有元素的数组。

该数组是重新分配的因此增删不会影响优先级阻塞队列。

数组中的元素是直接按元素数组中的原始顺序排列的并不是优先级阻塞队列的元素出队顺序。

/***

返回一个包含队列中所有元素的数组。

返回的数组元素没有特定的顺序。

*

The

返回的数组是安全的队列中未维护任何指向该数组的引用。

换句话说该方法必须分配一个新数组。

调用者因此可以自由的修改返*

This

转化数组返回一个包含优先级阻塞队列所有元素的数组。

该数组是重新分配的因此增删不会影响优先级阻塞队列。

数组中*

Description:

的元素是直接按元素数组中的原始顺序排列的并不是优先级阻塞队列的元素出队顺序。

*/public

Object[]

返回一个包含优先级阻塞队列所有元素的数组。

该数组是重新分配的因此增删不会影响优先级阻塞队列。

数组中的元素是直接按元素数组中的原始顺序排列的并不是优先级阻塞队列的元素出队顺序。

如果传入的数组长度足够则直接将该数组返回否则会新分配第一个指定类型且大小与优先级阻塞队列相同的数组用于返回。

/***

返回一个包含队列中所有元素的数组返回数组的运行时类型是指定数组的运行时类型。

返回的数组元素没有特定的顺序。

如果队列*

符合指定的数组意思是指定数组的长度足以容下队列的所有元素则返回指定数组否则分配一个指定数组的运行时类型与队列大小*

this

如果队列符合指定数组并且有所空余即数组拥有与队列更多的元素应该说长度更合适毕竟数组里面不一定有元素数组中的元*

素直接跟随队列的重点设置为null即将迁移后的最后元素的后一个索引位置设置为null。

*

Like

类似于toArray()方法该方法行为可作为基于数组和基于集的API沟通的桥梁。

此外这种方法允许对输出数组的运行时类型进行精*

Suppose

假设一个队列已知只包含字符串。

下述代码可用于倾泻队列之一个新分配的字符串数组*

pre

Object[0])在功能上等同于toArray()其实还是不一样的如果队列中没有元素前者不会新分配数组。

**

param

如果足够大用于保存队列中所有元素的数组否则按计划分配一个相同运行时类型的新数组*

return

数组保存异常如果指定数组的运行时类型不是队列中每个元素的运行时类型的超类*

throws

转化数组返回一个包含优先级阻塞队列所有元素的数组。

该数组是重新分配的因此增删不会影响优先级阻塞队列。

数组中*

Description:

的元素是直接按元素数组中的原始顺序排列的并不是优先级阻塞队列的元素出队顺序。

如果传入的数组长度足够则直接将*

Description:

该数组返回否则会新分配第一个指定类型且大小与优先级阻塞队列相同的数组用于返回。

*/public

T[]

如果传入的数组长度不够直接通过拷贝返回一个包含所有元素且类型相同的泛型数组。

return

(T[])

如果传入的数组的长度足够则通过拷贝将队列中的元素拷贝到指定数组中。

System.arraycopy(queue,

n);//

返回一个遍历队列中元素的迭代器。

该迭代器不按任何特定的顺序返回元素即不按出队顺序。

*

The

hrefpackage-summary.html#Weaklyiweakly

consistent/i/a.*

直接将当前时间的元素数组拷贝作为迭代器可迭代的元素...这实现真容易...丫的数组阻塞队列能有这什么简单不就好了。

return

new

迭代器类直接将优先级阻塞队列的元素快照保存起来进行遍历由此可以完全不受有优先级阻塞队列的影响。

*/

final

用于持有当前节点中容纳的元素。

由于节点可能会被移除/拿取包括中途移除这种情况下节点都会被转化空节点因此元素需要额外保存。

lastRet上个索引

直接优先级阻塞队列的元素数组快照保存起来因此迭代器中保存所有要迭代的元素。

lastRet

-1;this.array

判断是否存在下个可迭代的元素。

如果存在返回true否则返回false。

/***

通过判断索引值是否合法来判断是否存在可迭代的元素。

return

cursor

将游标在元素数组快照中的对应元素返回并对游标进行递增。

return

(E)

判断是否进行过迭代或上个迭代的元素是否已经被移除如果是则抛出异常。

if

(lastRet

找到元素数组快照中保存的上个元素在元素数组中寻找并移除这个元素如果这个元素还存在的话。

removeEQ(array[lastRet]);//

将上个索引赋值为-1表示已移除。

因此当上个索引的值为-1时有两种可能一是尚未迭代二是上个迭代的元素已被移除。

lastRet

-1;}