Как отсортировать записи HashMap, сравнивая значения, где каждое значение является int []?

Question

У меня есть HashMap, определяемый как HashMap<String, int[]>. Значение - int[], в котором будет ровно 2 цифры. То, что я хочу сделать, это сортировать записи HashMap по сумме этих двух чисел.

Вот что у меня есть. Я использую Java 8. Мне просто нужно добавить часть, где я суммирую 2 ints в int[] и рассматривать ее как одно число, а затем сортировать, как я делаю ниже, но я не уверен, как добавить эту часть.

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

Answer 1

Вот решение с Java 8 Компаратор лямбды:

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

Обратите внимание, что это решение имеет риск перелива/Опустошений см leeyuiwah answer для лучшего решения этого. Идея заключается в том, чтобы вместо этого использовать метод comparingLong.

Answer 2

Я уверен, что вы не можете создать элемент заказа с помощью HashMap. Мое предложение заключается в использовании 2 других карт:

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

Сначала вам нужно скопировать гм карту в tempMap, естественное упорядочение в TreeMap будет заказать целочисленный ключ в порядке возрастания.

После получения отсортированного результата в tempMap вы можете скопировать в resultMap, чтобы получить окончательный результат.

«Копировать» означает, что вы перебираете свою старую карту, а затем кладете (ключ, значение) на новую карту.

Этот подход будет стоить вам двойной памяти, но он будет работать со сложностью O (n lg n).

Если вы хотите использовать компаратор, вы можете использовать этот подход:

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 3

Этот ответ был действительно вдохновлен другой ответ по Хешам Аттиа и может рассматриваться в качестве альтернативного решения вопроса.

Тем не менее, я также использую эту возможность, чтобы обсудить потенциальную проблему переполнения типа данных int (см. Ниже).

Данное решение использует интерфейс Comparator.comparingLong(), а не интерфейс 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 (показано в испытании 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 

опасность реализации компаратора простого вычитанием

Эта проблема показана в приведенной выше программе испытаний (Test 2), но и была предостерегал против в Oracle/Sun Tutorial на объекте заказа

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

последнее замечание: Вы можете попытаться заменить окончательное возвращение заявление в компараторе с более простым:

возвратного e1.number() - e2.number();

Не делайте этого, если вы не являетесь абсолютно уверены, что ни у кого никогда не будет отрицательного номера сотрудника! Этот трюк делает вообще неработоспособным, потому что целочисленный тип со знаком не достаточно большой , чтобы представить разность двух произвольных значащих целых чисел. Если i равно большое положительное целое число, а j - большое отрицательное целое число, i-j будет переполнения и вернет отрицательное целое число. Полученный компаратор нарушает одно из четырех технических ограничений, которые мы продолжаем говорить о (транзитивность) и производит ужасные, тонкие ошибки. Это не теоретическая проблема ; люди обжигаются им.

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()), который выглядит более компактным, но выполняет ту же работу. Для меня лично моя версия выглядит более понятной, но у Хольгера больше лямбда-стайлера.

Answer 5

Простейший и лучший способ ИМХО - не использовать карту.Вступление методы сравнения, потому что вы не сравниваете с помощью ключа или значения, но с помощью выведенного значения:

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

Отрицательных значения создают перевернутый порядок код предполагает, вы хотите.