HashSet jauh lebih cepat daripada TreeSet (waktu-konstan versus waktu-log untuk sebagian besar operasi seperti menambah, menghapus, dan memuat) tetapi tidak menawarkan jaminan pemesanan seperti TreeSet.
- kelas menawarkan kinerja waktu yang konstan untuk operasi dasar (menambah, menghapus, memuat dan ukuran).
- itu tidak menjamin bahwa urutan elemen akan tetap konstan seiring waktu
- kinerja iterasi tergantung pada kapasitas awal dan faktor beban HashSet.
- Cukup aman untuk menerima faktor muatan default, tetapi Anda mungkin ingin menentukan kapasitas awal yang kira-kira dua kali ukuran yang Anda harapkan akan meningkat.
- menjamin log (n) biaya waktu untuk operasi dasar (menambah, menghapus, dan memuat)
- menjamin bahwa elemen himpunan akan diurutkan (naik, alami, atau yang ditentukan oleh Anda melalui konstruktornya) (mengimplementasikan
SortedSet
)
- tidak menawarkan parameter penyetelan untuk kinerja iterasi
- menawarkan beberapa metode yang berguna untuk menangani set memerintahkan seperti
first()
, last()
, headSet()
, dan tailSet()
lain-lain
Poin-poin penting:
- Keduanya menjamin koleksi elemen yang bebas duplikat
- Biasanya lebih cepat untuk menambahkan elemen ke HashSet dan kemudian mengonversi koleksi ke TreeSet untuk traversal yang diurutkan duplikat-gratis.
- Tidak satu pun dari implementasi ini yang disinkronkan. Itu adalah jika beberapa utas mengakses satu set secara bersamaan, dan setidaknya satu utas mengubah set, itu harus disinkronkan secara eksternal.
- LinkedHashSet dalam beberapa hal menengah antara
HashSet
dan TreeSet
. Diimplementasikan sebagai tabel hash dengan daftar tertaut yang berjalan melewatinya, bagaimanapun, ia menyediakan iterasi penyisipan yang tidak sama dengan traversal yang diurutkan yang dijamin oleh TreeSet .
Jadi pilihan penggunaan sepenuhnya tergantung pada kebutuhan Anda, tetapi saya merasa bahwa bahkan jika Anda memerlukan koleksi yang dipesan maka Anda harus tetap memilih HashSet untuk membuat Set dan kemudian mengubahnya menjadi TreeSet.
- misalnya
SortedSet<String> s = new TreeSet<String>(hashSet);
Satu keuntungan yang belum disebutkan tentang a
TreeSet
adalah bahwa ia memiliki "lokalitas" yang lebih besar, yang merupakan singkatan untuk mengatakan (1) jika dua entri berdekatan dalam urutan, aTreeSet
menempatkan mereka berdekatan satu sama lain dalam struktur data, dan karenanya dalam memori; dan (2) penempatan ini memanfaatkan prinsip lokalitas, yang mengatakan bahwa data serupa sering diakses oleh aplikasi dengan frekuensi yang sama.Ini berbeda dengan a
HashSet
, yang menyebarkan entri ke seluruh memori, apa pun kunci mereka.Ketika biaya latensi membaca dari hard drive adalah ribuan kali biaya membaca dari cache atau RAM, dan ketika data benar-benar diakses dengan lokalitas, itu
TreeSet
bisa menjadi pilihan yang jauh lebih baik.sumber
TreeSet
/TreeMap
bukan lokalitas dioptimalkan. Meskipun dimungkinkan untuk menggunakan b-tree orde 4 untuk mewakili pohon merah-hitam dan dengan demikian meningkatkan kinerja lokalitas dan cache, itu bukanlah cara implementasi. Sebaliknya, setiap node menyimpan pointer ke kunci sendiri, nilainya sendiri, orang tuanya, dan node anak kiri dan kanannya, terbukti dalam kode sumber JDK 8 untuk TreeMap.Entry .HashSet
adalah O (1) untuk mengakses elemen, jadi tentu saja itu penting. Tetapi mempertahankan urutan objek di set tidak mungkin dilakukan.TreeSet
berguna jika mempertahankan pesanan (Dalam hal nilai dan bukan urutan penyisipan) penting bagi Anda. Tetapi, seperti yang telah Anda catat, Anda memperdagangkan pesanan untuk waktu yang lebih lambat untuk mengakses elemen: O (log n) untuk operasi dasar.Dari javadocs untuk
TreeSet
:sumber
1.HashSet memungkinkan objek nol.
2.TreeSet tidak akan mengizinkan objek nol. Jika Anda mencoba menambahkan nilai nol, itu akan melempar NullPointerException.
3.HashSet jauh lebih cepat daripada TreeSet.
misalnya
sumber
null
ke set Anda dengan cara baik.TreeSet<String> badassTreeSet = new TreeSet<String>(new Comparator<String>() { public int compare(String string1, String string2) { if (string1 == null) { return (string2 == null) ? 0 : -1; } else if (string2 == null) { return 1; } else { return string1.compareTo(string2); } } }); badassTreeSet.add("tree"); badassTreeSet.add("asdf"); badassTreeSet.add(null); badassTreeSet.add(null); badassTreeSet.add("set"); badassTreeSet.add("tree"); System.out.println(badassTreeSet);
Mendasarkan pada jawaban visual yang bagus di Maps oleh @shevchyk, inilah pilihan saya:
sumber
Alasan mengapa sebagian besar digunakan
HashSet
adalah bahwa operasi (rata-rata) O (1) bukan O (log n). Jika set berisi item standar, Anda tidak akan "bermain-main dengan fungsi hash" seperti yang telah dilakukan untuk Anda. Jika set berisi kelas kustom, Anda harus menerapkanhashCode
untuk menggunakanHashSet
(meskipun Java Efektif menunjukkan caranya), tetapi jika Anda menggunakanTreeSet
Anda harus membuatnyaComparable
atau menyediakan aComparator
. Ini bisa menjadi masalah jika kelas tidak memiliki urutan tertentu.Saya kadang-kadang menggunakan
TreeSet
(atau sebenarnyaTreeMap
) untuk set / peta yang sangat kecil (<10 item) meskipun saya belum memeriksa untuk melihat apakah ada keuntungan nyata dalam melakukannya. Untuk set besar perbedaannya bisa sangat besar.Sekarang jika Anda perlu diurutkan, maka
TreeSet
sudah tepat, meskipun itupun jika pembaruan sering dan kebutuhan untuk hasil yang diurutkan jarang, kadang-kadang menyalin konten ke daftar atau array dan menyortirnya bisa lebih cepat.sumber
Jika Anda tidak memasukkan cukup elemen untuk menghasilkan pengulangan yang sering (atau tabrakan, jika HashSet Anda tidak dapat mengubah ukuran), HashSet tentu saja memberi Anda manfaat dari akses waktu yang konstan. Tetapi pada set dengan banyak pertumbuhan atau penyusutan, Anda mungkin benar-benar mendapatkan kinerja yang lebih baik dengan Treesets, tergantung pada implementasinya.
Waktu diamortisasi bisa mendekati O (1) dengan pohon merah-hitam fungsional, jika ingatanku. Buku Okasaki akan memiliki penjelasan yang lebih baik daripada yang bisa saya lakukan. (Atau lihat daftar publikasinya )
sumber
Implementasi HashSet, tentu saja, jauh lebih cepat - lebih sedikit overhead karena tidak ada pemesanan. Analisis yang baik dari berbagai implementasi Set di Jawa disediakan di http://java.sun.com/docs/books/tutorial/collections/implementations/set.html .
Diskusi di sana juga menunjukkan pendekatan 'jalan tengah' yang menarik untuk pertanyaan Tree vs Hash. Java menyediakan LinkedHashSet, yang merupakan HashSet dengan daftar tertaut "berorientasi penyisipan" yang berjalan melaluinya, yaitu, elemen terakhir dalam daftar tertaut juga yang paling baru disisipkan ke dalam Hash. Ini memungkinkan Anda untuk menghindari kerusuhan hash yang tidak teratur tanpa menimbulkan peningkatan biaya TreeSet.
sumber
The TreeSet adalah salah satu dari dua koleksi diurutkan (yang lain makhluk TreeMap). Ia menggunakan struktur pohon Merah-Hitam (tetapi Anda tahu itu), dan menjamin bahwa unsur-unsurnya akan berada dalam urutan naik, menurut urutan alami. Secara opsional, Anda bisa membuat TreeSet dengan konstruktor yang memungkinkan Anda memberikan koleksi aturan Anda sendiri seperti apa urutannya (daripada mengandalkan urutan yang ditentukan oleh kelas elemen) dengan menggunakan Sebanding atau Pembanding
dan A LinkedHashSet adalah versi HashSet yang diurutkan yang memelihara Daftar yang ditautkan ganda di semua elemen. Gunakan kelas ini alih-alih HashSet saat Anda peduli dengan urutan iterasi. Saat Anda beralih melalui HashSet, pesanan tidak dapat diprediksi, sedangkan LinkedHashSet memungkinkan Anda beralih melalui elemen-elemen dalam urutan di mana mereka dimasukkan
sumber
Banyak jawaban telah diberikan, berdasarkan pertimbangan teknis, terutama seputar kinerja. Menurut saya, pilihan antara
TreeSet
danHashSet
hal - hal.Tapi saya lebih suka mengatakan pilihan harus didorong oleh pertimbangan konseptual terlebih dahulu.
Jika, untuk objek yang perlu Anda manipulasi, pemesanan alami tidak masuk akal, maka jangan gunakan
TreeSet
.Ini adalah set yang diurutkan, karena mengimplementasikan
SortedSet
. Jadi itu berarti Anda perlu mengganti fungsicompareTo
, yang harus konsisten dengan fungsi pengembalian apaequals
. Sebagai contoh jika Anda memiliki satu set objek dari kelas yang disebut Siswa, maka saya tidak berpikir aTreeSet
akan masuk akal, karena tidak ada pemesanan alami antara siswa. Anda dapat memesannya dengan nilai rata-rata, oke, tapi ini bukan "pemesanan alami". FungsicompareTo
akan mengembalikan 0 tidak hanya ketika dua objek mewakili siswa yang sama, tetapi juga ketika dua siswa yang berbeda memiliki nilai yang sama. Untuk kasus kedua,equals
akan menghasilkan false (kecuali jika Anda memutuskan untuk membuat yang kedua kembali benar ketika dua siswa berbeda memiliki nilai yang sama, yang akan membuatequals
fungsi memiliki makna yang menyesatkan, tidak untuk mengatakan makna yang salah.)Harap perhatikan konsistensi antara
equals
dancompareTo
bersifat opsional, tetapi sangat disarankan. Kalau tidak, kontrak antarmukaSet
terputus, membuat kode Anda menyesatkan orang lain, sehingga juga mungkin mengarah pada perilaku tak terduga.Tautan ini mungkin merupakan sumber informasi yang baik mengenai pertanyaan ini.
sumber
Mengapa memiliki apel ketika Anda bisa memiliki jeruk?
Serius cowok dan cewek - jika koleksi Anda besar, baca dan tulis hingga beberapa kali, dan Anda membayar untuk siklus CPU, maka pilihan koleksi ini HANYA relevan jika Anda PERLU untuk berkinerja lebih baik. Namun, dalam kebanyakan kasus, ini tidak terlalu penting - beberapa milidetik di sana-sini tidak diperhatikan dalam istilah manusia. Jika itu sangat penting, mengapa Anda tidak menulis kode di assembler atau C? [isyarat diskusi lain]. Jadi intinya adalah jika Anda senang menggunakan koleksi apa pun yang Anda pilih, dan itu memecahkan masalah Anda [bahkan jika itu tidak secara khusus jenis koleksi terbaik untuk tugas itu] pingsan. Perangkat lunak ini mudah ditempa. Optimalkan kode Anda jika perlu. Paman Bob mengatakan Pengoptimalan Dini adalah akar dari semua kejahatan. Paman Bob mengatakan demikian
sumber
Edit Pesan ( penulisan ulang lengkap ) Ketika pesanan tidak penting, saat itulah. Keduanya harus memberikan Log (n) - akan berguna untuk melihat apakah keduanya lebih dari lima persen lebih cepat daripada yang lain. HashSet dapat memberikan O (1) pengujian dalam satu lingkaran harus mengungkapkan apakah itu.
sumber
sumber