Adakah implementasi dari Ordered Set di Java?

Jika ada yang familiar dengan Objective-C, ada koleksi yang disebut NSOrderedSetsebagai Set dan itemnya bisa diakses sebagai Array .

Apakah ada yang seperti ini di Jawa?

Saya pernah mendengar ada koleksi yang disebut LinkedHashMap, tetapi saya belum menemukan yang seperti itu untuk satu set.

Lihatlah kelas LinkedHashSet

Dari dokumen Java :

Tabel hash dan implementasi daftar tertaut dari antarmuka Set, dengan urutan iterasi yang dapat diprediksi . Implementasi ini berbeda dari HashSet karena ia mempertahankan daftar tertaut ganda yang berjalan melalui semua entri. Daftar tertaut ini mendefinisikan pengurutan iterasi, yaitu urutan elemen yang dimasukkan ke dalam set (urutan-penyisipan) . Perhatikan bahwa urutan penyisipan tidak terpengaruh jika sebuah elemen dimasukkan kembali ke dalam set . (Sebuah elemen e dimasukkan kembali ke dalam himpunan s jika s.add (e) dipanggil ketika s.contains (e) akan mengembalikan true segera sebelum pemanggilan.).

Setiap Set memiliki iterator (). Iterator HashSet normal cukup acak, TreeSet melakukannya dengan urutan, iterator LinkedHashSet melakukan iterasi dengan urutan sisipan.

Namun, Anda tidak dapat mengganti elemen di LinkedHashSet. Anda dapat menghapus satu dan menambahkan yang lain, tetapi elemen baru tidak akan menggantikan aslinya. Di LinkedHashMap, Anda dapat mengganti nilai untuk kunci yang sudah ada, lalu nilainya akan tetap berada dalam urutan aslinya.

Selain itu, Anda tidak dapat memasukkan pada posisi tertentu.

Mungkin sebaiknya Anda menggunakan ArrayList dengan pemeriksaan eksplisit untuk menghindari penyisipan duplikat.

Lihat dokumen API standar Java . Tepat di sebelah LinkedHashMap, ada file LinkedHashSet. Tapi perhatikan bahwa urutannya adalah urutan penyisipan, bukan urutan alami elemen. Dan Anda hanya dapat melakukan iterasi dalam urutan itu, tidak melakukan akses acak (kecuali dengan menghitung langkah iterasi).

Ada juga antarmuka yang SortedSetdiimplementasikan oleh TreeSetdan ConcurrentSkipListSet. Keduanya memungkinkan iterasi dalam urutan alami elemennya atau a Comparator, tetapi bukan akses acak atau urutan penyisipan.

Untuk struktur data yang memiliki akses efisien menurut indeks dan dapat mengimplementasikan kriteria yang ditetapkan secara efisien, Anda memerlukan daftar lewati , tetapi tidak ada implementasi dengan fungsionalitas itu di Java Standard API, meskipun saya yakin mudah untuk menemukannya di internet.

TreeSet sudah dipesan.

http://docs.oracle.com/javase/6/docs/api/java/util/TreeSet.html

Coba gunakan java.util.TreeSetalat itu SortedSet.

Mengutip dok:

"Elemen diurutkan menggunakan urutan aslinya, atau oleh Pembanding yang disediakan pada waktu pembuatan yang ditetapkan, bergantung pada konstruktor mana yang digunakan"

Perhatikan bahwa tambah, hapus, dan isi memiliki log biaya waktu (n).

Jika Anda ingin mengakses konten kumpulan sebagai Array, Anda dapat mengonversinya dengan melakukan:

YourType[] array = someSet.toArray(new YourType[yourSet.size()]); 

Array ini akan diurutkan dengan kriteria yang sama dengan TreeSet (natural atau dengan pembanding), dan dalam banyak kasus ini akan memiliki keuntungan daripada melakukan Arrays.sort ()

treeet adalah himpunan terurut, tetapi Anda tidak dapat mengakses melalui indeks item, cukup lakukan iterasi atau lanjutkan ke awal / akhir.

Jika kita berbicara tentang implementasi daftar lewati yang murah, saya bertanya-tanya dalam istilah O besar, berapa biaya operasi ini:

YourType [] array = someSet.toArray (YourType baru [yourSet.size ()]);

Maksud saya itu selalu macet ke dalam seluruh pembuatan array, jadi itu adalah O (n):

java.util.Arrays#copyOf

IndexedTreeSet dari project indexed-tree-map menyediakan fungsionalitas ini (set yang dipesan / diurutkan dengan akses seperti daftar berdasarkan indeks).

Anda mungkin juga mendapatkan beberapa utilitas dari Peta Dua Arah seperti BiMapdari Google Guava

Dengan a BiMap, Anda dapat memetakan Integer secara efisien (untuk akses indeks acak) ke tipe objek lainnya. BiMaps adalah satu-ke-satu, jadi setiap bilangan bulat yang diberikan memiliki, paling banyak, satu elemen yang terkait dengannya, dan setiap elemen memiliki satu bilangan bulat terkait. Ini dengan cerdik didukung oleh dua HashTablecontoh, sehingga menggunakan hampir dua kali lipat memori, tetapi jauh lebih efisien daripada kebiasaan Listsejauh pemrosesan karena contains()(yang dipanggil saat item ditambahkan untuk memeriksa apakah sudah ada) adalah waktu konstan dan operasi paralel-friendly seperti HashSet's, sedangkan Listimplementasinya jauh lebih lambat.

Saya punya masalah serupa. Saya tidak terlalu membutuhkan set yang dipesan tetapi lebih banyak daftar dengan cepat indexOf/ contains. Karena saya tidak menemukan apa pun di luar sana, saya menerapkannya sendiri. Inilah kodenya, ini mengimplementasikan keduanya Setdan List, meskipun tidak semua operasi daftar massal secepat ArrayListversinya.

disclaimer: tidak diuji

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Set;
import java.util.Collection;
import java.util.Comparator;
import java.util.function.Predicate;
import java.util.function.UnaryOperator;
import static java.util.Objects.requireNonNull;

/**
 * An ArrayList that keeps an index of its content so that contains()/indexOf() are fast. Duplicate entries are
 * ignored as most other java Set's do.
 */
public class IndexedArraySet<E> extends ArrayList<E> implements Set<E> {

    public IndexedArraySet() { super(); }

    public IndexedArraySet(Iterable<E> c) {
        super();
        addAll(c);
    }

    private HashMap<E, Integer> indexMap = new HashMap<>();

    private void reindex() {
        indexMap.clear();
        int idx = 0;
        for (E item: this) {
            addToIndex(item, idx++);
        }
    }

    private E addToIndex(E e, int idx) {
        indexMap.putIfAbsent(requireNonNull(e), idx);
        return e;
    }

    @Override
    public boolean add(E e) {
        if(indexMap.putIfAbsent(requireNonNull(e), size()) != null) return false;
        super.add(e);
        return true;
    }

    @Override
    public boolean addAll(Collection<? extends E> c) {
        return addAll((Iterable<? extends E>) c);
    }
    public boolean addAll(Iterable<? extends E> c) {
        boolean rv = false;
        for (E item: c) {
            rv |= add(item);
        }
        return rv;
    }

    @Override
    public boolean contains(Object e) {
        return indexMap.containsKey(e);
    }

    @Override

    public int indexOf(Object e) {
        if (e == null) return -1;
        Integer i = indexMap.get(e);
        return (i == null) ? -1 : i;
    }

    @Override
    public int lastIndexOf(Object e) {
        return indexOf(e);
    }

    @Override @SuppressWarnings("unchecked")
    public Object clone() {
        IndexedArraySet clone = (IndexedArraySet) super.clone();
        clone.indexMap = (HashMap) indexMap.clone();
        return clone;
    }

    @Override
    public void add(int idx, E e) {
        if(indexMap.putIfAbsent(requireNonNull(e), -1) != null) return;
        super.add(idx, e);
        reindex();
    }

    @Override
    public boolean remove(Object e) {
        boolean rv;
        try { rv = super.remove(e); }
        finally { reindex(); }
        return rv;
    }

    @Override
    public void clear() {
        super.clear();
        indexMap.clear();
    }

    @Override
    public boolean addAll(int idx, Collection<? extends E> c) {
        boolean rv;
        try {
            for(E item : c) {
                // check uniqueness
                addToIndex(item, -1);
            }
            rv = super.addAll(idx, c);
        } finally {
            reindex();
        }
        return rv;
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        boolean rv;
        try { rv = super.removeAll(c); }
        finally { reindex(); }
        return rv;
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        boolean rv;
        try { rv = super.retainAll(c); }
        finally { reindex(); }
        return rv;
    }

    @Override
    public boolean removeIf(Predicate<? super E> filter) {
        boolean rv;
        try { rv = super.removeIf(filter); }
        finally { reindex(); }
        return rv;
    }

    @Override
    public void replaceAll(final UnaryOperator<E> operator) {
        indexMap.clear();
        try {
            int duplicates = 0;
            for (int i = 0; i < size(); i++) {
                E newval = requireNonNull(operator.apply(this.get(i)));
                if(indexMap.putIfAbsent(newval, i-duplicates) == null) {
                    super.set(i-duplicates, newval);
                } else {
                    duplicates++;
                }
            }
            removeRange(size()-duplicates, size());
        } catch (Exception ex) {
            // If there's an exception the indexMap will be inconsistent
            reindex();
            throw ex;
        }

    }

    @Override
    public void sort(Comparator<? super E> c) {
        try { super.sort(c); }
        finally { reindex(); }
    }
}