Implementasi antarmuka Set dan Antrian

"Nah, bagaimana prosesor Anda?"

"Tidak apa-apa. Saya duduk di nitrogen cair selama satu jam, jadi sekarang saya seperti baru!"

"Bagus. Kalau begitu mari kita lanjutkan."

"Atur koleksi."

Secara matematis, himpunan adalah sekelompok elemen unik. Jadi, dalam pemrograman, Set adalah kumpulan elemen unik, yaitu kumpulan yang tidak memungkinkan Anda menyimpan elemen identik.

"Aku tidak tahu apakah Ellie menunjukkanmu hierarki warisan Set. Jika tidak, ini dia:"

"A HashSet adalah kumpulan yang menyimpan elemen secara internal menggunakan nilai hash yang dikembalikan oleh metode hashCode ()."

"Untuk kemudahan, HashSet<E> menyimpan objek HashMap<E, Object> yang menyimpan nilai HashSet sebagai kunci."

"Wah!"

"Menggunakan kode hash memungkinkan Anda mencari, menambah, dan menghapus elemen dari Set dengan cepat."

"Tetapi perlu diingat bahwa kelas Anda harus menerapkan metode hashCode & equals dengan benar untuk menambahkan objek kelas Anda ke Set, dan menemukannya dengan benar di sana."

"Kedua metode banyak digunakan di dalam HashSet/HashMap. "

"Jika Anda lupa mengimplementasikan metode kode hash (), maka Anda berisiko tidak dapat menemukan objek Anda di Set, meskipun objek itu ada."

"Ya, saya ingat, saya ingat. Anda memberi tahu saya tentang ini sebelumnya. Saya sudah mendengar semuanya."

"Oke. Lalu ini beberapa informasi berguna untukmu."

"Misalkan Anda telah mengimplementasikan kode hash dan sama dengan  benar di kelas Anda, dan Anda dengan senang hati menyimpan objek Anda di Set."

"Tapi kemudian Anda pergi dan mengubah salah satu objek, dan dengan demikian Anda mengubah data internal yang digunakan untuk menghitung hashnya . Jadi hash objek berubah."

"Dan ini berarti saat Anda mencarinya di Set, Anda mungkin tidak akan menemukannya."

"Whoa! Bagaimana cara kerjanya?"

"Ini adalah jebakan terkenal saat bekerja dengan hash. Intinya, pencarian HashSet (dan HashMap) hanya dijamin berfungsi dengan baik jika objeknya tidak dapat diubah ."

"Whoa! Dan apa, tidak ada yang melakukan apa-apa?"

"Semua orang berpura-pura bahwa masalahnya tidak ada. Tapi ini sering muncul dalam wawancara, jadi mungkin perlu diingat…"

" LinkedHashSet adalah HashSet yang elemennya juga disimpan dalam daftar tertaut. HashSet normal tidak mendukung pengurutan elemen. Pertama, ini bukan operasi resmi. Kedua, bahkan urutan internal dapat berubah secara signifikan ketika satu elemen ditambahkan."

Tapi Anda bisa mendapatkan iterator dari LinkedHashSet dan menggunakannya untuk menelusuri semua elemen sesuai urutan penambahannya ke LinkedHashSet . Itu tidak sering terjadi, tapi terkadang ini sangat dibutuhkan."

"Begitu. Aku suka ketika ada kelas untuk skenario «berjaga-jaga» ini. Kasus seperti itu tidak terlalu langka."

" TreeSet adalah kumpulan yang menyimpan elemen dalam bentuk pohon yang diurutkan berdasarkan nilai. TreeSet <E> berisi TreeMap <E, Object> yang menyimpan semua nilai tersebut. Dan TreeMap ini menggunakan pohon merah -hitam seimbang untuk menyimpan elemen . Akibatnya, ini mendukung operasi tambah, hapus, dan isi yang sangat cepat."

"Ya, aku ingat. Kami membahasnya baru-baru ini. Dan aku juga memikirkan di mana ini digunakan."

"Dan ternyata beberapa koleksi Java yang paling populer menggunakannya."

"Ya. Omong-omong, pewawancara sering bertanya tentang TreeSet . Mereka biasanya mencoba menipu Anda. Mereka akan berkata, 'jika TreeSet menggunakan pohon biner, maka semua elemen dapat membentuk satu cabang panjang, jadi pencarian akan memakan waktu waktu yang lama «Ini hanya waktu untuk menempatkan orang yang kurang ajar di tempatnya dengan menyatakan, "Bahkan seorang anak pun tahu bahwa TreeSet dan TreeMap menggunakan pohon merah - hitam yang seimbang , sehingga situasi itu sebenarnya tidak mungkin."

"Ah. Aku ingin sekali melihat wajah orang yang menanyakan pertanyaan itu. Aku bahkan mungkin akan mengingat kalimat itu. …"

"Namun dalam praktiknya, Set ternyata tidak sesederhana yang saya kira semula."

"Di sisi lain, situasi dengan Queue jauh lebih sederhana:"

" Antrean mengimplementasikan antrean. Elemen ditambahkan ke akhir antrean dan diambil dari depan."

" PriorityQueue sebenarnya adalah satu-satunya implementasi klasik dari antarmuka Queue , tidak termasuk LinkedList , yang secara teknis juga merupakan antrian."

"Oke, aku lelah. Itu saja untuk hari ini. Sampai lain kali."