Java - Ist es gängige Praxis, eine Hashtable (z.B. HashMap) zu verwenden, um Objekte auf sich selbst abzubilden?

Question

Ich erstelle eine Java-Anwendung, die eine Vielzahl zufälliger Wörter speichern soll (die jederzeit hinzugefügt oder aus der Anwendung gelöscht werden können). Ich möchte schnelle Suchvorgänge durchführen, um festzustellen, ob ein bestimmtes Wort im Wörterbuch enthalten ist oder nicht. Welche Java-Datenstruktur wäre dafür am besten geeignet? Ich dachte daran, eine hashMap zu verwenden und dasselbe Wort sowohl als Wert als auch als Schlüssel für diesen Wert zu verwenden. Ist das gängige Praxis? Es erscheint mir seltsam, dass dasselbe Wort sowohl als Schlüssel als auch als Wert in einem (Schlüssel, Wert)-Paar verwendet wird, daher wollte ich sicherstellen, dass ich keine bessere Idee übersehe.

Ich dachte auch daran, alternativ eine treeMap zu verwenden, um die Wörter sortiert zu halten, was mir eine Suchzeit von O(lgn) geben würde, aber die hashMap sollte eine erwartete Suchzeit von O(1) haben, so wie ich es verstehe, also dachte ich, dass das besser wäre.

Also möchte ich einfach nur sicherstellen, dass die Idee mit der hashMap und den Zeichenfolgen, die jeweils als Schlüssel und Wert in jedem (Schlüssel, Wert)-Paar dienen, eine gute Entscheidung wäre. Vielen Dank.

Answer 1

Ich möchte schnelle Nachschlagen, um zu sehen, ob ein bestimmtes Wort im Wörterbuch vorhanden ist oder nicht. Welche Java-Datenstruktur wäre dafür am besten?

Dies ist der klassische Anwendungsfall für ein Set. Sie können ein HashSet verwenden. Die naive Implementierung für Set verwendet eine entsprechende Map, um einfach zu kennzeichnen, ob der Eintrag existiert oder nicht.

Answer 2

Wenn Sie es als eine Sammlung von Wörtern in einem Wörterbuch speichern, würde ich vorschlagen, sich Tries anzusehen. Sie benötigen weniger Speicher als ein Set und ermöglichen schnelle Suchzeiten im schlechtesten Fall von O(String-Länge).

Answer 3

Jede Klasse, die ein Set ist, sollte Ihrem Zweck dienen. Beachten Sie jedoch, dass ein Set keine Duplikate zulässt. Selbst ein Map erlaubt keine doppelten Schlüssel. Ich würde vorschlagen, stattdessen ein ArrayList zu verwenden (sofern keine Synchronisierung erforderlich ist), wenn Sie doppelte Einträge hinzufügen und sie separat behandeln möchten.

Answer 4

Meine einzige Sorge wäre der Speicher, wenn Sie HashSet verwenden und eine sehr große Wortkollektion haben... Dann müssen Sie die gesamte Kollektion im Speicher laden... Wenn das kein Problem ist.... (Und Ihre Sammlung muss sehr groß sein, damit dies ein Problem ist)... Dann sollte das HashSet in Ordnung sein... Wenn Sie tatsächlich eine sehr große Wortkollektion haben, können Sie versuchen, einen Baum zu verwenden und nur die Teile im Speicher zu laden, die Sie interessieren.

Denken Sie auch daran, dass das Einfügen schnell ist, aber nicht so schnell wie in einem Baum, denken Sie daran, dass Java jedes Element sortiert einfügt. Wieder nichts Wesentliches, aber wenn Sie viele Wörter gleichzeitig hinzufügen, sollten Sie vielleicht einen Baum verwenden...