Производительность оператора HashMap vs Switch
A HashMap, по существу, имеет производительность O (1), в то время как состояние коммутатора может иметь либо O (1), либо O (log (n)) в зависимости от того, использует ли компилятор переключатель tablewitch или lookup.
Понятно, что если оператор switch написан как таковой,
switch (int) {
case 1:
case 2:
case 3:
case 4:
default:
}
тогда он будет использовать табличный интерфейс и, очевидно, имеет преимущество перед стандартным HashMap. Но что, если оператор switch разрежен? Это были бы два примера, которые я бы сравнивал:
HashMap<Integer, String> example = new HashMap<Integer, String>() {{
put(1, "a");
put(10, "b");
put(100, "c");
put(1000, "d");
}};
.
switch (int) {
case 1:
return "a";
case 10:
return "b";
case 100:
return "c";
case 1000:
return "d";
default:
return null;
}
Что обеспечит большую пропускную способность, lookupswitch или HashMap?
Накладные расходы на HashMap дают преимущество поиска раньше, но в конечном итоге сокращаются по мере увеличения числа случаев/записей?
Изменить: Я пробовал некоторые тесты с использованием JMH, вот мои результаты и используемые коды. https://gist.github.com/mooman219/bebbdc047889c7cfe612
Как вы, ребята, упомянули, оператор lookupswitch превзошел HashTable. Мне все еще интересно, почему.
Ответы
Ответ 1
Это зависит:
-
Если есть несколько предметов | фиксированные предметы. Используя переключатель, если можете (наихудший вариант O (n))
-
Если есть много элементов ИЛИ вы хотите добавить будущие элементы без изменения большого количества кода ---> Использование хэш-карты (время доступа считается постоянным)
-
Для вашего случая. Вы не должны беспокоиться о производительности, потому что разное время выполнения очень мало. Просто сфокусируйтесь на удобочитаемости и удобстве сопровождения вашего кода. Стоит ли оптимизировать простой случай для улучшения на несколько наносекунд?
Ответ 2
Принятый ответ здесь неправильный.
http://java-performance.info/string-switch-implementation/
Переключения всегда будут такими же быстрыми, как если бы они не были быстрее, чем хэш-карты. Операторы Switch преобразуются в таблицы прямого просмотра. В случае целочисленных значений (целых, перечислений, коротких, длинных) это прямой поиск /jmp в выражении. Нет необходимости в дополнительном хешировании. В случае String он предварительно вычисляет хеш-строку для операторов case и использует входной хеш-код String, чтобы определить, куда следует перейти. В случае столкновения он выполняет цепочку if/else. Теперь вы можете подумать: "Это то же самое, что и HashMap, верно?" Но это не правда. Хеш-код для поиска вычисляется во время компиляции и не уменьшается в зависимости от количества элементов (меньшая вероятность столкновения).
Переключатели имеют O (1), а не O (n). (Хорошо, по правде говоря, для небольшого числа элементов переключатели превращаются в операторы if/else. Это обеспечивает лучшую локальность кода и позволяет избежать дополнительных поисков в памяти. Однако для многих элементов переключатели превращаются в таблицу поиска, о которой я упоминал выше).
Вы можете прочитать больше об этом здесь. Как работает переключатель Java под капотом?
Ответ 3
В вашем случае, поскольку вы используете Integer
ключ для HashMap
и простой <<22 > для вашего оператора switch
, наиболее эффективной реализацией будет оператор switch
, если только число проходов через этот раздел кода очень высока (десятки или сотни тысяч).
Ответ 4
Если у меня есть такой пример, я использую Guava ImmutableMaps (конечно, вы можете использовать также и Java 9 Builder).
private static final Map<String, String> EXAMPLE = ImmutableMaps.<String, String>>builder()
.put("a", "100")
.put("b", "200")
.build();
Таким образом, они неизменны и инициируются только один раз.
Иногда я использую шаблон стратегии таким образом:
private static final Map<String, Command> EXAMPLE = ImmutableMaps.<String, String>>builder()
.put("a", new SomethingCool())
.put("b", new BCool())
.build();
private static final Command DEFAULT= new DefCommand();
Использование:
EXAMPLE.getOrDefault("a", DEFAULT).execute(); //java 8
О производительности просто выберите удобочитаемость. Вы будете благодарить меня позже (1 год спустя): D.