Ich versuche, die Datenstruktur zu verwenden, speichern Schlüssel-Wert-Paare zu entscheiden, wann nur benötigten FunktionenWelche Datenstruktur ist für diese Situation geeignet?
- Insertion
- Lookup
Insbesondere brauche ich nicht in der Lage sein, um Paare zu löschen oder durch Schlüssel/Werte/Paare zu iterieren.
Die Schlüssel sind Ganzzahl-Tupel, die Werte sind Zeiger (Referenzen, was auch immer). Ich speichere nur ein paar Millionen Paare über (viele) Objekte verteilt.
Ich erwäge derzeit entweder mit
- eine Hash-Tabelle
- ein kd-Baum
- ein B-Baum
Ich bin zu der Hash-Tabelle lehnt (für die O(1) Insertion/Lookup-Zeit), aber ich wollte meine Neigungen bestätigen.
Welche Struktur (von den oben genannten oder anderen) würden Sie empfehlen und warum? Wenn Sie eine Hash-Tabelle empfehlen, sollte ich eine separate Tabelle für jedes Objekt erstellen oder einfach eine einzelne Tabelle erstellen und die ID des Objekts als Teil des Schlüsseltupels verwenden?
Ein kd-Baum ist eine räumliche Datenstruktur - es macht keinen Sinn, sie in dieser Situation zu verwenden. Meinst du einen rot-schwarzen Baum? –
Wie werden Sie diese Datenstruktur verwenden? Machst du alle Inserts im Vordergrund oder mischst du sie mit den Lookups? Wie viele Nachschlagevorgänge erwarten Sie gegenüber Einfügungen? Sind die Schlüssel einzigartig? Wie viele Schlüssel gibt es (2^64?). Wie sind sie verteilt? – Dolphin