Czy istnieje struktura danych dla tego typu listy / mapy?

22

Być może istnieje nazwa tego, czego chcę, ale nie jestem tego świadomy. Potrzebuję czegoś podobnego do LinkedHashMapjęzyka Java, ale zwraca wartość „poprzednią”, jeśli pod określonym kluczem nie ma żadnej wartości.

To znaczy, mam listę obiektów przechowywanych przez klucz liczby całkowitej (która w moim przypadku jest w jednostkach czasu):

; key->value
10->A
15->B
20->C

Gdybym więc zapytał o wartość dla klucza 0–9, zwróciłbym null. Specjalną częścią jest to, że jeśli zapytałem o coś 10 <= i <= 14, zwróci A. Lub, dla i> = 20, zwróci C.

Czy istnieje do tego struktura danych?

java data-structures Nacięcie
źródło
Nie wiem, czy istnieje, ale prawdopodobnie mógłbyś rozszerzyć istniejącą, aby to zrobić. Czy spełni twoje cele w zakresie wydajności, czy nie bez przepisywania, nie wiem ...
Rig
1
+1 za świetne pytanie. Większość osób z trzema cyframi z pytaniem zadaje pytanie typu „proszę odrabiać lekcje”. Nie w tym przypadku.
Tulains Córdova

Odpowiedzi:

33

Szukasz NavigableMap . Jest to podtyp SortedMap, który ma również pewne funkcje oprócz charakteru sortowanej mapy. Zauważ, że mapa nawigacyjna „ma zastąpić interfejs SortedMap”. ( Udoskonalenia środowiska Java SE 6 Collections ). Wszystko, co obecnie implementuje, SortedMapimplementuje NavigableMapi to prawdopodobnie pozostanie prawdą.

W szczególności metoda, floorKey(K key)która „zwraca największy klucz mniejszy lub równy podanemu kluczowi, lub null, jeśli takiego klucza nie ma.

To tylko jedna z wielu metod, które pozwalają uzyskać określone klucze lub mapy.

  • sufit / podłoga (wejście wyższe / niższe niż parametr)
  • dostęp do kluczy lub mapy w kolejności malejącej
  • głowa / ogon (wpisy mniejsze / większe niż dany klucz)
  • wyższy / niższy (następny klawisz, który jest wyższy lub niższy niż parametr)
  • submap (biorąc pod uwagę dwa klucze, zwraca mapę między dwoma kluczami)

Java ma dwie implementacje NavigableMap - TreeMap i ConcurrentSkipListMap .

Jeśli spojrzysz na pomysł / implementację listy pominięć , zobaczysz, dlaczego tak dobrze działałaby z taką strukturą i jej zapytaniami.


źródło
Ponad 1 świetna odpowiedź. Nigdy nie myślałem, że taka konkretna mapa istnieje w API Java.
Tulains Córdova
@ user61852 Moim ulubionym typem danych jest lista przeskakiwania i zaczęłam się nią bawić. Kiedy zobaczyłem, że został zaimplementowany w wersji 1.6, przyjrzałem się wszystkim, co zapewniało, i zauważyłem interfejsy, które posiadał, a tym samym moją znajomość.
Takie rzeczy przekonują mnie, że Java jest jednym z najlepiej zaprojektowanych języków, jakie można znaleźć.
Tulains Córdova
1
Zauważ, że chociaż wydaje się to dotyczyć problemu OP, nie działa tak, jak LinkedHashMapon wspomina. Ani TreeMapnie ConcurrentSkipListMapsą uporządkowane według czasu wstawienia LinkedHashMap, ale raczej są uporządkowane według naturalnego Comparatorlub klucza Naturalnego Porządkowania, jeśli są realizowane Comparable.
MikeFHay
1
Bardzo dobra uwaga. To, czego szukałem na podłodze, to komparator, który mogę łatwo dodać. A w moim przypadku ładniej jest zaimplementować komparator, zamiast wymyślać koło. Dzięki.
Nick
1

To, czego szukasz, to tablica symboli, która obsługuje uporządkowane operacje. A w twoim przypadku jest to operacja na podłodze.

Implementacja skrótu tablicy symboli jest najszybsza, ale nie oferuje tych uporządkowanych operacji.

Ale implementacja drzewa tabel symboli ma. Przykładem tego w Javie jest klasa TreeMap

Wszechmocny wielbłąd Moha
źródło