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

Question

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

        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 (но я могу ошибаться)

Answer 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 мс

... и т. Д.

Answer 2

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

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

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

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

(оба keySet() и entrySet() являются дешевыми звонками)

Answer 3

Карта:

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

Помимо двух вариантов, есть еще один.

1) набор ключей () - используйте его, если вам нужно использовать только ключи

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

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

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

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

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

Answer 4

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

Answer 5

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

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

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

Answer 6

bguiz,

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

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

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

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

Версия 0 должна быть ПРОСТОЙ, КАК ВОЗМОЖНОЙ, без каких-либо «оптимизаций».

Answer 7

Наиболее эффективные способы (согласно моему тесту) - использовать новый метод HashMap.forEach(), добавленный в Java 8, или HashMap.entrySet().forEach().

JMH Benchmark:

@Param({"50", "500", "5000", "50000", "500000"})
int limit;
HashMap<String, Integer> m = new HashMap<>();
public Test() {
}
@Setup(Level.Trial)
public void setup(){
    m = new HashMap<>(m);
    for(int i = 0; i < limit; i++){
        m.put(i + "", i);
    }
}
int i;
@Benchmark
public int forEach(Blackhole b){
    i = 0;
    m.forEach((k, v) -> { i += k.length() + v; });
    return i;
}
@Benchmark
public int keys(Blackhole b){
    i = 0;
    for(String key : m.keySet()){ i += key.length() + m.get(key); }
    return i;
}
@Benchmark
public int entries(Blackhole b){
    i = 0;
    for (Map.Entry<String, Integer> entry : m.entrySet()){ i += entry.getKey().length() + entry.getValue(); }
    return i;
}
@Benchmark
public int keysForEach(Blackhole b){
    i = 0;
    m.keySet().forEach(key -> { i += key.length() + m.get(key); });
    return i;
}
@Benchmark
public int entriesForEach(Blackhole b){
    i = 0;
    m.entrySet().forEach(entry -> { i += entry.getKey().length() + entry.getValue(); });
    return i;
}
public static void main(String[] args) throws RunnerException {
    Options opt = new OptionsBuilder()
            .include(Test.class.getSimpleName())
            .forks(1)
            .warmupIterations(25)
            .measurementIterations(25)
            .measurementTime(TimeValue.milliseconds(1000))
            .warmupTime(TimeValue.milliseconds(1000))
            .timeUnit(TimeUnit.MICROSECONDS)
            .mode(Mode.AverageTime)
            .build();
    new Runner(opt).run();
}

Результаты:

Benchmark            (limit)  Mode  Cnt      Score    Error  Units
Test.entries              50  avgt   25      0.282 ±  0.037  us/op
Test.entries             500  avgt   25      2.792 ±  0.080  us/op
Test.entries            5000  avgt   25     29.986 ±  0.256  us/op
Test.entries           50000  avgt   25   1070.218 ±  5.230  us/op
Test.entries          500000  avgt   25   8625.096 ± 24.621  us/op
Test.entriesForEach       50  avgt   25      0.261 ±  0.008  us/op
Test.entriesForEach      500  avgt   25      2.891 ±  0.007  us/op
Test.entriesForEach     5000  avgt   25     31.667 ±  1.404  us/op
Test.entriesForEach    50000  avgt   25    664.416 ±  6.149  us/op
Test.entriesForEach   500000  avgt   25   5337.642 ± 91.186  us/op
Test.forEach              50  avgt   25      0.286 ±  0.001  us/op
Test.forEach             500  avgt   25      2.847 ±  0.009  us/op
Test.forEach            5000  avgt   25     30.923 ±  0.140  us/op
Test.forEach           50000  avgt   25    670.322 ±  7.532  us/op
Test.forEach          500000  avgt   25   5450.093 ± 62.384  us/op
Test.keys                 50  avgt   25      0.453 ±  0.003  us/op
Test.keys                500  avgt   25      5.045 ±  0.060  us/op
Test.keys               5000  avgt   25     58.485 ±  3.687  us/op
Test.keys              50000  avgt   25   1504.207 ± 87.955  us/op
Test.keys             500000  avgt   25  10452.425 ± 28.641  us/op
Test.keysForEach          50  avgt   25      0.567 ±  0.025  us/op
Test.keysForEach         500  avgt   25      5.743 ±  0.054  us/op
Test.keysForEach        5000  avgt   25     61.234 ±  0.171  us/op
Test.keysForEach       50000  avgt   25   1142.416 ±  3.494  us/op
Test.keysForEach      500000  avgt   25   8622.734 ± 40.842  us/op

Как видите, HashMap.forEach и HashMap.entrySet().forEach() лучше всего работают на больших картах и ​​объединены циклом for на entrySet() для лучшей производительности на маленьких картах.

Причина, по которой методы ключей медленнее, возможно, в том, что им приходится снова искать значение для каждой записи, в то время как другим методам просто нужно прочитать поле в объекте, которому они уже должны получить значение. Причина, по которой я ожидаю, что методы итератора будут медленнее, заключается в том, что они выполняют внешнюю итерацию, которая требует двух вызовов метода (hasNext и next) для каждого элемента, а также сохранения состояния итерации в объекте итератора, в то время внутренняя итерация, выполняемая forEach, требует всего одного вызова метода для accept.

Чтобы получить более точный результат, вам нужно профилировать на целевом оборудовании целевые данные и выполнять целевое действие в циклах.