klucz HashMap uzyskać z zakresu liczb jako wartości

Question

mam HashMap<Integer, Float> z wpisami:

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 

Niech załóżmy, że chcę klucz do Float 0,465 (co nie jest istniejąca wartość). 0.465 jest między 0.447 i 0.487, więc chciałbym uzyskać klucz 10.

Pierwsza myśl, która przyszła mi do głowy, była możliwa dzięki 15 instrukcjom if/else if lub instrukcjom switch. Moim zdaniem nie byłoby to jednak zbyt eleganckie i praktyczne.

Czy jest jakiś inny sposób na zrobienie tego?

Answer 1

Mapa nie jest odpowiednia struktura danych. Użyj TreeSet Zamiast:

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

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

Będzie to wykonać bardzo dobrze: TreeSet znajduje punkt wstawiania w O (log n) czas (jak poszukiwania binarnego), a lista jest zwracany tylko widok (nową listę nie jest tworzony), więc cała operacja jest lekka.

Należy również pamiętać, że elementy nie muszą być dodawane w dowolnej kolejności - TreeSet wewnętrznie utrzymuje ich kolejność, dzięki czemu wyszukiwanie jest szybkie.

---

Oto niektóre kodu testu:

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)); 

wyjściowa:

10 

Answer 2

Zakładając data jest początkowy mapa i wartości są unikalne, można zrobić:

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()); 

Answer 3

Jeżeli wartości są zawsze klasyfikowane, wystarczy użyć wspólnej tablicy:

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

a potem, zadzwoń na metę Arrays.binarySearch() d, który zwraca indeks wartości, która jest natychmiast większa od podanej wartości.

Należy pamiętać, że to podejście obsługuje duplikaty wartości, a zwracany indeks to 0-based.