Frage Besorgen Sie sich den Schlüssel einer Hashmappe mit einem Zahlenbereich als Wert


Ich habe ein HashMap<Integer, Float> mit Einträgen:

 1 -> 0.127
 2 -> 0.167
 3 -> 0.207
 4 -> 0.247
 5 -> 0.237
 6 -> 0.327
 7 -> 0.367
 8 -> 0.407
 9 -> 0.447
10 -> 0.487
11 -> 0.527
12 -> 0.567
13 -> 0.607
14 -> 0.647
15 -> 0.652

Angenommen, ich möchte den Schlüssel zum Float 0.465 (was kein existierender Wert ist). 0.465 ist zwischen 0.447 und 0.487Also möchte ich den Schlüssel bekommen 10.

Der erste Gedanke, der mir in den Sinn kam, war dies mit 15 if / else if-Anweisungen oder mit der switch-Anweisung. Aber meiner Meinung nach wäre das nicht sehr elegant und praktisch.

Gibt es einen anderen Weg, dies zu tun?


5
2017-07-16 22:51


Ursprung


Antworten:


Eine Map ist nicht die geeignete Datenstruktur. Benutze einen TreeSet stattdessen:

TreeSet<Float> numbers = new TreeSet<>();
// populate the set with your numbers, in any order, then

int index = numbers.headSet(n).size() + 1;

Dies wird sehr gut funktionieren: TreeSet findet den Einfügepunkt in O (log n) -Zeit (wie eine binäre Suche) und die zurückgegebene Liste ist nur a Aussicht (Eine neue Liste wird nicht erstellt.) Daher ist die gesamte Operation leichtgewichtig.

Beachten Sie auch, dass die Elemente nicht in einer bestimmten Reihenfolge hinzugefügt werden müssen - TreeSet intern verwaltet ihre Reihenfolge, so dass die Suche schnell ist.


Hier ist ein Testcode:

TreeSet<Float> numbers = new TreeSet<>(Arrays.asList(
    0.607F, 0.647F, 0.127F, 0.167F, 0.207F, 0.247F, 0.237F, 0.327F,
    0.367F, 0.407F, 0.447F, 0.487F, 0.527F, 0.567F, 0.652F));

Ausgabe:

10

4
2017-07-16 23:06



Angenommen data Ist Ihre ursprüngliche Karte und die Werte sind einzigartig, könnten Sie tun:

java.util.NavigableMap<Double, Integer> reverseMap = new java.util.TreeMap<>();
for(java.util.Map.Entry<Double, Integer> entry : data.entrySet()) {
    reverseMap.put(entry.getValue(), entry.getKey());
}
System.out.println(reverseMap.ceilingEntry(0.465).getValue());

1
2017-07-16 22:58



Wenn Werte immer sortiert sind, verwenden Sie einfach ein gemeinsames Array:

double[] values = {0.127, ..., 0.652};

Und dann, ruf an Arrays.binarySearch() Methode, die den Index des Werts zurückgibt, der unmittelbar größer als der angegebene Wert ist.

Bitte beachten Sie, dass dieser Ansatz doppelte Werte unterstützt und der zurückgegebene Index ist 0-based.


1
2017-07-16 23:09