Wydajność Hashmap vs Array

Czy (pod względem wydajności) lepiej używać tablic lub HashMaps, gdy indeksy tablicy są znane? Należy pamiętać, że 'objects array / map' w przykładzie jest tylko przykładem, w moim prawdziwym projekcie jest generowana przez inną klasę, więc nie mogę używać poszczególnych zmiennych.

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 one wygląda znacznie lepiej, ale naprawdę potrzebuję wydajności na tym, aby to miało priorytet.

EDIT: Cóż to jest następnie sugestie są nadal mile widziane

EDIT: zapomniałem wspomnieć, rozmiar tablicy / HashMap jest zawsze taki sam (6)

EDIT: wygląda na to, że Hashmapy są szybsze Array: 128MS Hash: 103ms

Przy użyciu mniejszej liczby cykli HashMaps był nawet dwa razy szybszy

Kod badania:

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();
}

}

Author: Tim, 2011-06-24

7 answers

HashMap używa tablicy pod spodem, więc nigdy nie może być szybsza niż prawidłowe użycie tablicy.

Random.nextInt() Jest wiele razy wolniejszy niż to, co testujesz, nawet używanie tablicy do testowania tablicy spowoduje pogorszenie wyników.

Powód, dla którego twój benchmark tablicy jest tak powolny, wynika z porównań równości, a nie samego dostępu do tablicy.

HashTable jest zwykle znacznie wolniejszy niż HashMap, ponieważ robi to samo, ale jest również zsynchronizowany.

Powszechny problem z micro-benchmarki to JIT, który jest bardzo dobry w usuwaniu kodu, który nic nie robi. Jeśli nie jesteś ostrożny, będziesz tylko testować, czy pomyliłeś JIT na tyle, że nie może ćwiczyć Twój kod nic nie robi.

Jest to jeden z powodów, dla których można pisać mikro-benchmarki, które wykonują systemy C++. Dzieje się tak dlatego, że Java jest prostszym językiem i łatwiejszym do rozumowania, a tym samym wykrywania kodu, który nie robi nic użytecznego. Może to prowadzić do testów, które pokazują, że Java robi" nic użytecznego " dużo szybciej niż C++;)
 29
Author: Peter Lawrey,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2018-04-02 08:43:50

Tablice, gdy indeksy są znane, są szybsze (HashMap używa tablicy połączonych list Za kulisami, która dodaje trochę nad tablicą dostępu, nie wspominając o operacjach haszujących, które należy wykonać)

And FYI HashMap<String,SomeObject> objects = HashMap<String,SomeObject>(); make it so you won ' t have to cast

 4
Author: ratchet freak,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-06-24 01:28:56

Na pokazanym przykładzie, HashTable wygrywa, jak sądzę. Problem z podejściem do tablicy polega na tym, że nie jest skalowana. Wyobrażam sobie, że chcesz mieć więcej niż dwa wpisy w tabeli, a drzewo gałęzi stanu w doSomethingToObject szybko stanie się nieporęczne i powolne.

 2
Author: sehe,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-06-24 00:16:53

Logicznie rzecz biorąc, HashMap zdecydowanie pasuje do twojego przypadku. Z punktu widzenia wydajności jest również wygrana, ponieważ w przypadku tablic będziesz musiał wykonać wiele porównań łańcuchowych (w algorytmie), podczas gdy w Hashmapie po prostu używasz kodu hashowego, jeśli współczynnik obciążenia nie jest zbyt wysoki. Zarówno tablica, jak i HashMap będą musiały zostać zmienione, jeśli dodasz wiele elementów, ale w przypadku Hashmapy będziesz musiał również redystrybuować elementy. W tym przypadku użycia HashMap przegrywa.

 2
Author: Alex Gitelman,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-06-24 00:20:37

Tablice będą zwykle szybsze niż klasy kolekcji.

PS. Wspomniałeś o HashTable w swoim poście. HashTable ma jeszcze gorszą wydajność niż HashMap. Zakładam, że Twoja wzmianka o HashTable była literówką

" The HashTable one looks much much lepiej "

 0
Author: Basanth Roy,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-06-24 00:19:12

Przykład jest dziwny. Kluczowym problemem jest to, czy dane są dynamiczne. Jeśli tak jest, to nie można napisać programu w ten sposób(jak w przypadku tablicy). W słowach porządkowych porównywanie pomiędzy implementacją tablicy i hasha nie jest sprawiedliwe. Implementacja hash działa dla danych dynamicznych, ale implementacja array nie.

Jeśli masz tylko dane statyczne (6 stałych obiektów), tablica lub hash działają tylko jako uchwyt danych. Można nawet zdefiniować obiekty statyczne.

 0
Author: BlueGuitar,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-06-24 01:19:07

Proszę, nigdy, przenigdy nie używaj extended if / else if / else if / else if / else if takich przypadków. Powodem, dla którego powtarzałem to tak wiele razy, jest to, że czujesz się tak, jak robi to Twój interpreter Javy, gdy uderza w takie bloki kodu.

Jak tylko będziesz miał więcej niż jeden if, albo użyj hashmapy, albo switch / case(java 7 pozwoli Ci to zrobić na ciągach, a java 6 musisz użyć enum). Jeszcze lepszym rozwiązaniem do sprawdzania tylko do odczytu jest mapa ImmutableMap z frameworka jak guawa; mają wysoce zoptymalizowane odczyty, ponieważ nie pozwalają na pisanie.

 0
Author: Ajax,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-04-19 07:40:10