Hashset vs Treeset

496

Saya selalu menyukai pohon, menyenangkan O(n*log(n))dan kerapiannya. Namun, setiap insinyur perangkat lunak yang pernah saya kenal telah bertanya kepada saya dengan jelas mengapa saya akan menggunakan TreeSet. Dari latar belakang CS, saya tidak berpikir itu penting semua yang Anda gunakan, dan saya tidak peduli untuk dipusingkan dengan fungsi hash dan ember (dalam kasus Java).

Dalam kasus apa saya harus menggunakan HashSetlebih dari satu TreeSet?

heymatthew
sumber

Jawaban:

860

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.

HashSet

  • 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.

TreeSet

  • 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 HashSetdan 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);
sactiw
sumber
38
Hanya saya yang menemukan penegasan "HashSet jauh lebih cepat daripada TreeSet (waktu-konstan versus waktu-log ...)" jelas-jelas salah? Pertama bahwa ini tentang kompleksitas waktu, bukan waktu absolut, dan O (1) dapat dalam banyak kasus lebih lambat daripada O (f (N)). Kedua O (logN) adalah "hampir" O (1). Saya tidak akan terkejut jika dalam banyak kasus, TreeSet mengungguli HashSet.
lvella
22
Saya hanya ingin komentar kedua Ivella. kompleksitas waktu BUKAN sama dengan waktu berjalan, dan O (1) tidak selalu lebih baik daripada O (2 ^ n). Contoh buruk menggambarkan poin: pertimbangkan set hash menggunakan algoritma hash yang mengambil 1 triliun instruksi mesin untuk mengeksekusi (O (1)) vs implementasi bubble sort (O (N ^ 2) rata-rata / terburuk) untuk 10 elemen . Bubble sort akan menang setiap saat. Intinya adalah kelas algoritma mengajar semua orang untuk berpikir tentang perkiraan menggunakan kompleksitas waktu tetapi di dunia nyata faktor konstan MASUK sering.
Peter Oehlert
17
Mungkin ini hanya saya, tetapi bukankah saran untuk pertama-tama menambahkan segala sesuatu ke hashset, dan kemudian menyamarkannya ke sebuah treeet yang mengerikan? 1) Penyisipan dalam hashset hanya cepat jika Anda mengetahui ukuran dataset Anda di muka, jika tidak Anda membayar O (n) re-hashing, mungkin beberapa kali. dan 2) Anda tetap membayar penyisipan TreeSet ketika mengonversi set tersebut. (dengan sepenuh hati, karena iterasi melalui hashset tidak terlalu efisien)
TinkerTank
5
Saran ini didasarkan pada fakta bahwa untuk suatu set, Anda harus memeriksa untuk melihat apakah suatu item adalah duplikat sebelum menambahkannya; karena itu Anda akan menghemat waktu untuk menghilangkan duplikat jika Anda menggunakan hashset di atas susunan pohon. Namun, mengingat harga yang harus dibayar untuk membuat set kedua untuk non-duplikat, persentase duplikat harus benar-benar hebat untuk mengatasi harga ini dan menjadikannya penghemat waktu. Dan tentu saja, ini untuk set menengah dan besar karena untuk set kecil, susunan pohon mungkin lebih cepat daripada hashset.
SylvainL
5
@PeterOehlert: tolong berikan patokan untuk itu. Saya mengerti maksud Anda, tetapi perbedaan antara kedua set hampir tidak masalah dengan ukuran koleksi kecil. Dan begitu set tumbuh ke titik, di mana implementasi penting, log (n) menjadi masalah. Secara umum adalah fungsi hash (bahkan yang kompleks) besarnya urutan lebih cepat dari beberapa cache misses (yang Anda miliki di pohon besar untuk hampir setiap tingkat akses) untuk menemukan / mengakses / menambah / memodifikasi daun. Setidaknya itulah pengalaman saya dengan dua perangkat ini di Jawa.
Bouncner
38

Satu keuntungan yang belum disebutkan tentang a TreeSetadalah bahwa ia memiliki "lokalitas" yang lebih besar, yang merupakan singkatan untuk mengatakan (1) jika dua entri berdekatan dalam urutan, a TreeSetmenempatkan 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 TreeSetbisa menjadi pilihan yang jauh lebih baik.

Carl Andersen
sumber
3
Bisakah Anda menunjukkan bahwa jika dua entri berada di dekatnya dalam urutan, TreeSet menempatkan mereka berdekatan satu sama lain dalam struktur data, dan karenanya dalam memori ?
David Soroko
6
Cukup tidak relevan untuk Java. Elemen set adalah Obyek dan menunjuk ke tempat lain, jadi Anda tidak menyimpan banyak hal.
Andrew Gallasch
Selain komentar lain yang dibuat tentang kurangnya lokalitas di Jawa pada umumnya, implementasi OpenJDK tentang TreeSet/ TreeMapbukan 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 .
kbolino
25

HashSetadalah O (1) untuk mengakses elemen, jadi tentu saja itu penting. Tetapi mempertahankan urutan objek di set tidak mungkin dilakukan.

TreeSetberguna 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 untukTreeSet :

Implementasi ini memberikan jaminan log (n) biaya waktu untuk operasi dasar ( add, removedan contains).

Duffymo
sumber
22

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

 TreeSet<String> ts = new TreeSet<String>();
 ts.add(null); // throws NullPointerException

 HashSet<String> hs = new HashSet<String>();
 hs.add(null); // runs fine
SuReN
sumber
3
ts.add (null) itu akan berfungsi dengan baik jika TreeSet jika nol ditambahkan sebagai Objek pertama di TreeSet. Dan objek apa pun yang ditambahkan setelah itu akan memberikan NullPointerException dalam metode compareTo dari Comparator.
Shoaib Chikate
2
Anda benar-benar tidak boleh menambahkan nullke set Anda dengan cara baik.
Fluffy
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);
Dávid Horváth
21

Mendasarkan pada jawaban visual yang bagus di Maps oleh @shevchyk, inilah pilihan saya:

╔══════════════╦═════════════════════╦═══════════════════╦═════════════════════╗
   Property          HashSet             TreeSet           LinkedHashSet   
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
                no guarantee order  sorted according                       
   Order       will remain constant to the natural        insertion-order  
                    over time          ordering                            
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
 Add/remove           O(1)              O(log(n))             O(1)         
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
                                      NavigableSet                         
  Interfaces           Set                Set                  Set         
                                       SortedSet                           
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
                                       not allowed                         
  Null values        allowed        1st element only        allowed        
                                        in Java 7                          
╠══════════════╬═════════════════════╩═══════════════════╩═════════════════════╣
                 Fail-fast behavior of an iterator cannot be guaranteed      
   Fail-fast   impossible to make any hard guarantees in the presence of     
   behavior              unsynchronized concurrent modification              
╠══════════════╬═══════════════════════════════════════════════════════════════╣
      Is                                                                     
 synchronized               implementation is not synchronized               
╚══════════════╩═══════════════════════════════════════════════════════════════╝
kiedysktos
sumber
13

Alasan mengapa sebagian besar digunakan HashSetadalah 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 menerapkan hashCodeuntuk menggunakan HashSet(meskipun Java Efektif menunjukkan caranya), tetapi jika Anda menggunakan TreeSetAnda harus membuatnya Comparableatau menyediakan a Comparator. Ini bisa menjadi masalah jika kelas tidak memiliki urutan tertentu.

Saya kadang-kadang menggunakan TreeSet(atau sebenarnya TreeMap) 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 TreeSetsudah 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.

Kathy Van Stone
sumber
setiap data menunjuk pada elemen-elemen besar ini seperti 10K atau lebih
kuhajeyan
11

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 )

Jason True
sumber
7

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.

Joseph Weissman
sumber
4

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

subhash laghate
sumber
3

Banyak jawaban telah diberikan, berdasarkan pertimbangan teknis, terutama seputar kinerja. Menurut saya, pilihan antara TreeSetdan HashSethal - 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 fungsi compareTo, yang harus konsisten dengan fungsi pengembalian apa equals. Sebagai contoh jika Anda memiliki satu set objek dari kelas yang disebut Siswa, maka saya tidak berpikir aTreeSetakan masuk akal, karena tidak ada pemesanan alami antara siswa. Anda dapat memesannya dengan nilai rata-rata, oke, tapi ini bukan "pemesanan alami". Fungsi compareToakan 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, equalsakan menghasilkan false (kecuali jika Anda memutuskan untuk membuat yang kedua kembali benar ketika dua siswa berbeda memiliki nilai yang sama, yang akan membuat equalsfungsi memiliki makna yang menyesatkan, tidak untuk mengatakan makna yang salah.)
Harap perhatikan konsistensi antara equalsdan compareTobersifat opsional, tetapi sangat disarankan. Kalau tidak, kontrak antarmuka Setterputus, 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.

Marek Stanley
sumber
3

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

pengguna924272
sumber
1

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.

Nicholas Jordan
sumber
-3
import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;

public class HashTreeSetCompare {

    //It is generally faster to add elements to the HashSet and then
    //convert the collection to a TreeSet for a duplicate-free sorted
    //Traversal.

    //really? 
    O(Hash + tree set) > O(tree set) ??
    Really???? Why?



    public static void main(String args[]) {

        int size = 80000;
        useHashThenTreeSet(size);
        useTreeSetOnly(size);

    }

    private static void useTreeSetOnly(int size) {

        System.out.println("useTreeSetOnly: ");
        long start = System.currentTimeMillis();
        Set<String> sortedSet = new TreeSet<String>();

        for (int i = 0; i < size; i++) {
            sortedSet.add(i + "");
        }

        //System.out.println(sortedSet);
        long end = System.currentTimeMillis();

        System.out.println("useTreeSetOnly: " + (end - start));
    }

    private static void useHashThenTreeSet(int size) {

        System.out.println("useHashThenTreeSet: ");
        long start = System.currentTimeMillis();
        Set<String> set = new HashSet<String>();

        for (int i = 0; i < size; i++) {
            set.add(i + "");
        }

        Set<String> sortedSet = new TreeSet<String>(set);
        //System.out.println(sortedSet);
        long end = System.currentTimeMillis();

        System.out.println("useHashThenTreeSet: " + (end - start));
    }
}
gli00001
sumber
1
Tulisan itu mengatakan Secara umum lebih cepat untuk menambahkan elemen ke HashSet dan kemudian mengonversi koleksi ke TreeSet untuk traversal diurutkan yang bebas duplikat. Set <String> s = TreeSet baru <String> (hashSet); Saya bertanya-tanya mengapa tidak Set <String> s = TreeSet baru <String> () secara langsung jika kita tahu itu akan digunakan untuk iterasi yang diurutkan, jadi saya membuat perbandingan ini dan hasilnya menunjukkan mana yang lebih cepat.
gli00001
"Dalam kasus apa saya ingin menggunakan HashSet di atas TreeSet?"
Austin Henley
1
maksud saya adalah, jika Anda perlu memesan, gunakan TreeSet saja lebih baik daripada meletakkan semuanya ke HashSet kemudian membuat TreeSet berdasarkan pada HashSet itu. Saya tidak melihat nilai HashSet + TreeSet sama sekali dari posting asli.
gli00001
@ gli00001: Anda melewatkan intinya. Jika Anda tidak selalu memerlukan set elemen untuk diurutkan, tetapi akan memanipulasinya lebih sering, maka itu akan layak bagi Anda untuk menggunakan hashset untuk mendapatkan keuntungan dari operasi yang lebih cepat sebagian besar waktu. Untuk saat - saat sesekali di mana Anda perlu memproses elemen-elemen secara berurutan, maka cukup bungkus dengan treeet. Itu tergantung pada use case Anda, tapi itu tidak terlalu umum use case (dan yang mungkin mengasumsikan set yang tidak mengandung terlalu banyak elemen dan dengan aturan pemesanan yang kompleks).
haylem