So wählen Sie einen zufälligen Schlüssel aus einer HashMap in Java?

Arbeite ich mit einem großen ArrayList<HashMap<A,B>>, und ich würde immer wieder brauchen, wählen Sie einen zufälligen Schlüssel aus einer zufälligen HashMap (und einige Sachen mit ihm). Die Auswahl der zufälligen HashMap ist trivial, aber wie soll ich wählen Sie eine zufällige Taste in dieser HashMap?

Geschwindigkeit wichtig ist (als ich dies tun müssen 10000 mal und die hashmaps sind groß), so dass nur wählen eine zufällige Zahl k in [0,9999] und dann tut .next() auf der iterator k-mal, das ist nicht wirklich eine option. Ähnlich, die Umwandlung der HashMap in ein array oder ArrayList auf jede zufällige Holen, das ist nicht wirklich eine option. Bitte, Lesen Sie diese, bevor Sie Antworten.

Technisch fühle ich, dass dies möglich sein sollte, da die HashMap speichert seine Schlüssel in einer Entry[] intern, und die Auswahl nach dem Zufallsprinzip aus einem array einfach ist, aber ich kann nicht herausfinden, wie Zugriff auf diese Entry[]. Also, irgendwelche Ideen auf das interne Entry[] sind mehr als willkommen. Andere Lösungen (solange Sie nicht verbrauchen die lineare Zeit in der hashmap-Größe) sind auch willkommen natürlich.

Hinweis: Heuristiken sind in Ordnung, wenn es also eine Methode, schließt die 1% der Elemente (z.B. wegen multi-gefüllte Eimer) das ist überhaupt kein problem.

Einträge angekettet werden, wenn Sie mehr als eine zur gleichen index. So, dass wäre nicht so einfach.
Wenn die Umwandlung den entrySet zu einer Liste ist'f schnell genug ist (hast du das Profil ?), dann müssen Sie eine weitere Datenstruktur.
Pseudo ist in Ordnung, wenn es 1% der Einträge, die nie abgeholt werden, ist dies keine große Sache. Nicht, dass geben zusätzliche Optionen? Also, keine sorgen, wenn ein element verkettet ist, dann wählen Sie einfach ein anderes element.

InformationsquelleAutor user1111929 | 2012-09-12

17

aus der Spitze von meinem Kopf
```
List<A> keysAsArray = new ArrayList<A>(map.keySet())
Random r = new Random()
```
dann nur
```
map.get(keysAsArray.get(r.nextInt(keysAsArray.size()))
```
- Das hat immer noch lineare Komplexität in der Größe der keySet, Nein? :/
- das hängt davon ab, ob Ihre keyset ändert sich oft. Sie können sich mit nur aktualisiert die Liste nur, wenn etwas zur map Hinzugefügt oder entfernt werden. Dann die Holen sich konstant Zeit.
- ach, jeder random pick ändert einer der hashmaps. Wenn ich hatte Zugang zu Entry[] ich könnte natürlich einfach eine einfache änderung in das array, aber es scheint, dass diese Entry[] nicht zugänglich ist (es sei denn ich kopieren und fügen Sie den gesamten source-code).
- Es ist besser in dem Sinne, dass Sie nicht brauchen, Reflexion und es wird effizient arbeiten, selbst wenn es nur sehr wenige Einträge übrig.
InformationsquelleAutor user902383
6

Benötigen Sie Zugriff auf die zugrunde liegende Tabelle.
```
//defined staticly
Field table = HashMap.class.getDeclaredField("table");
table.setAccessible(true);
Random rand = new Random();

public Entry randomEntry(HashMap map) {
    Entry[] entries = (Entry[]) table.get(map);
    int start = rand.nextInt(entries.length);
    for(int i=0;i<entries.length;i++) {
       int idx = (start + i) % entries.length;
       Entry entry = entries[idx];
       if (entry != null) return entry;
    }
    return null;
}
```
Diese noch Durchlaufen muss, die Einträge zu finden, das ist so der worst-case ist O(n), sondern das typische Verhalten ist O(1).
- HashMap.class.getDeclaredField("table");, genial, danke! Alle, die ich bin Links zu Fragen, mit jetzt ist, warum Sie nicht setzen Sie dieses in HashMap und HashSet standardmäßig. 🙂
- Die Verwendung von Generika für diese Art der Zweck ist bedenklich, wenn die Umsetzung jemals ändert, wird das Programm unterbrochen wird. Man sollte das Programm gegen die Schnittstelle, nicht die Implementierung.
- Ich denke du meinst mit Reflexionen ist sowas von faul und brüchig. Ich sehe kein problem bei der Verwendung von Generika. 😉
- Wie wäre es mit dieser Lösung stackoverflow.com/questions/12385284/... findest du es besser?
- ja, hab ein Hirn-Furz.
InformationsquelleAutor Peter Lawrey
5

Habe ich es geschafft eine Lösung zu finden, ohne performance-Verlust. Ich werde es hier posten, da kann es helfen, anderen Menschen-und möglicherweise beantworten mehrere offene Fragen zu diesem Thema (ich Suche für diese später).

Was Sie brauchen, ist eine zweite benutzerdefinierte Set-wie Datenstruktur, die zum speichern der Schlüssel-nicht eine Liste, wie einige hier vorgeschlagen. Listen-Daten-Strukturen sind zu teuer, um Elemente zu entfernen aus. Die erforderlichen Operationen sind das hinzufügen/entfernen von Elementen in konstanter Zeit (zu halten Sie up-to-date mit der HashMap) und ein Verfahren zu wählen, das zufällige element. Die folgende Klasse MySet tut genau dies
```
class MySet<A> {
     ArrayList<A> contents = new ArrayList();
     HashMap<A,Integer> indices = new HashMap<A,Integer>();
     Random R = new Random();

     //selects random element in constant time
     A randomKey() {
         return contents.get(R.nextInt(contents.size()));
     }

     //adds new element in constant time
     void add(A a) {
         indices.put(a,contents.size());
         contents.add(a);
     }

     //removes element in constant time
     void remove(A a) {
         int index = indices.get(a);
         contents.set(index,contents.get(contents.size()-1));
         contents.remove(contents.size()-1);
         indices.set(contents.get(contents.size()-1),index);
         indices.remove(a);
     }
}
```
- Die add-operation ist O(n), weil Sie mit ArrayList.
- Warum würde die add-operation O(n)? Ich bin Anhängen an das Ende der ArrayList, das ist O(1).
- Ja, aber die ArrayList ist nicht unbegrenzt in Größe ist es? Was passiert also, wenn Sie fügen Sie ein weiteres element in der schon voll ArrayList? Es deklariert ein neues, größeres array und kopiert das array, das größer ist, erfordert O(n). Aber dies geschieht rearely, also technisch gesehen, Sie können sich darauf verlassen, O(1). Streng genommen, es ist O(n).
- Und die remove-operation ist auch O(n) (diesmal sogar technisch). ArrayList sagt: "Die Größe, isEmpty, get, set, iterator und listIterator Operationen laufen in konstanter Zeit. Die add-operation läuft in amortisiert konstanter Zeit, das heißt, das hinzufügen von n Elementen benötigt O(n) Zeit. Alle anderen Vorgänge laufen in linearer Zeit (grob gesagt)."
- Und ich verstehe nicht, warum Sie mit einer anderen Karte zum speichern von integer-Indizes. Warum verwenden Sie nicht nur die indexOf Methode?
- Weil indexOf läuft in linearer Zeit, nicht Konstante Zeit. Entfernen der index k funktioniert in O(Größe k) mit der Zeit, so dass, wenn Sie entfernen Sie nur das Letzte element jedes mal, es funktioniert in O(1) Zeit. Dies ist, wie die ArrayList arbeitet.
InformationsquelleAutor user1111929
3

Klingt wie Sie sollten entweder eine untergeordnete Liste mit den Tasten oder ein reales Objekt, nicht eine Karte, die zum speichern in der Liste.
- Leider eine HashMap nicht die Möglichkeit bieten, die zum speichern der Schlüssel in einer einfachen Liste, und keine andere Struktur-Karten, beliebige Objekte an beliebigen Objekten mit einer Konstanten Zeit get().
- Daher das Wort "Leistungsschutzrecht". Es ist separate Daten-Struktur, die Sie pflegen zusammen mit der Liste der Karten. Du bist schuldig des Denkens an einem zu niedrigen Niveau.
- Das ist wahr, aber angesichts der Größe meiner HashMaps, alle zusätzlichen Struktur wird der Speicherverbrauch deutlich (wie die Objekte sind klein, aber es gibt eine Menge von Ihnen). Ich bin immer noch der Hoffnung, irgendwie Zugang zu den Entry[]. Ich kann copy-paste der gesamte Quellcode in eine neue Datei und verwenden Sie es dort, aber das ist nicht wirklich guten coding style. :/
InformationsquelleAutor duffymo
1

Ich nehme an, Sie sind mit HashMap wie müssen Sie Aussehen, bis zu einem späteren Datum?

Wenn das nicht der Fall, dann ändern Sie einfach Ihre HashMap zu einem Array/ArrayList.

Wenn dies der Fall ist, warum nicht speichern Sie Ihre Objekte in einer Map UND ein ArrayList so kann man zufällig oder durch die-Taste.

Alternativ könnten Sie verwenden ein TreeMap statt HashMap? Ich weiß nicht, was geben Sie Ihren Schlüssel aber Sie verwenden TreeMap.floorKey() in Verbindung mit einigen der wichtigsten randomizer.
- Treemap einfügen und suchen log(n) und nicht protokollieren(1)
InformationsquelleAutor TedTrippin
1

Nach einiger Zeit, kam ich zu dem Schluss, dass Sie brauchen, um ein Modell zu erstellen, das kann unterstützt werden durch eine List<Map<A, B>> und ein List<A> zu halten Ihre Schlüssel. Sie benötigen, um den Zugriff auf Ihre List<Map<A, B>> und List<A> einfach die Operationen/Methoden an den Aufrufer. Auf diese Weise haben Sie die volle Kontrolle über die Implementierung, und die eigentlichen Objekte werden sicherer aus externen Veränderungen.

Btw, deine Fragen führen mich zu,
- Warum funktioniert das in java.util.Set<V> interface nicht bieten eine get(Object o) Methode?, und
- Bimap: Ich habe versucht, schlau zu sein, aber, natürlich, seine values() Methode liefert auch Set.
Diesem Beispiel IndexedSet, kann geben Ihnen eine Idee über, wie.

[bearbeitet]

Dieser Klasse, SetUniqueList, könnte Ihnen helfen, wenn Sie sich entscheiden, erstellen Sie Ihr eigenes Modell. Es besagt ausdrücklich, dass es umhüllt den list (keine Kopien). Also, ich denke, wir können etwas tun,
```
List<A> list = new ArrayList(map.keySet());
SetUniqueList unikList = new SetUniqueList(list, map.keySet);
//Now unikList should reflect all the changes to the map keys
...
//Then you can do
unikList.get(i);
```
Hinweis: ich nicht es selber auszuprobieren. Wird das auch später machen (hetzen, zu Hause).

InformationsquelleAutor Adeel Ansari
1

Seit Java 8 gibt es eine O(log(N)) - Ansatz mit O(log(N)) zusätzliche memory: erstellen Sie eine Spliterator über map.entrySet().spliterator() machen log(map.size()) trySplit() Anrufe und wählen Sie entweder die erste oder die zweite Hälfte nach dem Zufallsprinzip. Wenn es sagen wir weniger als 10 Elemente, die Links in einem Spliterator, steckt Sie in eine Liste und machen Sie eine zufällige Holen.
- Wird diese Rendite eine (mehr oder weniger) uniformely zufällige element der hashmap? Tut trySplit() teilen Sie immer in der Hälfte oder was? Ich bin verwirrt über das Innenleben dieser neuen routine.
- Je größer die cutoff-Größe, wenn Sie ausgeben der verbleibenden Elemente einer Liste und eine zufällige Auswahl, desto gleichmäßiger wird die Wahl von zufälligen Schlüssel insgesamt. 10 Elementen ist der Ausgangspunkt für tests (Homogenität). Ich denke, dass der tatsächliche Wert kann zwischen 8 und 32 Elemente bei der Auswahl wird sehr gleichmäßig.
- Es kommt wohl auf die Qualität der Verteilung der hash-codes der Schlüssel, jedoch. Wenn die Qualität anständig ist, dies sollte nicht eine Sorge, aber wenn es gibt eine Menge von genauen hash-code-Kollisionen und alle Tasten sind konzentriert in einigen teilen der Tabelle, da einige bits 0s oder 1s in der Mehrheit oder alle hash-codes, die Einheitlichkeit der random-Taste, Wahl beeinflusst werden könnte.
InformationsquelleAutor leventov
0

Wenn du unbedingt Zugriff auf den array-Eintrag in der HashMap, die Sie verwenden können, Reflexion. Aber dann wird Ihr Programm sein, abhängig von der konkreten Implementierung der HashMap.

Wie vorgeschlagen, können Sie halten eine separate Liste der Schlüssel, die für jede Karte. Sie würde nicht halten, tief Kopien der Schlüssel, so dass der tatsächliche Speicher, der entnormierung wäre nicht so groß.

Dritte Ansatz ist die Implementierung eigener Map-Implementierung, die einem immer, dass keys in einer Liste statt einem Satz.

InformationsquelleAutor Jakub Zaverka
0

Wie etwa Verpackung HashMap in eine andere Implementierung von Map? Die andere Karte verwaltet eine Liste, und auf der put() es gilt:
```
if (inner.put(key, value) == null) listOfKeys.add(key);
```
(Ich gehe davon aus, dass null-Werte nicht zulässig, wenn Sie verwenden, containsKey, aber das ist langsamer)

InformationsquelleAutor Arkadiy

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.