V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
amiwrong123
V2EX  ›  Java

PriorityBlockingQueue 的构造器好奇怪啊?

  •  
  •   amiwrong123 · 2020-08-03 21:28:56 +08:00 · 1837 次点击
    这是一个创建于 1333 天前的主题,其中的信息可能已经有所发展或是发生改变。
        public PriorityBlockingQueue(Collection<? extends E> c) {
            this.lock = new ReentrantLock();
            this.notEmpty = lock.newCondition();
            boolean heapify = true; // true if not known to be in heap order
            boolean screen = true;  // true if must screen for nulls
            if (c instanceof SortedSet<?>) {
                SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
                this.comparator = (Comparator<? super E>) ss.comparator();
                heapify = false;
            }
            else if (c instanceof PriorityBlockingQueue<?>) {
                PriorityBlockingQueue<? extends E> pq =
                    (PriorityBlockingQueue<? extends E>) c;
                this.comparator = (Comparator<? super E>) pq.comparator();
                screen = false;
                if (pq.getClass() == PriorityBlockingQueue.class) // exact match  第一处
                    heapify = false;
            }
            Object[] a = c.toArray();
            int n = a.length;
            // If c.toArray incorrectly doesn't return Object[], copy it.
            if (a.getClass() != Object[].class)  //第二处
                a = Arrays.copyOf(a, n, Object[].class);
            if (screen && (n == 1 || this.comparator != null)) {  //第三处
                for (int i = 0; i < n; ++i)
                    if (a[i] == null)
                        throw new NullPointerException();
            }
            this.queue = a;
            this.size = n;
            if (heapify)
                heapify();
        }
    
    1. 为什么一定要if (pq.getClass() == PriorityBlockingQueue.class)才不用重新建堆( heapify 为 false,就不用重新建堆),大概意思就是 PriorityBlockingQueue 的子类可能重写了方法,所以可能 PriorityBlockingQueue 的子类的内部数组根本不是堆吗?

    2. 为什么当if (a.getClass() != Object[].class)时,就一定要新建一个类型为Object[].class的数组,即使两个数组里面的元素都是一样的。而且意思 c.toArray()返回的实际类型不一定是Object[].class了呗

    3. if (screen && (n == 1 || this.comparator != null))时重新检查有没有 null 元素,但是后面的(n == 1 || this.comparator != null)不是很理解为什么这么判断?

    看最近的 jdk 的源码也是这样,http://hg.openjdk.java.net/jdk/jdk15/file/d2c6eb3b2c8d/src/java.base/share/classes/java/util/concurrent/PriorityBlockingQueue.java#l242 ,应该不是版本问题。

    求大佬们不吝赐教

    4 条回复    2020-08-04 22:11:56 +08:00
    mind3x
        1
    mind3x  
       2020-08-04 04:11:07 +08:00   ❤️ 1
    哇,非常好的问题。先尝试回答第 2 个:

    PriorityBlockingQueue<E>的类型参数 E 本身没有类型约束(例如 E extends Comparable<E>),因此在 PriorityBlockingQueue 的实现内部,要插入或删除一个 E 类型的元素时,是通过先把元素强转成接口类型 Comparable<? super E>,再进行比较,再赋值给对应的位置 queue[???]。例如

    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)
    break;
    array[k] = e;
    k = parent;
    }
    array[k] = key;
    }

    这里的问题是,如果 queue 不是在构造函数里初始化成 Object[]类型,而是 E[]类型,上面的 array[k] = key 将会导致 ArrayStoreException 。例如,如果 E 是 Integer,cast 成 Comparable 没问题,但 Comparable 不是 Integer,没法存回 Integer[]。所以 queue 需要初始化成什么都能存的 Object[]。

    但其实还有更简单的办法——把 array[k]=key 改成 array[k] = x,queue 就可以安安全全的使用 E[] type,也不需要那么多强制转型。至于为什么 Java 没这么做,就不是我能回答的了。

    至于 PriorityBlockingQueue<E>为什么不直接声明成 PriorityBlockingQueue<E extends Comparable<E>>,是因为 PriorityBlockingQueue 同时支持 Comparable 和 Comparator 两种比较接口,插入删除都是两种版本,E 的类型约束都是靠运行时强制转型的动态检查,没法静态声明。
    amiwrong123
        2
    amiwrong123  
    OP
       2020-08-04 11:49:47 +08:00
    @mind3x
    谢谢回复

    原来如此,大概就是:
    Integer[] array = new Integer[5];
    Comparable<?> aa = (Comparable<?>)(new Integer(1));
    array[4] = aa;//编译报错

    我也很好奇为什么不把 array[k]=key 改成 array[k] = x,这样构造器里面就不用转换数组类型了嘛

    PriorityBlockingQueue<E>的声明,你不提醒我,我都没注意到这一点。
    amiwrong123
        3
    amiwrong123  
    OP
       2020-08-04 21:58:54 +08:00
    @mind3x
    大佬,还想问个问题:
    就是你 1 楼给的泛型函数里,
    为什么一定要声明 Comparable<? super T> key = (Comparable<? super T>) x;
    我觉得声明成 Comparable<T> key = (Comparable<T>) x;就完全可以了啊,完全不理解为啥这样。

    因为 key.compareTo((T) e)比较时,也是和确定的 T 类型进行比较的啊。
    mind3x
        4
    mind3x  
       2020-08-04 22:11:56 +08:00
    @amiwrong123
    这里我怀疑原因是这样:这个 contravariant 类型 <? super T> 对于使用 Comparator 的情形是有意义的,例如有 type B, D 并且 D extends B,PriorityBlockingQueue<D>可以使用 Comparator<D>,但是也可以使用 Comparator<B>,因此一般这种情况会允许 Comparator<? super T>。
    但 Comparable 是 obj.comparesTo(other),这里用 contravariant 类型没有意义,因为类型擦除,运行时毫无区别,大概只是实习生照着 Comparator 分支抄过来的……
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3238 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 33ms · UTC 13:56 · PVG 21:56 · LAX 06:56 · JFK 09:56
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.