1.简介
PriorityBlockingQueue是一个基于优先级堆的无界的并发安全的队列，队列中的元素可以按照自然顺序也可以根据构造器提供的Comparator进行排序。
堆是一种二叉树结构，堆的根元素是整个树的最大值或最小值，然后堆的子树也满足对结构。
PriorityBlockingQueue通过ReentrantLock实现线程安全，同时通过Condition实现阻塞唤醒。
2.主要方法
2.1offer
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 (cmp == null)
siftUpComparable(n, e, array); //所有插入都用从底向上调整
else
siftUpUsingComparator(n, e, array, cmp);
size = n + 1;
notEmpty.signal(); //添加后通知非空条件队列可以take
} finally {
lock.unlock();
}
return true;
}
//数组扩容
private void tryGrow(Object[] array, int oldCap) {
lock.unlock(); // 数组扩容的时候使用自旋锁，不需要锁主锁，先释放
Object[] newArray = null;
if (allocationSpinLock == 0 &&
UNSAFE.compareAndSwapInt(this, allocationSpinLockOffset,
0, 1)) { //cas占用自旋锁
try {
int newCap = oldCap + ((oldCap < 64) ?
(oldCap + 2) : // grow faster if small
(oldCap >> 1)); //这里容量最少是翻倍
if (newCap - MAX_ARRAY_SIZE > 0) { // possible overflow
int minCap = oldCap + 1;
if (minCap < 0 || minCap > MAX_ARRAY_SIZE)
throw new OutOfMemoryError();
newCap = MAX_ARRAY_SIZE; //扩容后，默认最大
}
if (newCap > oldCap && queue == array)
newArray = new Object[newCap];
} finally {
allocationSpinLock = 0; //扩容后释放自旋锁
}
}
if (newArray == null) // 到这里如果是本线程扩容newArray肯定是不为null，为null就是其他线程在处理扩容，那就让给别的线程处理
Thread.yield();
lock.lock(); //这里重新重入锁，因为扩容后还有其他操作
if (newArray != null && queue == array) { //这里不为null那就复制数组
queue = newArray;
System.arraycopy(array, 0, newArray, 0, oldCap);
}
}
//所有插入都用从下向上调整
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) //如果比父节点大，那就无所谓退出，直接放在k位置
break;
array[k] = e; //比父节点小，按照k位置给父节点，然后从父节点开始继续向上查找
k = parent;
}
array[k] = key;
}
//所有插入都用从底向上调整，跟siftUpComparable方法类似就是比较的时候使用了构造传入的comparator
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;
}
2.2 poll
public E poll() {
final ReentrantLock lock = this.lock;
lock.lock();
try {
return dequeue();
} finally {
lock.unlock();
}
}
public E take() throws InterruptedException {
final ReentrantLock lock = this.lock;
lock.lockInterruptibly(); //响应中断
E result;
try {
while ( (result = dequeue()) == null)
notEmpty.await(); //如果take，数组没有元素是要阻塞的
} finally {
lock.unlock();
}
return result;
}
public E poll(long timeout, TimeUnit unit) throws InterruptedException {
long nanos = unit.toNanos(timeout);
final ReentrantLock lock = this.lock;
lock.lockInterruptibly(); //响应中断
E result;
try {
while ( (result = dequeue()) == null && nanos > 0)
nanos = notEmpty.awaitNanos(nanos); //响应超时，每次唤醒的超时时间要检查
} finally {
lock.unlock();
}
return result;
}
public E peek() {
final ReentrantLock lock = this.lock;
lock.lock();
try {
return (size == 0) ? null : (E) queue[0]; //只是获取元素，不移除
} finally {
lock.unlock();
}
}
//获取的基本都调用这个方法
private E dequeue() {
int n = size - 1;
if (n < 0)
return null;
else {
Object[] array = queue;
E result = (E) array[0];
E x = (E) array[n]; //将最后一个数组元素取出作为比较基准
array[n] = null; //出队，最后一个数组清掉，相当于堆的最底层最右的叶子节点清掉
Comparator<? super E> cmp = comparator;
if (cmp == null)
siftDownComparable(0, x, array, n); //从顶向下调整
else
siftDownUsingComparator(0, x, array, n, cmp);
size = n;
return result;
}
}
//从顶向下调整
private static <T> void siftDownComparable(int k, T x, Object[] array,
int n) {
if (n > 0) { //元素数量大于0,数组非空
Comparable<? super T> key = (Comparable<? super T>)x;
int half = n >>> 1; // 最后一个叶子节点的父节点位置
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) //如果待调整key最小，那就退出，直接赋值
break;
array[k] = c; //如果key不是最小，那就取左右节点小的那个放到调整位置，然后小的那个节点位置开始再继续调整
k = child;
}
array[k] = key;
}
}
2.3 remove
public boolean remove(Object o) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
int i = indexOf(o); //查找o在数组中位置
if (i == -1)
return false;
removeAt(i); //remove掉
return true;
} finally {
lock.unlock();
}
}
//o在数组中的位置
private int indexOf(Object o) {
if (o != null) {
Object[] array = queue;
int n = size;
for (int i = 0; i < n; i++)
if (o.equals(array[i]))
return i;
}
return -1;
}
//remove掉数组指定位置的元素
//跟之前take的dequeue相似的地方，dequeue是remove掉0的位置，然后调整也是从0的位置开始调整，这里是从指定位置调整
private void removeAt(int i) {
Object[] array = queue;
int n = size - 1;
if (n == i) // removed last element
array[i] = null;
else {
E moved = (E) array[n]; //跟dequeue一样也是最后一个叶子节点作为比较
array[n] = null;
Comparator<? super E> cmp = comparator;
if (cmp == null)
siftDownComparable(i, moved, array, n); //从指定位置调整
else
siftDownUsingComparator(i, moved, array, n, cmp);
//经过从上向下调整后，如果是直接将比较节点放在待调整位置，那只能说明这个节点在以它为堆顶的堆里面最小，但不能说明从这个节点就向上查找就最大
//这里需要自底向上再来一次调整
if (array[i] == moved) {
if (cmp == null)
siftUpComparable(i, moved, array);
else
siftUpUsingComparator(i, moved, array, cmp);
}
}
size = n;
}
网友评论