Koleksi dengan akses berdasarkan ordinalitas dan pencarian kunci

Apa yang saya cari adalah koleksi tidak berurutan default yang didukung oleh array atau daftar array yang memungkinkan pencarian berdasarkan kunci. Atau peta asosiatif yang dapat dilalui berdasarkan waktu penyisipan.

Kasusnya adalah sebagai berikut, saya memiliki adaptor yang menelusuri koleksi melalui posisi, dan penyisipannya seperti daftar, tetapi pada saat yang sama saya ingin mengubah elemen individual dengan menemukannya berdasarkan kunci alih-alih mengulangi seluruh daftar.

Yang tidak saya inginkan adalah mengimplementasikan kembali seluruh Koleksi dari awal, atau mencegat panggilan untuk yang lain, karena itu pasti akan terjadi kesalahan.


android java collections
person MLProgrammer-CiM    schedule 06.02.2015    source sumber

Jawaban (4)


arrow_upward
3
arrow_downward

LinkedHashMap adalah pilihan terbaik Anda.

Ia bekerja seperti HashMap yang memiliki daftar tertaut ganda yang berjalan melalui item Map.Entry-nya. Anda dapat menggunakan daftar untuk iterasi dan menjadi HashMap itu akan memberi Anda pencarian O(1).

Anda dapat memilih perintah penyisipan atau perintah akses.

person aa333    schedule 06.02.2015
comment
Bagaimana saya bisa mendapatkan entri di posisi 5 tanpa mengulangi tombol? - person MLProgrammer-CiM; 06.02.2015
comment
Saya mungkin perlu memformat ulang pertanyaannya, saya menggunakan ArrayMap yang memberi saya indexOfKey dan keyAt tetapi tidak mendukung perintah penyisipan. - person MLProgrammer-CiM; 06.02.2015
comment
Jadi Anda ingin Akses Acak secara ordinal dan O(1) mencari beberapa kunci non-ordinal yang ditentukan? - person robert_difalco; 06.02.2015
comment
Saya tahu banyak yang ingin ditanyakan, itu sebabnya saya sendiri belum menemukan apa pun di dokumen. - person MLProgrammer-CiM; 06.02.2015
comment
Ada implementasi ArrayMap yang mendukung pengurutan, tetapi digabungkan dengan kelas lain libgdx.badlogicgames.com/nightlies/docs/api/com/badlogic/gdx/ - person MLProgrammer-CiM; 06.02.2015
comment
Panggilan get ArrayMap adalah O(n), FWIW. - person Louis Wasserman; 06.02.2015
comment
Saya tidak bisa memikirkan cara lain untuk mengizinkan akses yang diindeks kecuali dengan memperluas LinkedHashMap agar memiliki Peta pendukung dengan indeks sebagai kunci. Tidak tahu apakah DS seperti itu ada di beberapa perpustakaan. Namun saya akan mencoba mencari atau menyiapkan implementasinya. - person aa333; 06.02.2015
comment
@ aa333 itulah yang saya cari, hanya saja saya tidak menerapkannya sendiri karena saya pernah mengalami hal itu sebelumnya. Lihat yang saya miliki di atas oleh LibGDX. Mereka juga telah memesan peta. - person MLProgrammer-CiM; 06.02.2015
comment
Saya menautkan di bawah ImmutableMap, yang mendukung semua operasi yang Anda sebutkan tetapi tidak mendukung penambahan atau penghapusan entri. - person Louis Wasserman; 06.02.2015
comment
Sayangnya, ini adalah daftar yang bisa berubah. - person MLProgrammer-CiM; 06.02.2015

arrow_upward
1
arrow_downward

LinkedHashMap akan memberi Anda mendekati O(1) dengan perintah penyisipan

person jmj    schedule 06.02.2015

arrow_upward
0
arrow_downward

Jika Anda memerlukan pencarian terindeks O(1) serta pencarian O(1) berdasarkan kunci, Anda dapat melakukannya jika Anda tidak perlu memasukkan entri baru ke dalam peta, hanya membuat peta satu kali (walaupun mungkin memodifikasi entri di peta), dengan ImmutableMapGuava a>, yang juga mempertahankan urutan penyisipan. Seperti Map biasa, Anda dapat melakukan pencarian berdasarkan kunci, dan Anda juga dapat melakukan map.values().asList().get(i), yang mengeluarkan elemen dalam waktu yang konstan. Saya tidak percaya ada sesuatu yang ada di dalam JDK yang dapat melakukan keduanya.

person Louis Wasserman    schedule 06.02.2015

arrow_upward
0
arrow_downward

Berdasarkan komentar @ aa333, saya menyiapkan implementasi saya sendiri, ini mungkin tidak lengkap jadi saran diterima.

https://Gist.github.com/anonymous/7a93535a3cfb63623a54

Ini melewati kasus uji Q&D ini:

public static void main(String[] args) {
    Map<String, String> preMap = new HashMap<String, String>();
    preMap.put("subZero", "-1");
    preMap.put("zero", "0");
    IterableLinkedMap<String, String> map = new IterableLinkedMap<String, String>();
    map.putAll(preMap);
    map.put("one", "1");
    map.put("two", "2");
    map.put("three", "3");
    map.put("four", "4");
    map.put("five", "5");
    map.put("six", "6");
    map.remove("three");
    map.put("eight", "8");
    map.put("seven", "7");
    map.remove("one");
    map.put("three", "33");
    map.put("five", "actually five");
    for (int i = 0; i < map.size(); i++){
        System.out.println(map.getPosition(i));
    }
    map.clear();
    System.out.println(map.getPosition(0));
}

Hasil:

0
-1
2
4
actually five
6
8
7
33
null
person MLProgrammer-CiM    schedule 07.02.2015
comment
Itu adalah titik awal tetapi lebih banyak hal yang diperlukan untuk membuatnya berfungsi di O(1) untuk penyisipan dan pencarian posisi dan kunci. Biaya penghapusannya adalah O(n), yang merupakan harga kecil yang harus dibayar IMO. - person MLProgrammer-CiM; 09.02.2015