江苏龙网

  1. 首页 > 人文 > >

#美团#Java面试题：集合高频要点问题你能答上来吗？( 五 )


DelayQueue 延迟队列提供了在指定时间才能获取队列元素的功能 ， 队列头元素是最接近过期的元素 。 没有过期元素的话 ， 使用 poll() 方法会返回 null 值 ， 超时判定是通过 getDelay(TimeUnit.NANOSECONDS) 方法的返回值小于等于 0 来判断 。 延时队列不能存放空元素 。
添加的元素必须实现 java.util.concurrent.Delayed 接口：
@Test
public void testLinkedList() throws InterruptedException {
DelayQueue<Person> queue = new DelayQueue<>();
queue.add(new Person());
System.out.println(\"queue.poll() = \" + queue.poll(200TimeUnit.MILLISECONDS));
static class Person implements Delayed {
@Override
public long getDelay(TimeUnit unit) {
// 这个对象的过期时间
return 100L;
@Override
public int compareTo(Delayed o) {
//比较
return o.hashCode() - this.hashCode();
输出 :
queue.poll() = null
LinkedTransferQueue 是 JDK1.7 加入的无界队列 ， 亮点就是无锁实现的 ， 性能高 。 Doug Lea 说这个是最有用的 BlockingQueue 了 ， 性能最好的一个 。 Doug Lea 说从功能角度来讲 ， LinkedTransferQueue 实际上是 ConcurrentLinkedQueue、SynchronousQueue（公平模式）和 LinkedBlockingQueue 的超集 。 他的 transfer 方法表示生产必须等到消费者消费才会停止阻塞 。
生产者会一直阻塞直到所添加到队列的元素被某一个消费者所消费（不仅仅是添加到队列里就完事） 。 同时我们知道上面那些 BlockingQueue 使用了大量的 condition 和 lock ， 这样效率很低 ， 而 LinkedTransferQueue 则是无锁队列 。 他的核心方法其实就是 xfer() 方法 ， 基本所有方法都是围绕着这个进行的 ， 一般就是 SYNC、ASYNC、NOW 来区分状态量 。 像 put、offer、add 都是 ASYNC ， 所以不会阻塞 。 下面几个状态对应的变量 。
private static final int NOW = 0; // for untimed poll tryTransfer(不阻塞) private static final int ASYNC = 1; // for offer put add(不阻塞) private static final int SYNC = 2; // for transfer take(阻塞) private static final int TIMED = 3; // for timed poll tryTransfer (waiting)
7. (小顶堆) 优先队列 PriorityQueue 的实现？
小顶堆是什么：任意一个非叶子节点的权值都不大于其左右子节点的权值 。
PriorityQueue 是非线程安全的 ， PriorityBlockingQueue 是线程安全的 。
两者都使用了堆 ， 算法原理相同 。
PriorityQueue 的逻辑结构是一棵完全二叉树 ， 就是因为完全二叉树的特点 ， 他实际存储确实可以为一个数组的 ， 所以他的存储结构其实是一个数组 。
首先 java 中的 PriorityQueue 是优先队列 ， 使用的是小顶堆实现 ， 因此结果不一定是完全升序 。
8. 自己实现一个大顶堆？
/**
* 构建一个 大顶堆
*
* @param tree
* @param n
*/
static void build_heap(int[
tree int n) {
// 最后一个节点
int last_node = n - 1;
// 开始遍历的位置是 : 最后一个堆的堆顶(以最小堆为单位)
int parent = (last_node - 1) / 2;
// 递减向上遍历
for (int i = parent; i >= 0; i--) {
heapify(tree n i);
/**
* 递归操作
* @param tree 代表一棵树
* @param n 代表多少个节点
* @param i 对哪个节点进行 heapify
*/
static void heapify(int[
tree int n int i) {
【#美团#Java面试题：集合高频要点问题你能答上来吗？】


推荐阅读


上一篇：『』花蚊子来到中国不到50年，但人们白天已无法乘凉，它是何方神圣？

下一篇：『浏览器』Flash已死，Deno当立？