Leistung von HashMap vs. Switch-Anweisung

Eine HashMap hat im Wesentlichen eine Leistung von O(1), während ein Switch-Zustand entweder O(1) oder O(log(n)) haben kann, je nachdem, ob der Compiler einen Tableswitch oder einen Lookup-Switch verwendet.

Verständlicherweise, wenn eine switch-Anweisung als solche geschrieben wird,

switch (int) {
    case 1:
    case 2:
    case 3:
    case 4:
    default:
}

dann würde es einen Tabellenschalter verwenden und einen eindeutigen Leistungsvorteil gegenüber einer Standard-HashMap haben. Aber was ist, wenn die switch-Anweisung spärlich ist? Dies wären zwei Beispiele, die ich vergleichen würde:

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

Was würde mehr Durchsatz liefern, ein Lookupswitch oder HashMap? Gibt der Overhead der HashMap dem Lookupswitch frühzeitig einen Vorteil, lässt aber mit zunehmender Anzahl von Fällen/Einträgen nach?

Bearbeiten: Ich habe einige Benchmarks mit JMH ausprobiert, hier sind meine Ergebnisse und der verwendete Code. https://gist.github.com/mooman219/bebbdc047889c7cfe612
Wie Sie bereits erwähnt haben, hat die Lookupswitch-Anweisung die HashTable übertroffen. Ich frage mich aber immer noch warum.

Die akzeptierte Antwort ist hier falsch.

http://java-performance.info/string-switch-implementation/

Switches sind immer so schnell, wenn nicht sogar schneller als Hash-Maps. Switch-Anweisungen werden in direkte Nachschlagetabellen umgewandelt. Bei Integer-Werten (ints, enums, shorts, longs) ist es ein direkter Lookup/JMP zur Anweisung. Es muss kein zusätzliches Hashing durchgeführt werden. Im Fall eines Strings wird der String-Hash für die Case-Anweisungen vorberechnet und der Hashcode des Eingabe-Strings verwendet, um zu bestimmen, wohin gesprungen werden soll. Im Falle einer Kollision führt es eine if/else-Kette aus. Jetzt denken Sie vielleicht: “Das ist dasselbe wie HashMap, oder?” Aber das stimmt nicht. Der Hash-Code für die Suche wird zur Kompilierzeit berechnet und nicht basierend auf der Anzahl der Elemente reduziert (geringere Kollisionswahrscheinlichkeit).

Switches haben O(1) Lookup, nicht O(n). (Ok, in Wahrheit werden Schalter für eine kleine Anzahl von Elementen in if/else-Anweisungen umgewandelt. Dies bietet eine bessere Codelokalität und vermeidet zusätzliche Speichersuchen. Bei vielen Elementen werden Schalter jedoch in die oben erwähnte Nachschlagetabelle geändert).

Sie können hier mehr darüber lesen. Wie funktioniert Javas Schalter unter der Haube?

Es hängt davon ab, ob:

1. Wenn es ein paar Artikel sind | feste Gegenstände. Verwenden Sie den Schalter, wenn Sie können (im schlimmsten Fall O (n))

2. Wenn es viele Elemente gibt ODER Sie zukünftige Elemente hinzufügen möchten, ohne viel Code zu ändern —> Hash-Map verwenden (Zugriffszeit wird als konstante Zeit betrachtet)

3. Sie sollten NICHT versuchen, die Leistung für den Fall zu verbessern, da der Unterschied in der Ausführungszeit Nanosekunden beträgt. Konzentrieren Sie sich einfach auf die Lesbarkeit/Wartbarkeit Ihres Codes. Lohnt es sich, einen einfachen Fall zu optimieren, um ein paar Nanosekunden zu verbessern?

TL/DR

Basieren Sie auf der Lesbarkeit und Wartbarkeit des Codes. Beide kosten O (1) und bieten fast keinen Unterschied (obwohl Switches im Allgemeinen etwas schneller sind).

In diesem speziellen Fall wäre eine Karte schneller, da ein Schalter eine Adresse zurückgibt und dann zu dieser Adresse gehen muss, um den Rückgabewert zu identifizieren. (Ein seltenes Fallbeispiel). Wenn Ihr Switch sowieso nur Funktionen aufruft, wäre eine Map auch schneller.

Um die Dinge schneller zu machen, würde ich sicherstellen, dass numerische Fälle verwendet werden, und die Verwendung von Zeichenfolgen über Konstanten oder Enumeratoren (Typoskript) vermeiden.

(bearbeitet) Ich habe erwartungsgemäß bestätigt: Wie funktioniert der Schalter von Java unter der Haube? mit Schaltern.

Ausführlichere Antwort

Im Unkraut:

Eine Switch-Anweisung ist normalerweise leistungsstärker. Es erstellt eine Nachschlagetabelle und eine Goto-Referenz und beginnt an diesem Punkt. Es gibt jedoch Ausnahmen.

Wenn Sie einen einfachen Schalter wie return map.get(x) vs. switch(1=>’a’, 2=>’b’, etc) verwenden. Das liegt daran, dass die Zuordnung den gewünschten Wert direkt zurückgeben kann, wo der Schalter die Zuordnung der Adressen beendet und fortfährt, bis die Unterbrechung oder das Ende erreicht ist.

In jedem Fall sollten sie hinsichtlich der Ausführungskosten äußerst ähnlich sein.

Denken Sie an die Wartbarkeit und Lesbarkeit des Codes

Die Verwendung einer Karte entkoppelt die Daten, was den Vorteil der dynamischen Erstellung von „Switch“-Fällen bringen kann. Näheres unten.

Wenn Sie mehrere komplexe Funktionen/Prozesse handhaben müssen, ist es möglicherweise einfacher zu lesen/schreiben, wenn Sie stattdessen eine Karte verwenden. Vor allem, wenn die Switch-Anweisung 20 oder 30 Optionen überschreitet.

Persönlich verwendetes Fallbeispiel für Karten:

Ich verwende seit einiger Zeit das folgende Muster für Flussmittel (Redux/useReducer) in React-Anwendungen.

Ich erstelle eine zentrale Karte, in der ich den Trigger als Schlüssel abbilde und der Wert eine funktionale Referenz ist. Ich kann dann Fälle laden, wo und wann es sinnvoll ist.

Ursprünglich habe ich dies verwendet, um die Anwendungsfälle aufzuschlüsseln, um die Dateigröße zu reduzieren und Fälle mit ähnlicher Funktion organisierter zusammenzufassen. Obwohl ich es später so weiterentwickelt habe, dass es in Domänen geladen werden kann, und die Ereignisse und Daten in einem Domänen-Hook konfiguriert habe, wie useUser, useFeedback, useProfile usw.

Dadurch konnte ich den Standardzustand, Initialisierungsfunktionen, Ereignisse usw. in einer logischen Dateistruktur erstellen und den Platzbedarf bis zur Verwendung gering halten.

Eine Anmerkung zu beachten

Die Verwendung einer Karte erlaubt kein Drop-Through, obwohl die meisten Leute diesen Code sowieso als Geruch betrachten. Gleichzeitig schützt es vor versehentlichem Durchfallen.

In Ihrem Fall, da Sie eine verwenden Integer Schlüssel für Ihre HashMap und ein einfaches ‘int‘ für dein switch -Anweisung ist die Implementierung mit der besten Leistung die switch -Anweisung, es sei denn, die Anzahl der Durchläufe durch diesen Codeabschnitt ist sehr hoch (Zehn- oder Hunderttausende).

Wenn ich ein solches Beispiel habe, verwende ich Guava ImmutableMaps (sicher, Sie können auch Java 9 Builder verwenden).

private static final Map<String, String> EXAMPLE = ImmutableMaps.<String, String>>builder()
    .put("a", "100")
    .put("b", "200")
    .build(); 

Auf diese Weise sind sie unveränderlich und werden nur einmal initiiert.

Manchmal verwende ich Strategiemuster auf diese Weise:

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

Verwenden:

EXAMPLE.getOrDefault("a", DEFAULT).execute(); //java 8

Über die Leistung wählen Sie einfach die Lesbarkeit. Du wirst mir später (1 Jahr später) danken :D.