Wie wähle ich einen zufälligen Schlüssel aus einer HashMap in Java?

Ich habe eine Lösung ohne Leistungsverlust gefunden. Ich werde es hier posten, da es anderen Leuten helfen kann - und möglicherweise mehrere offene Fragen zu diesem Thema beantwortet (ich werde später danach suchen).

Was Sie brauchen, ist eine zweite benutzerdefinierte Set - ähnliche Datenstruktur, um die Schlüssel zu speichern - nicht eine Liste wie einige hier vorgeschlagen. Listenähnliche Datenstrukturen sind zu teuer, um Objekte zu entfernen. Die erforderlichen Operationen sind das Hinzufügen / Entfernen von Elementen in konstanter Zeit (um mit der HashMap auf dem neuesten Stand zu bleiben) und eine Prozedur zum Auswählen des Zufallselements. Die folgende Klasse MySet macht genau dies

von meinem Kopf

dann nur

Klingt so, als sollten Sie entweder eine zusätzliche Liste von Schlüsseln oder ein reales Objekt, nicht eine Map, in Ihrer Liste speichern.

Sie benötigen Zugriff auf die zugrunde liegende Eingabetabelle.

Dies muss immer noch die Einträge durchlaufen, um einen zu finden, der da ist, also ist der schlechteste Fall O (n), aber das typische Verhalten ist O (1).

Ich gehe davon aus, dass Sie HashMap verwenden, da Sie zu einem späteren Zeitpunkt etwas nachschlagen müssen?

Wenn nicht, ändern Sie einfach Ihre HashMap in eine Array / ArrayList .

Wenn das der Fall ist, speichern Sie Ihre Objekte nicht in Map UND ArrayList , damit Sie nach dem Zufallsprinzip oder nach Schlüssel suchen können.

Alternativ könnten Sie eine TreeMap anstelle von HashMap verwenden? Ich weiß nicht, welchen Typ Ihr ​​Schlüssel hat, aber Sie verwenden TreeMap.floorKey() in Verbindung mit einem Schlüssel-Randomizer.

Nach einiger Zeit bin ich zu dem Schluss gekommen, dass Sie ein Modell erstellen müssen, das mit einem List<Map<A, B>> und einem List<A> unterstützt werden kann, um Ihre Schlüssel zu verwalten. Sie müssen den Zugriff von List<Map<A, B>> und List<A> beibehalten und dem Aufrufer nur die Operationen / Methoden zur Verfügung stellen. Auf diese Weise haben Sie die volle Kontrolle über die Implementierung, und die tatsächlichen Objekte sind sicherer vor externen Änderungen.

Übrigens, Ihre Fragen führen mich zu

• Warum wird java.util verwendet? .Set & lt; V & gt; Schnittstelle bieten keine Get (Object o) -Methode? und
• Bimap : Ich habe versucht, schlau zu sein, aber Natürlich liefert seine Methode values() auch Set .
zurück

In diesem Beispiel, IndexedSet , erhalten Sie möglicherweise eine Vorstellung davon, wie zu.

[bearbeitet]

Diese Klasse, SetUniqueList , könnte Ihnen helfen, wenn Sie entscheiden sich, ein eigenes Modell zu erstellen. Es besagt explizit, dass es die list , nicht die Kopien, umschließt. Also, ich denke, wir können etwas wie,

Hinweis: Ich habe das selbst nicht versucht. Werde das später tun (nach Hause hetzen).

Holen Sie sich von Ihrem Map-Keyset mit map.keySet() und wählen Sie den zufälligen Schlüssel wie bei ArrayList . Dann können Sie Wert mit map.get(randomKey) erhalten.

Wenn Sie unbedingt auf das Entry-Array in HashMap zugreifen müssen, können Sie reflection verwenden. Aber dann hängt Ihr Programm von dieser konkreten Implementierung von HashMap ab.

Wie vorgeschlagen, können Sie eine separate Liste von Schlüsseln für jede Karte beibehalten. Sie würden keine tiefen Kopien der Schlüssel behalten, also wäre die tatsächliche Speicherdenormalisierung nicht so groß.

Der dritte Ansatz besteht darin, eine eigene Map-Implementierung zu implementieren, die Schlüssel in einer Liste statt in einem Satz enthält.

Wie wäre es mit HashMap in einer anderen Implementierung von Map? Die andere Karte enthält eine Liste und put ():

(Ich nehme an, dass Nullen für Werte nicht erlaubt sind, wenn sie useSkey verwenden, aber das ist langsamer)