写点什么

PriorityQueue 源码解析 (二)

作者:知识浅谈
  • 2022-10-16
    吉林
  • 本文字数:1589 字

    阅读完需:约 1 分钟


🍁 作者:知识浅谈,CSDN 博客专家,阿里云签约博主,InfoQ 签约博主,华为云云享专家

📌 擅长领域:全栈工程师、爬虫、ACM 算法

💒 公众号:知识浅谈


PriorityQueue 源码解析(二)总结

🤞这次都给他拿下🤞

正菜来了⛳⛳⛳

🎈PriorityQueue 源码解析-函数篇

上篇中谈到了initElementsFromCollectioninitFromPriorityQueueinitFromCollection这两个函数。


三个函数的调用路径:


🍮initFromPriorityQueue

含义: 见名知意,从一个有限队列中初始化当前队列,首先判断 c 是不是优先队列,如果是的话,直接把当前队列中数组 queue 指向 c 队列的转化成的数组,size 指向 c 的大小。


private void initFromPriorityQueue(PriorityQueue<? extends E> c) {    if (c.getClass() == PriorityQueue.class) {        this.queue = c.toArray();        this.size = c.size();    } else {        initFromCollection(c);    }}
复制代码


上边如果传入的不是优先队列,就可以调用 initFromCollection,从集合中初始化当前队列。

🍮initFromCollection

含义: 使用给定集合中的元素初始化队列数组。这个就不想上边的那个,这个直接调用了 initElementsFromCollection(c).


private void initFromCollection(Collection<? extends E> c) {    initElementsFromCollection(c);    heapify();}
复制代码


接着看 initElementsFromCollection 这个函数的操作。

🍮initElementsFromCollection

含义: 从下边的函数的具体实现中可以看出,先把集合 c 转换为一个 Object 数组,然后对数组的类型以及数组中间的元素进行检查,查看是否有 null 的,如果有就抛出异常,如果没有就把当前创建的优先队列对象的 queue 指向 a。


 private void initElementsFromCollection(Collection<? extends E> c) {     Object[] a = c.toArray();     // If c.toArray incorrectly doesn't return Object[], copy it.     if (a.getClass() != Object[].class)         a = Arrays.copyOf(a, a.length, Object[].class);     int len = a.length;     if (len == 1 || this.comparator != null)         for (int i = 0; i < len; i++)             if (a[i] == null)                 throw new NullPointerException();     this.queue = a;     this.size = a.length; }
复制代码


函数中涉及到的 heapify()之后再分析。

🍮grow(int minCapacity)

含义: Increases the capacity of the array.增加队列中的容量,从下边的函数中可以判断扩容的时候先判断旧容量是否小于 64,如果小于就在原有的数量上加 2,否则就扩大一倍容量,之后再调用 hugeCapacity 判断新容量是都大于 MAX_ARRAY_SIZE,大于的话判断传递过来的 minCapacity 是否大于 MAX_ARRAY_SIZE,是的话就返回 Integer 的最大值。


private void grow(int minCapacity) {    int oldCapacity = queue.length;    // Double size if small; else grow by 50%    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);}
复制代码

🍮int hugeCapacity(int minCapacity)

含义:从这个函数中可以看出,会对传入的 minCapacity 进行判断是否大于 MAX_ARRAY_SIZE,大于的话就返回 Integer.MAX_VALUE,也就是整数的最大值,否则就返回 MAX_ARRAY_SIZE。


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

🍚总结

以后就是关于 PriorityQueue 中源码中的部分函数的总结,希望有所帮助。

发布于: 刚刚阅读数: 3
用户头像

知识浅谈

关注

公众号:知识浅谈 2022-06-22 加入

🍁 作者:知识浅谈,InfoQ签约作者,CSDN博客专家/签约讲师,华为云云享专家,阿里云签约博主,51CTO明日之星 📌 擅长领域:全栈工程师、爬虫、ACM算法 💒 公众号:知识浅谈 🔥 联系方式vx:zsqtcc

评论

发布
暂无评论
PriorityQueue 源码解析(二)_Priority Queue_知识浅谈_InfoQ写作社区