Apakah ada struktur data untuk jenis daftar / peta ini?

22

Mungkin ada nama untuk apa yang saya inginkan, tetapi saya tidak menyadarinya. Saya perlu sesuatu yang mirip dengan LinkedHashMapdi Jawa, tetapi di mana ia mengembalikan nilai 'sebelumnya' jika tidak ada nilai pada kunci yang ditentukan.

Yaitu, saya memiliki daftar objek yang disimpan oleh kunci integer (yang dalam satuan waktu dalam kasus saya):

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

Jadi, jika saya meminta nilai untuk kunci 0-9, itu akan kembali null. Bagian khusus adalah jika saya menanyakan sesuatu 10 <= i <= 14 itu akan mengembalikan A. Atau, untuk i> = 20, itu akan mengembalikan C.

Apakah ada struktur data untuk ini?

java data-structures Nick
sumber
Saya tidak tahu apakah ada yang diterapkan tetapi Anda mungkin bisa memperpanjang yang sudah ada untuk melakukan ini. Entah itu akan memenuhi sasaran kinerja Anda atau tidak tanpa menulis ulang, saya tidak tahu ...
Rig
1
+1 untuk pertanyaan hebat. Kebanyakan orang dengan tiga perwakilan rendah digit menanyakan jenis pertanyaan "tolong kerjakan pekerjaan rumah saya". Tidak demikian di sini.
Tulains Córdova

Jawaban:

33

Anda mencari NavigableMap . Ini adalah subtipe dari SortedMap yang juga memiliki beberapa fungsi yang tersedia di samping sifat peta yang sedang diurutkan. Perhatikan bahwa peta Navigable "dimaksudkan untuk menggantikan antarmuka SortedMap." ( Java SE 6 Collections Framework Enhancements ). Segala sesuatu yang saat ini mengimplementasikan SortedMapmengimplementasikan NavigableMapdan ini kemungkinan akan tetap benar.

Secara khusus, metode floorKey(K key)yang "mengembalikan kunci terbesar kurang dari atau sama dengan kunci yang diberikan, atau nol jika tidak ada kunci seperti itu.

Ini hanyalah salah satu dari banyak metode yang memungkinkan Anda untuk mendapatkan kunci atau submaps spesifik dari peta.

  • plafon / lantai (entri yang lebih tinggi / lebih rendah dari parameter)
  • akses kunci atau peta dalam urutan menurun
  • head / tail (entri kurang / lebih besar dari kunci yang diberikan)
  • lebih tinggi / lebih rendah (kunci berikutnya yang lebih tinggi atau lebih rendah dari parameter)
  • submap (diberi dua tombol, kembalikan peta yang ada di antara dua tombol)

Java memiliki dua implementasi NavigableMap - TreeMap dan ConcurrentSkipListMap .

Jika Anda melihat ide / implementasi daftar lompatan Anda akan melihat mengapa itu akan bekerja dengan sangat baik dengan struktur dan kueri tersebut.


sumber
1+ jawaban yang bagus. Tidak pernah terpikir suatu Peta spesifik seperti itu ada di Java API.
Tulains Córdova
@ user61852 datatype favorit saya adalah daftar lewati dan saya menyodoknya. Ketika saya melihatnya diimplementasikan di 1.6 saya melihat ke dalam apa yang disediakan dan memperhatikan antarmuka yang dimilikinya dan dengan demikian saya terbiasa dengannya.
Itulah hal-hal yang meyakinkan saya bahwa Java adalah salah satu bahasa dengan desain terbaik yang dapat Anda temukan.
Tulains Córdova
1
Perhatikan bahwa sementara ini muncul untuk mengatasi masalah OP, itu tidak bertindak seperti LinkedHashMapyang ia sebutkan. Baik TreeMaptidak ConcurrentSkipListMapdiperintahkan oleh waktu penyisipan suka LinkedHashMap, melainkan mereka diperintahkan oleh ComparatorPemesanan Alami atau kunci jika mereka menerapkan Comparable.
MikeFHay
1
Poin yang sangat bagus. Operasi lantai adalah apa yang saya cari, pembanding yang dapat saya tambahkan dengan mudah. Dan dalam kasus saya ini bekerja jauh lebih baik untuk mengimplementasikan pembanding daripada menciptakan kembali roda. Terima kasih.
Nick
1

Apa yang Anda cari adalah tabel simbol yang mendukung operasi yang dipesan. Dan dalam kasus Anda itu adalah operasi lantai.

Implementasi hash dari tabel simbol adalah yang tercepat, tetapi tidak menawarkan operasi yang dipesan tersebut.

Tetapi implementasi pohon dari tabel simbol tidak. Contoh dari itu di Jawa adalah kelas TreeMap

Moha unta yang mahakuasa
sumber