Indizierte Stringsammlung in Java

Question

Verwendung von Java, vorausgesetzt v1.6.

Ich habe eine Auflistung, in der der eindeutige Index eine Zeichenfolge ist und der nicht eindeutige Wert eine Zahl ist. Ich muss Tausende von Abfragen anhand dieser Sammlung so schnell wie möglich durchführen.

Ich verwende derzeit eine HashMap<String, Integer> aber ich bin besorgt, dass die Boxing/unboxing der Integer zu int macht dies langsamer.

Ich hatte an die Verwendung eines ArrayList<String> gekoppelt mit einem int[] .

d.h. Statt:

int value = (int) HashMap<String, Integer>.get("key");

Ich könnte

int value = int[ArrayList<String>.indexOf("key")];

Haben Sie eine Idee? Gibt es einen schnelleren Weg, dies zu tun?

p.s. Ich werde die Sammlung nur einmal erstellen und sie vielleicht einmal ändern, aber jedes Mal werde ich die Größe kennen, so dass ich die String[] 代わりに ArrayList aber nicht sicher, ob es einen schnelleren Weg gibt, indexOf zu replizieren...

Answer 1

Wenn die Kosten für die einmalige Erstellung der Karte keine Rolle spielen, sollten Sie sich folgende Optionen ansehen perfektes Hashing zum Beispiel Bob Jenkins' Code .

Answer 2

Hier gibt es ein kleines Problem: Sie können doppelte Elemente in einer Liste haben. Wenn Sie es wirklich auf die zweite Art machen wollen, sollten Sie stattdessen ein Set verwenden.

Haben Sie dennoch einen Leistungstest mit den beiden durchgeführt, um zu sehen, ob einer schneller ist als der andere?

Bearbeiten: Natürlich wird der beliebteste Set-Typ (HashSet) selbst von einer HashMap unterstützt, so dass der Wechsel zu einem Set vielleicht doch keine so kluge Änderung ist.

Answer 3

List.indexOf führt einen linearen Scan der Liste durch - typischerweise O(n). Eine binäre Suche erledigt die Aufgabe in O(log n). Eine Hash-Tabelle erledigt dies in O(1).

Eine große Anzahl von Integer Objekte im Speicher könnten ein Problem darstellen. Das Gleiche gilt aber auch für String s (sowohl die String et char[] ). Sie könnten Ihre eigene benutzerdefinierte DB-Stil-Implementierung zu tun, aber ich schlage vor, Benchmarking ersten.

Answer 4

Der Zugriff auf die Karte führt kein Unboxing für den Lookup durch, nur der spätere Zugriff auf das Ergebnis macht ihn langsam.

Ich schlage vor, einen kleinen Wrapper mit einem Getter für den int einzuführen, wie z.B. SimpleInt. Er hält den int ohne Konvertierung. Der Konstruktor ist nicht teuer und insgesamt ist billiger als ein Integer.

public SimpleInt
{
    private final int data;

    public SimpleInt(int i)
    {
        data = i;
    }

    // getter here
    ....
}