Эффективный способ сортировки ключи HashMap Java

Question

дали hashMap и вернуть ключи hashmap в отсортированном порядке в arraylist Это функция API:

ArrayList<String> foo(HashMap<String,String> hashMap) 
{ 
} 

Теперь, есть два пути решения проблемы:

1. Возьмите все ключи в ArrayList, а затем отсортировать его
2. хранить ключи на карте в TreeSet, а затем хранить в rraylist и возвращение.

Бывший подход не будет использовать дополнительную космическую сложность, поскольку я не использую treeet. Клавиши являются буквенно-цифровыми. У кого будет меньше времени. Любой другой способ, который вы бы порекомендовали?

Answer 1

ответ будет зависеть! в области ключей. Существуют ситуации, когда хранение ключей в отсортированном порядке (то есть в дереве) очень эффективно. Однако я бы предположил, что в большинстве случаев будет более эффективным сортировать один раз, при извлечении.

Я попытался следующий код:

Map<Integer, Integer> map = new HashMap<>(); 
    Random random = new Random(); 
    random.ints(1000000).forEach(n -> map.put(n, n)); 
    long time1 = System.currentTimeMillis(); 
    Set<Integer> set = new TreeSet<>(map.keySet()); 
    List<Integer> list1 = new ArrayList<>(set); 
    long time2 = System.currentTimeMillis(); 
    List<Integer> list2 = new ArrayList<>(map.keySet()); 
    Collections.sort(list2); 
    long time3 = System.currentTimeMillis(); 
    System.out.println("Set approach " + (time2 - time1)); 
    System.out.println("Sort approach " + (time3 - time2)); 

Результат был 3768 и 1824, которые я подозреваю, что будет довольно типичным для двух подходов.

По сути интереса я также пытался:

List<Integer> list3 = map.keySet().stream().sorted().collect(Collectors.toList()); 

Результат был 537 миллисекунды: более чем в 3 раза быстрее, чем Collections.sort подход.

Однако, когда я повторен с 10 миллионов записей, три подхода принял

• 26,916 для TreeSet
• 2845 для Collection.sort
• 13,580 для Stream.sorted

Сделан вывод о том, что сортировке массив один раз намного эффективнее для больших карт.

Answer 2

В определенной степени это зависит от того, что вы собираетесь делать с «отсортированной» штукой впоследствии.

Но в вашем случае вы говорите: в конце вы хотите отсортированный список; таким образом: непосредственно создавайте список, сортируйте и возвращайте его!

Даже если оба подхода имеют одинаковую сложность (O (n * log (n)) - имейте в виду, что сортировка этого списка может быть, вероятно, быстрее (поскольку ему просто нужно перемещать элементы в массиве, вместо того чтобы создать множество узлов дерева)

другими словами:.. создавая что TreeList, чтобы затем превратить его в ArrayList означает наверняка много копирования будет продолжаться просто избежать этого