如何通过比较值对 HashMap 的条目进行排序，其中每个值都是一个 int[]？

Question

我有一个定义为 HashMap<String, int[]> 的 HashMap。该值是一个 int[]，其中正好有 2 个数字。我想要做的是根据这两个数字的总和对这个 HashMap 的条目进行排序。

这是我的资料。我正在使用 Java 8。我只需要添加我在 int[] 中对 2 ints 求和的部分，并将其视为一个数字，然后按照下面的操作进行排序，但我是不确定如何添加该部分。

hm.entrySet().stream()
    .sorted(Map.Entry.comparingByValue(Comparator.reverseOrder()))

Answer 1

我很确定您不能使用 HashMap 创建排序元素。我的建议是使用另外 2 个地图：

Map<Integer,String> tempMap = new TreeMap<Integer,String>();
Map<String,int []> resultMap = new LinkedHashMap<String,int[]>();

首先您需要将您的hm 映射复制到tempMap 中，TreeMap 中的自然排序将按升序排列您的整数键。

在tempMap中得到排序结果后，可以复制到resultMap中得到最终结果。

"Copy" 表示您迭代旧地图，然后将 (key,value) 放入新地图中。

这种方法会消耗你双倍的内存，但它会运行复杂度为 O(n lg n)。

如果要使用Comparator，可以使用这种方式：

hm.entrySet().stream().sorted(Map.Entry.comparingByValue(
    new Comparator<int []>() {
    public int compare(int [] a,int [] b) {
        int sumA = a[0] + a[1];
        int sumB = b[0] + b[1];
        return sumA - sumB;
    }
}));

Answer 2

这个答案实际上是受 Hesham Attia 的另一个答案的启发，可以作为问题的替代解决方案。

不过，我也借此机会讨论溢出 int 数据类型的潜在问题（详见下文）。

此解决方案使用接口 Comparator.comparingLong() 和 keyExtractor，而不是接口 Map.Entry.comparingByValue() 和 comparator。

（如果我们不够小心，两者都可能会发生数据溢出——请参阅下面的测试 2 和 3。）

hm.entrySet()
    .stream()
    .sorted(Comparator.comparingLong(
                e -> ((long) e.getValue()[0])+e.getValue()[1]
           ))

这是一个完整的测试程序，中间演示了失败的测试2和3。排序的正确答案应该是e, b, c, a, d（如Test 4所示）

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;

public class StreamSortedIntArray {

    public static void main(String[] args) {
        Map<String, int[]> hm = new HashMap<>();
        hm.put("a", new int[]{3, 1});
        hm.put("b", new int[]{1, 1});
        hm.put("c", new int[]{2, 1});
        hm.put("d", new int[]{Integer.MAX_VALUE, 1});
        hm.put("e", new int[]{Integer.MIN_VALUE, 1});

        // Test 1: 
        System.out.println("Test 1: hm before sorting: ");

        hm.entrySet()
            .stream()
            .forEach(StreamSortedIntArray::printEntry);

        // Test 2: 
        System.out.println("Test 2: hm after sort -- using Map.Entry.comparingByValue()"); 
        hm.entrySet()
            .stream()
            .sorted(Map.Entry.comparingByValue(
                        (v1, v2) -> v2[0] + v2[1] - v1[0] - v1[1]))
            .forEach(StreamSortedIntArray::printEntry);

        // Test 3: After sorting -- using Comparator.comparingLong()
        // WITHOUT protection against data overflowing the int type
        System.out.println("Test 3: hm after sorting: (using Comparator.comparingLong())"); 
        System.out.println("WITHOUT protection against data overflowing the int type"); 
        hm.entrySet()
            .stream()
            .sorted(Comparator.comparingLong(
                        e -> e.getValue()[0]+e.getValue()[1]
                   ))
            .forEach(StreamSortedIntArray::printEntry);

        // Test 4: After sorting -- using Comparator.comparingLong()
        // WITH protection against data overflowing the int type
        System.out.println("Test 4: hm after sorting: (using Comparator.comparingLong())"); 
        System.out.println("WITH protection against data overflowing the int type"); 
        hm.entrySet()
            .stream()
            .sorted(Comparator.comparingLong(
                        // protection against overflowing the int type
                        // cast to long before the sum operation
                        e -> ((long) e.getValue()[0])+e.getValue()[1]
                   ))
            .forEach(StreamSortedIntArray::printEntry);


    }

    public static void printEntry(Map.Entry<String, int[]> e) {
        String message
            = String.format("%s: %20s; sum=%d"
                            , e.getKey()
                            , Arrays.toString(e.getValue())
                            , ((long)(e.getValue()[0])+e.getValue()[1]));
        System.out.println(message);
    }

}

此程序的输出 -- 测试 4 显示正确答案，但测试 2 和 3 不正确：

Test 1: hm before sorting: 
a:               [3, 1]; sum=4
b:               [1, 1]; sum=2
c:               [2, 1]; sum=3
d:      [2147483647, 1]; sum=2147483648
e:     [-2147483648, 1]; sum=-2147483647
Test 2: hm after sort -- using Map.Entry.comparingByValue()
e:     [-2147483648, 1]; sum=-2147483647
d:      [2147483647, 1]; sum=2147483648
a:               [3, 1]; sum=4
c:               [2, 1]; sum=3
b:               [1, 1]; sum=2
Test 3: hm after sorting: (using Comparator.comparingLong())
WITHOUT protection against data overflowing the int type
d:      [2147483647, 1]; sum=2147483648
e:     [-2147483648, 1]; sum=-2147483647
b:               [1, 1]; sum=2
c:               [2, 1]; sum=3
a:               [3, 1]; sum=4
Test 4: hm after sorting: (using Comparator.comparingLong())
WITH protection against data overflowing the int type
e:     [-2147483648, 1]; sum=-2147483647
b:               [1, 1]; sum=2
c:               [2, 1]; sum=3
a:               [3, 1]; sum=4
d:      [2147483647, 1]; sum=2147483648

通过简单的减法实现比较器的危险

这个问题在上面的测试程序（测试二）中有体现，而且已经 Oracle/Sun 对象排序教程

中警告不要这样做

https://docs.oracle.com/javase/tutorial/collections/interfaces/order.html

One last note: You might be tempted to replace the final return statement in the Comparator with the simpler:

return e1.number() - e2.number();

Don't do it unless you're absolutely sure no one will ever have a negative employee number! This trick does not work in general because the signed integer type is not big enough to represent the difference of two arbitrary signed integers. If i is a large positive integer and j is a large negative integer, i - j will overflow and will return a negative integer. The resulting comparator violates one of the four technical restrictions we keep talking about (transitivity) and produces horrible, subtle bugs. This is not a purely theoretical concern; people get burned by it.

Answer 3

这是一个使用 Java 8 个比较器 lambda 的解决方案：

map.entrySet().stream()
              .sorted(Map.Entry.comparingByValue(
                      (v1, v2) -> v2[0] + v2[1] - v1[0] - v1[1]));

请注意，此解决方案存在 overflowing/underflowing 的风险，请参阅 leeyuiwah answer 以获得更好的解决方案。这个想法是改用 comparingLong 方法。

Answer 4

更通用的解决方案，使用适当的比较器（不影响可能的溢出问题），适用于任何长度的数组：

1) 由于无法对不保留键顺序的 HashMap 进行排序，我们需要创建新映射 - LinkedHashMap:

    Map<String, int[]> result = new LinkedHashMap<>();

2) 自行排序：

    map.entrySet().stream()
            .sorted(Map.Entry.comparingByValue(
                            (o1, o2) -> Integer.compare(Arrays.stream(o1).sum(), Arrays.stream(o2).sum()))
            )
    .forEach(se -> result.put(se.getKey(), se.getValue()));

UPD: 亲爱的@Holger 建议使用 Comparator.comparingInt(o -> Arrays.stream(o).sum())，它看起来更紧凑，但作用相同。就我个人而言，我的版本看起来更容易理解，但 Holger 的版本更 lambda-styler.

Answer 5

最简单且恕我直言的最佳方法是不使用 Map.Entry 比较方法，因为您不是通过键或值进行比较，而是通过派生值进行比较：

map.entrySet().stream()
    .sorted(Comparator.comparing(e -> 0 - e.getValue()[0] - e.getValue[1]))
    .forEach(<whatever>);

负值会创建您的代码所建议的相反顺序。

如何通过比较值对 HashMap 的条目进行排序，其中每个值都是一个 int[]？

How to sort a HashMap's entries by comparing values, where each value is an int[]?

java

sorting

dictionary

comparator

java-8