Java 中的这个 Lambda 表达式如何帮助排序？帮我理解

Question

这里的任务是获取输入字符串，例如 'tree' 并根据频率对其进行排序，输出应为 'eetr'/'eert'，因为 e 重复 2 次且 t,r 频率为 1 .

我有这段代码，它是做什么的，它遍历字符串，将字符串中的所有字符及其频率放入Hashmap中，并使用优先级队列对它们进行降序排序，然后将结果放入字符串中建设者，

但我需要一些帮助来理解优先级队列参数中使用的 lambda 函数。这是我的功能。

public String frequencySort(String s)          // lets assume that input string is "tree"
{
    HashMap<Character,Integer> map = new HashMap<>();
    for(char c:s.toCharArray())
    {
        map.put(c,map.getOrDefault(c,0) + 1);
    }                                                       //  now after this my HashMap will have values (t,1),(r,1),(e,2)

PriorityQueue<Character> maxHeap = new PriorityQueue<>((a,b) -> map.get(b) - map.get(a));  //my question is about this constructor in priority queue, There are just two input parameters , how subtracting two things will help in sorting ??

maxHeap.addAll(map.keySet()); // i guess the keyset is now 't,r,e'  but constructor has only 2 parameters, what is going on ? How will the constructor help in setting the sorting behaviour of prioroty queue? 

StringBuilder result = new StringBuilder();

    while(maxHeap.isEmpty())
    {
        char current = maxHeap.remove();
        for(int i=0;i < map.get(current);i++)
        {
            result.append(current);
        }
    }

}

谁能用函数中的示例 'tree' 向我解释流程

Answer 1

它与 Scala 中的 wordCount 示例非常相似。但它对字符串中的单词进行计数，而您的程序对单词中的字母进行计数。很像。

但是，地图输出如下：

(t,1), (r,1), (e,2)

map.get(b) - map.get(a)只是用作比较器。如果 map.get(b) - map.get(a) 为负，则表示 map.get(b) < map.get(a) 并且结果在 a 之前排序。如果为正则表示 map.get(b) > map.get(a) 并且结果在 a 之后排序。如果为零，则它们相等。

See Javadoc for PriorityQueue ：基于优先级堆的无界优先级队列。优先级队列的元素根据它们的自然顺序排序，或者由队列构造时提供的比较器排序，具体取决于使用的构造函数.

Answer 2

but constructor has only 2 parameters

没有，仔细看，在new PriorityQueue(...)中，...部分只包含一个东西——(a, b) -> map.get(b) - map.get(a)。 PriorityQueue<Character> 的构造函数需要一个 Comparator<Character> 类型的参数。 Comparator 是一个能够比较两个对象并判断哪个“更大”或者它们是否相等的对象。优先级队列将使用此 Comparator 对其元素进行排序。

如果您觉得 lambda 表达式令人困惑，不妨将代码重写为：

new PriorityQueue<>(Comparator.comparing(map::get).reversed());

意图应该更清楚，它做的事情大致相同。我们正在创建一个优先级队列，它应该通过比较我们通过对每个元素应用 map.get 获得的整数来比较其元素。换句话说，给定两个元素 a 和 b，队列应该通过比较 map.get(a) 和 map.get(b) 来决定哪个元素先出现。你想要 reverse 升序（即降序）。

在您的原始代码中，不是使用 return 是 Comparator<Character> 的 comparing 方法，而是使用 lambda 表达式，它基本上是 [=40= 的实现] 方法。如果您阅读该方法的文档，您会发现您应该：

return 如果第一个参数“小于”第二个参数，则为负整数
return 如果参数相等则为 0
return 如果第一个参数“大于”第二个参数，则为正整数

从数学上观察，如果 map.get(a) < map.get(b)，map.get(a) - map.get(b) 将为负数。 map.get(a) > map.get(b)时，map.get(a) - map.get(b)为正数，map.get(a) = map.get(b)时，map.get(a) - map.get(b)为0。

现在你应该明白为什么 map.get(b) - map.get(a) 通过比较每个元素应用 map.get 得到的整数来给你反向顺序。

杂项说明：

用减法实现Comparator其实不是个好主意，因为会溢出。有关详细信息，请参阅 here。
您的代码有两个 typos/mistakes。 1.最后少了一个return result.toString();语句 2.循环控制条件应该是while(!maxHeap.isEmpty())。你错过了 !.

Answer 3

我认为，像这样使用“隐式”比较器可能会非常混乱。 PriorityQueue 构造函数（自 Java 8 起）被定义为采用 java.util.Comparator 作为参数之一。 Comparator 接口指定一个函数 compare() 接受两个参数，returns 一个整数。整数的符号表示哪个元素较大。这就是为什么在 OP 中减去两个元素的值——如果它们相等，则结果将为零。如果一个比另一个大，则结果将是正数或负数。 PriorityQueue 实施使用这些应用于许多元素的结果来确定它们的放置顺序。

我认为，在兰巴表达式出现之前，这种逻辑是相当直观的。现在，Comparator 被声明为“功能接口”。这意味着可以直接从 lamba 表达式创建接口的匿名实例化。 Java 编译器知道 PriorityQueue 构造函数的参数是 Comparator，并且它知道根据 lambda 表达式实例化 Comparator。 lambda 表达式有两个参数，在本例中为 a 和 b。 Comparator 接口有一个接受两个参数的方法 -- compare (a,b)。因此有一个匹配可以用于代码生成。

因此 Java 生成的代码用 Comparator 的定义替换了 lamba 表达式，其 compare (a,b) 方法是 lambda 函数的实现（即，文本到->).

右边

我认为，造成这种潜在混淆的原因是 Comparator 接口本身是完全不可见的——您需要知道 PriorityQueue 有一个 Comparator 参数，并且Comparator 是一个函数式接口，它有一个方法和两个参数，compare()，匹配 lamba 表达式。

Java 中的这个 Lambda 表达式如何帮助排序？帮我理解

How does this Lambda expression in Java help in sorting ? help me understand

java

lambda

stringbuilder

priority-queue