Список дан на картев качестве значений, как я могу найти один или несколько ключей, которые имеют наибольший размер списка Java

Question

Я написал метод, который возвращает карту.Структура карты:

Map<String, List<String>> map;

Карта может содержать более 1000 ключей, и каждый ключ может содержать список размером более 10000.Я хочу получить те ключи, которые имеют самый большой размер списка.Есть ли какой-нибудь подход, чтобы получить результат за минимальное время, если это возможно?

Answer 1

Вы все еще можете сделать это, используя java-steam API:

  Map<String, List<Integer>> map = Map.of(
                                        "a",List.of(1,2),
                                        "b",List.of(3,4,5,6),
                                        "c",List.of(7,8,9)
                                   );

Запись с максимальным размером списка:

Optional<Map.Entry<String, List<Integer>>> max = map.entrySet()
                    .stream()
                    .max(Comparator.comparingInt(value -> value.getValue().size()));

карта с записями с максимальным размером списка:

Integer maxSize = max.get().getValue().size();
Map<String, List<Integer>> maxMap = map
        .entrySet()
        .stream()
        .filter(entry -> entry.getValue().size() == maxSize)
        .collect(Collectors.toMap(Map.Entry::getKey,Map.Entry::getValue));

или, наконец, вы можете отсортировать карту и сохранить результат в LinkedHashMap:

LinkedHashMap<String, List<Integer>> sortedMap = map
        .entrySet()
        .stream()
        .sorted(Comparator.comparingInt(value -> value.getValue().size()))
        .collect(
                Collectors.toMap(
                        Map.Entry::getKey,
                        Map.Entry::getValue,
                        (u, v) -> {
                            throw new IllegalStateException(String.format("Duplicate key %s", u));
                        }, 
                        LinkedHashMap::new 
                )
        );

Answer 2

Сгруппируйте записи по размеру списка значений в структуре данных, которая поможет вам найти самый большой ключ:

TreeMap<Integer, List<Entry<String, List<String>>>> collect =
    map.entrySet().stream()
        .collect(groupingBy(e -> e.getValue().size(), TreeMap::new, toList()));

(Вы можете получить только ключи, используя mapping(Map.Entry::getKey, toList()) вместо toList()).

Затем получите записи с наибольшим размером, используя:

List<Map.Entry<String, List<String>>> largestEntries =
    grouped.lastEntry().getValue();

Конечно, вы можете сделать это и без потоков, без сохранения всех записей, которые меньше, чем самые большие.:

List<Map.Entry<String, List<String>>> largestEntries = new ArrayList<>();
// Don't need both this and largestEntries;
// just adding to show how you'd only get keys.
List<String> largestKeys = new ArrayList<>();  
int largestSize = Integer.MIN_VALUE;

for (Map.Entry<String, List<String>> entry : map.entrySet()) {
  if (entry.getValue().size() > largestSize) {
    largestEntries.clear();
    largestEntries.add(entry);
    largestKeys.add(entry.getKey());
    largestSize = entry.getValue().size();
  } else if (entry.getValue().size() == largestSize) {
    largestEntries.add(entry);
    largestKeys.add(entry.getKey());
  }
}

Answer 3

Используя потоки, вы могли бы составить решение, которое повторяет все записи вашей карты, выбирает размер каждого списка, чтобы в итоге предоставить тот ключ, который имеет список "максимального" размера.Или вы следуете совету Николаса в ответе и применяете этот подход «старой школы».

Проблема в том, что если вам нужно делать это очень часто, это все равно может превратиться в проблему производительности.С этой точки зрения вы должны спросить себя, действительно ли этот «макет» ваших данных вам нужен.

Значение: вместо использования карты вы можете использовать TreeMap и назначить этому специальный компаратор.Который затем сортирует записей вашей карты на основе длины этих списков.Тогда вы просто выбираете «первую» запись, и вы получаете своего победителя.Недостатком здесь является то, что компаратор работает только с ключами, входящими в карту, поэтому вам, вероятно, понадобится какой-то особый «класс-обертка», где ключ знает о размере списка.Это ужасно.

В качестве альтернативы, вы можете создать специальную «карту обертывания», которая внутри содержит две карты:

• a TreeMap<Integer, String>, которые отображают списокразмеры к вашим "реальным" ключам карты
• , которые действительны Map<String, List<String>>, которые содержат ваши фактические данные.

Answer 4

Использование функции фильтрации потоков java8:

Map <String, List<String>> map = new HashMap<>();

Map <String, List<String>> filteredMap = map.entrySet().stream()
                    .filter(stringListEntry -> stringListEntry.getValue().size() > 100)
                    .limit(10)
                    .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue));

`

Answer 5

Если производительность является приоритетом, забудьте о java-streams и используйте собственный подход, используя простую итерацию for-loop.

String maxKey;
int maxSize = -1;

for (Entry<String, List<String>> list: map.entrySet()) {
    int size = list.getValue().size();
    if (size  > maxSize) {
        maxKey = list.getKey();
        maxSize = size;
    }
}

Если вы хотите сохранить все ключи с максимумом, сохраните их в Set<String> и замените условие на:

int size = list.getValue().size();
if (size  == maxSize) {
    maxKeySet.add(list.getKey());
}
if (size  > maxSize) {
    maxKeySet.clear();
    maxKeySet.add(list.getKey());
    maxSize = size;
}