Java: Итерация через HashMap, которая более эффективна?

Учитывая следующий код, с двумя альтернативными способами итерации через него,
Есть ли разница в производительности между этими двумя методами?

        Map<String, Integer> map = new HashMap<String, Integer>();
        //populate map

        //alt. #1
        for (String key : map.keySet())
        {
            Integer value = map.get(key);
            //use key and value
        }

        //alt. #2
        for (Map.Entry<String, Integer> entry : map.entrySet())
        {
            String key = entry.getKey();
            Integer value = entry.getValue();
            //use key and value
        }

Я склонен думать, что alt. #2 является более эффективным средством повторения через весь map (но я мог ошибаться)

Ответ 1

Ваши второй вариант определенно более эффективен, так как вы выполняете поиск только один раз по сравнению с n количеством раз в первом варианте.

Но ничто не держится лучше, чем пытаться, когда сможешь. Итак, здесь идет -

(Не идеально, но достаточно хорошо, чтобы проверить допущения и на моей машине)

public static void main(String args[]) {

    Map<String, Integer> map = new HashMap<String, Integer>();
    // populate map

    int mapSize = 500000;
    int strLength = 5;
    for(int i=0;i<mapSize;i++)
        map.put(RandomStringUtils.random(strLength), RandomUtils.nextInt());

    long start = System.currentTimeMillis();
    // alt. #1
    for (String key : map.keySet()) {
        Integer value = map.get(key);
        // use key and value
    }
    System.out.println("Alt #1 took "+(System.currentTimeMillis()-start)+" ms");

    start = System.currentTimeMillis();
    // alt. #2
    for (Map.Entry<String, Integer> entry : map.entrySet()) {
        String key = entry.getKey();
        Integer value = entry.getValue();
        // use key and value
    }
    System.out.println("Alt #2 took "+(System.currentTimeMillis()-start)+" ms");
}

РЕЗУЛЬТАТЫ (некоторые интересные)

С int mapSize = 5000; int strLength = 5;
Alt # 1 занял 26 мс
Alt # 2 занял 20 мс

С int mapSize = 50000; int strLength = 5;
Alt # 1 занял 32 мс
Alt # 2 занял 20 мс

С int mapSize = 50000; int strLength = 50;
Alt # 1 занял 22 мс
Alt # 2 занял 21 мс

С int mapSize = 50000; int strLength = 500;
Alt # 1 занял 28 мс
Alt # 2 занял 23 мс

С int mapSize = 500000; int strLength = 5;
Alt # 1 занял 92 мс
Alt # 2 занял 57 мс

... и т.д.

Ответ 2

Второй фрагмент будет немного быстрее, так как ему не нужно повторно искать ключи.

Итераторы HashMap вызывают метод nextEntry, который возвращает Entry<K,V>.

Ваш первый фрагмент отбрасывает значение из записи (в KeyIterator), а затем снова ищет его в словаре.

Второй фрагмент использует ключ и значение напрямую (из EntryIterator)

(Оба keySet() и entrySet() дешевые звонки)

Ответ 3

Последний эффективнее первого. Инструмент, подобный FindBugs, фактически обозначит первое и предложит вам сделать последнее.

Ответ 4

Карта

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

Помимо двух опций, есть еще один.

1) keySet() - используйте его, если вам нужно использовать только клавиши

for ( String k : map.keySet() ) {
    ...
}

2) entrySet() - используйте его, если вам нужны оба: ключи и значения

for ( Map.Entry<String, Integer> entry : map.entrySet() ) {
    String k = entry.getKey();
    Integer v = entry.getValue();
    ...
}

3) значения() - используйте его, если вам нужны только значения

for ( Integer v : map.values() ) {
    ...
}

Ответ 5

bguiz,

Я думаю (я не знаю), что итерация EntrySet (альтернатива 2) немного более эффективна, просто потому, что она не имеет хэша для каждого ключа, чтобы получить его значение... Сказав это, вычисляя хэш является операцией O (1) для каждой записи, и поэтому мы ТОЛЬКО говорим O (n) по всему HashMap... но обратите внимание, что все это относится только к HashMap... другим реализациям Map могут иметь ОЧЕНЬ разные характеристики производительности.

Я действительно думаю, что вы будете "подталкивать", чтобы на самом деле ЗАМЕЧАТЬ разницу в производительности. Если вы заинтересованы, почему бы не настроить тестовый сценарий во время обоих методов итерации?

Если у вас нет РЕАЛЬНОЙ, сообщившей о проблеме производительности, то вы действительно беспокоитесь о не очень... Несколько тиков часов здесь и там не повлияют на общее удобство использования вашей программы.

Я считаю, что многие, многие другие аспекты кода, как правило, важнее, чем прямая работа. Конечно, некоторые блоки являются "критичными по производительности", и это известно до того, как оно даже написано, без проблем протестировано... но такие случаи довольно редки. В качестве общего подхода лучше сосредоточиться на написании полного, правильного, гибкого, проверяемого, многоразового, читаемого, поддерживаемого кода... производительность CAN может быть построена позже, по мере необходимости.

Версия 0 должна быть AS SIMPLE AS ВОЗМОЖНА без каких-либо "оптимизаций".

Ответ 6

В общем, второй будет немного быстрее для HashMap. Это действительно имеет значение, если у вас много хэш-коллизий, так как тогда вызов get(key) становится медленнее, чем O(1) - он получает O(k), а k - количество записей в одном и том же ведре (т.е. Число ключи с одним и тем же хэш-кодом или другим хеш-кодом, который по-прежнему отображается в одном и том же ведре - это зависит от емкости, размера и коэффициента загрузки на карте).

Вариант ввода-итерации не должен выполнять поиск, поэтому здесь он становится немного быстрее.

Другое примечание. Если емкость вашей карты намного больше фактического размера, и вы часто используете итерации, вы можете вместо этого использовать LinkedHashMap. Он обеспечивает O(size) вместо O(size+capacity) сложность для полной итерации (а также предсказуемый порядок итерации). (Вы все равно должны измерять, действительно ли это дает улучшение, поскольку факторы могут отличаться. LinkedHashMap имеет большие накладные расходы для создания карты.)