Java源码分析

• 阅读源码
• PriorityQueue

阅读源码

• 好处：能学习到更优秀的代码，提高代码架构能力，深入理解代码设计思想，理解框架设计
• 原则：
  • 文档：先阅读官方文档，标记不理解的地方，和期望深入了解的地方，着重理解设计思路和关键技术
  • 定焦：抓主线，带着文档中的问题，找到相关代码，再深入阅读
  • 宏观：站在上帝视角，关注整体设计思路，不要试图去深入每一个细节
• 方法、技巧：
  • 断点
  • 反调（Find Usages)
  • 经验（例如源码看多了，就知道某些命名的方法是用来干什么的）

PriorityQueue

offer处的源码

private void siftUpUsingComparator(int k, E x) {
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = queue[parent];
        if (comparator.compare(x, (E) e) >= 0)
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = x;
}

k是数组最后的位置，也就是二叉树的最后新增节点，x表示insert的元素；

若x与其父节点相比，小于其父节点，继续循环比较，直到大于等于其父节点，默认二叉树构成小顶堆。

pq默认的comparator实现为：

public int Comparator.compare(int insertValue, int parentValue) {
	return insertValue - parentValue;
}

第一个入参为插入值，因此自实现Comparator时，如果需要将小优先，也就实现insertValue-parentValue。如果大的优先，则反过来。