Производительность Hashmap vs Array

Лучше ли использовать (с точки зрения производительности) массивы или HashMaps, когда известны индексы массива? Имейте в виду, что "массив объектов/карта" в примере является всего лишь примером, в моем реальном проекте он генерируется другим классом, поэтому я не могу использовать отдельные переменные.

ArrayExample:

SomeObject[] objects = new SomeObject[2];
objects[0] = new SomeObject("Obj1");
objects[1] = new SomeObject("Obj2");

void doSomethingToObject(String Identifier){
    SomeObject object;
    if(Identifier.equals("Obj1")){
        object=objects[0];
    }else if(){
        object=objects[1];
    }
    //do stuff
}

HashMapExample:

HashMap objects = HashMap();
objects.put("Obj1",new SomeObject());
objects.put("Obj2",new SomeObject());

void doSomethingToObject(String Identifier){
    SomeObject object = (SomeObject) objects.get(Identifier);
    //do stuff
}

HashMap выглядит намного лучше, но мне действительно нужна производительность, поэтому он имеет приоритет.

EDIT: Ну массив, тогда предложения все же приветствуются

EDIT: Я забыл упомянуть, что размер массива /HashMap всегда один и тот же (6)

EDIT: Похоже, что HashMaps быстрее Массив: 128 мс Хэш: 103 мс

При использовании меньших циклов HashMaps был даже в два раза быстрее

тестовый код:

import java.util.HashMap;
import java.util.Random;

public class Optimizationsest {
private static Random r = new Random();

private static HashMap<String,SomeObject> hm = new HashMap<String,SomeObject>();
private static SomeObject[] o = new SomeObject[6];

private static String[] Indentifiers = {"Obj1","Obj2","Obj3","Obj4","Obj5","Obj6"};

private static int t = 1000000;

public static void main(String[] args){
    CreateHash();
    CreateArray();
    long loopTime = ProcessArray();
    long hashTime = ProcessHash();
    System.out.println("Array: " + loopTime + "ms");
    System.out.println("Hash: " + hashTime + "ms");
}

public static void CreateHash(){
    for(int i=0; i <= 5; i++){
        hm.put("Obj"+(i+1), new SomeObject());
    }
}

public static void CreateArray(){
    for(int i=0; i <= 5; i++){
        o[i]=new SomeObject();
    }
}

public static long ProcessArray(){
    StopWatch sw = new StopWatch();
    sw.start();
    for(int i = 1;i<=t;i++){
        checkArray(Indentifiers[r.nextInt(6)]);
    }
    sw.stop();
    return sw.getElapsedTime();
}



private static void checkArray(String Identifier) {
    SomeObject object;
    if(Identifier.equals("Obj1")){
        object=o[0];
    }else if(Identifier.equals("Obj2")){
        object=o[1];
    }else if(Identifier.equals("Obj3")){
        object=o[2];
    }else if(Identifier.equals("Obj4")){
        object=o[3];
    }else if(Identifier.equals("Obj5")){
        object=o[4];
    }else if(Identifier.equals("Obj6")){
        object=o[5];
    }else{
        object = new SomeObject();
    }
    object.kill();
}

public static long ProcessHash(){
    StopWatch sw = new StopWatch();
    sw.start();
    for(int i = 1;i<=t;i++){
        checkHash(Indentifiers[r.nextInt(6)]);
    }
    sw.stop();
    return sw.getElapsedTime();
}

private static void checkHash(String Identifier) {
    SomeObject object = (SomeObject) hm.get(Identifier);
    object.kill();
}

}

Ответы

Ответ 1

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

Random.nextInt() во много раз медленнее, чем те, которые вы тестируете, даже при использовании массива для проверки массива будет искажать ваши результаты.

Причина, по которой ваш тестовый массив настолько медленный, объясняется сравнением сравнений, а не доступом к массиву.

HashTable обычно намного медленнее, чем HashMap, потому что он делает то же самое, но также синхронизируется.

Общей проблемой с микро-бенчмарками является JIT, которая очень хорошо удаляет код, который ничего не делает. Если вы не будете осторожны, вы будете тестировать только то, запутали ли вы JIT, что он не может тренироваться, ваш код ничего не делает.

Это одна из причин, по которой вы можете написать микро-тесты, которые выполняют С++-системы. Это связано с тем, что Java является более простым языком и легче рассуждать и, следовательно, обнаруживать код, который ничего не полезен. Это может привести к испытаниям, которые показывают, что Java "ничего полезного" намного быстрее, чем С++;)

Ответ 2

когда индексы известны быстрее (HashMap использует массив связанных списков за кулисами, что добавляет немного надстройки над доступом к массиву, не говоря уже о хэш-операциях, которые необходимо выполнить)

и FYI HashMap<String,SomeObject> objects = HashMap<String,SomeObject>(); делает так, что вам не придется бросать

Ответ 3

В показанном примере побеждает HashTable. Проблема с методом массива заключается в том, что он не масштабируется. Я предполагаю, что вы хотите иметь более двух записей в таблице, а дерево ветвей condition в doSomethingToObject быстро станет неудобным и медленным.

Ответ 4

Логически, HashMap определенно подходит для вашего случая. С точки зрения производительности также выигрывает, так как в случае массивов вам нужно будет выполнять ряд сравнений строк (в вашем алгоритме), в то время как в HashMap вы просто используете хэш-код, если коэффициент загрузки не слишком высок. И массив, и HashMap необходимо будет изменить размер, если вы добавите много элементов, но в случае HashMap вам также необходимо будет перераспределить элементы. В этом случае HashMap теряет.

Ответ 5

Массивы обычно быстрее, чем классы коллекций.

PS. Вы упомянули HashTable в своем посте. HashTable имеет еще худшую производительность, чем HashMap. Я предполагаю, что ваше упоминание о HashTable было опечаткой

"HashTable выглядит очень много лучше"

Ответ 6

Пример странный. Основная проблема заключается в том, являются ли ваши данные динамическими. Если это так, вы не могли бы написать программу таким образом (как в случае с массивом). Для слов, сравнение между вашим массивом и хэш-реализацией не справедливо. Реализация хеша работает для динамических данных, но реализация массива не выполняется.

Если у вас есть только статические данные (6 фиксированных объектов), массив или хеш просто работают как держатель данных. Вы даже можете определить статические объекты.

Ответ 7

Пожалуйста, никогда не используйте расширенный if/else if/else if/else if/else if/else, если такие случаи. Причина, по которой я повторял это много раз, - это просто заставить вас почувствовать, что ваш интерпретатор java делает, когда он сталкивается с такими блоками кода.

Как только у вас будет более одного, если либо используйте хэш-карту, либо переключатель /case (java 7 позволит вам сделать это на Strings, а java 6 - перечислить). Еще лучшим решением для проверки только для чтения является ImmutableMap из фреймворка, такого как guava; они имеют высоко оптимизированные чтения, поскольку они не позволяют выполнять записи.