Hashtables

21 Juni 2002

T: Saat saya menggunakan objek sebagai kunci dalam Hashtable, apa di kelas Object yang harus saya ganti dan mengapa?

J: Saat Anda membuat objek kunci sendiri untuk digunakan di a Hashtable, Anda harus mengganti metode Object.equals()dan Object.hashCode()karena Hashtablemenggunakan kombinasi kunci hashCode()dan equals()metode untuk menyimpan dan mengambil entri dengan cepat. Ini juga merupakan aturan umum bahwa saat Anda mengganti equals(), Anda selalu menimpa hashCode().

Lebih lanjut tentang mengapa

Penjelasan yang sedikit lebih mendalam akan membantu Anda memahami Hashtablemekanisme penyimpanan dan pengambilan. A secara Hashtableinternal berisi keranjang tempat menyimpan pasangan kunci / nilai. The Hashtablepenggunaan kode hash kunci untuk menentukan ke mana bucket pasangan kunci / nilai harus peta.

Gambar 1 menunjukkan a Hashtabledan kelompoknya. Saat Anda meneruskan kunci / nilai ke Hashtable, kode hash kunci akan ditanyakan. The Hashtablepenggunaan kode untuk menentukan ember di mana untuk menempatkan kunci / nilai. Jadi, misalnya, jika kode hash sama dengan nol, Hashtabletempatkan nilai ke Keranjang 0. Demikian pula, jika kode hash adalah dua, Hashtabletempatkan nilai ke Keranjang 2. (Ini adalah contoh sederhana; Hashtableakan memijat kode hash terlebih dahulu sehingga Hashtabletidak mencoba memasukkan nilai di luar keranjang.)

Dengan menggunakan kode hash dengan cara ini, Hashtabledapat dengan cepat menentukan di keranjang mana ia telah menempatkan nilai saat Anda mencoba mengambilnya.

Hashcode, bagaimanapun, hanya mewakili setengah dari gambar. Kode hash hanya memberi tahu Hashtablebucket mana untuk melepaskan kunci / nilai. Namun terkadang, beberapa objek dapat dipetakan ke keranjang yang sama, peristiwa yang disebut tabrakan. Di Java, Hashtablerespons tabrakan dengan menempatkan beberapa nilai ke dalam keranjang yang sama (implementasi lain mungkin menangani tabrakan secara berbeda). Gambar 2 menunjukkan seperti apa Hashtabletampilan setelah beberapa tabrakan.

Sekarang bayangkan Anda memanggil get()dengan kunci yang dipetakan ke Bucket 0. HashtableSekarang Anda perlu melakukan penelusuran berurutan melalui pasangan kunci / nilai di Bucket 0 untuk menemukan nilai yang Anda minta. Untuk melakukan pencarian ini, Hashtablemenjalankan langkah-langkah berikut:

1. Buat kueri kode hash kunci
2. Ambil daftar kunci / nilai yang berada di keranjang yang diberikan oleh kode hash
3. Memindai melalui setiap entri berurutan sampai kunci yang sama dengan kunci berlalu menjadi get()ditemukan

Jawaban panjang untuk pertanyaan singkat yang saya tahu, tetapi semakin buruk. Menggantikan dengan benar equals()dan hashCode()merupakan latihan yang tidak sepele. Anda harus sangat berhati-hati untuk menjamin kontrak kedua metode.

Saat menerapkan sama dengan ()

Menurut equals()Javadoc, metode tersebut harus sesuai dengan aturan berikut:

" equals()Metode ini mengimplementasikan relasi ekivalen:

• Ini refleksif: Untuk nilai referensi x, x.equals(x)harus mengembalikan true
• Ini simetris: Untuk nilai referensi x dan y, x.equals(y)harus mengembalikan true jika dan hanya jika y.equals(x)mengembalikan true
• Ini transitif: Untuk nilai referensi x, y, dan z, jika x.equals(y)mengembalikan true dan y.equals(z)mengembalikan true, maka x.equals(z)harus mengembalikan true
• Itu konsisten: Untuk nilai referensi x dan y, beberapa pemanggilan yang x.equals(y)secara konsisten mengembalikan benar atau secara konsisten mengembalikan salah, asalkan tidak ada informasi yang digunakan dalam perbandingan yang sama pada objek yang dimodifikasi
• Untuk nilai referensi bukan nol x, x.equals(null)harus mengembalikan salah "

Di Java Efektif, Joshua Bloch menawarkan resep lima langkah untuk menulis equals()metode yang efektif . Berikut resepnya dalam bentuk kode:

public class EffectiveEquals {private int valueA; private int valueB; . . . public boolean sama dengan (Object o) {if (this == o) {// Langkah 1: Lakukan tes == return true; } if (! (o instanceof EffectiveEquals)) {// Langkah 2: Contoh check return false; } EffectiveEquals ee = (EffectiveEquals) o; // Langkah 3: Cast argumen // Langkah 4: Untuk setiap field penting, periksa apakah sama // Untuk primitif gunakan == // Untuk objek gunakan equals () tapi pastikan juga // menangani kasus null pertama kembali ee.valueA == valueA && ee.valueB == valueB; }. . . }

Catatan: Anda tidak perlu melakukan pemeriksaan null karena null instanceof EffectiveEqualsakan mengevaluasi salah.

Terakhir, untuk Langkah 5, kembali ke equals()kontrak dan tanyakan pada diri Anda apakah equals()metodenya refleksif, simetris, dan transitif. Jika tidak, perbaiki!

Saat mengimplementasikan hashCode ()

Untuk hashCode()kontrak umum, Javadoc mengatakan:

• "Setiap kali dipanggil pada objek yang sama lebih dari sekali selama eksekusi aplikasi Java, hashCode()metode harus secara konsisten mengembalikan bilangan bulat yang sama, asalkan tidak ada informasi yang digunakan dalam perbandingan yang sama pada objek yang diubah. Bilangan bulat ini tidak perlu tetap konsisten dari satu eksekusi aplikasi ke eksekusi lain dari aplikasi yang sama.
• Jika dua objek sama menurut equals(Object)metode, maka pemanggilan hashCode()metode pada masing-masing objek harus menghasilkan hasil integer yang sama.
• Tidak diperlukan bahwa jika dua objek tidak sama menurut equals(java.lang.Objectmetode, maka pemanggilan hashCode()metode pada masing-masing objek harus menghasilkan hasil bilangan bulat yang berbeda. Namun, programmer harus menyadari bahwa menghasilkan hasil integer yang berbeda untuk objek yang tidak sama dapat meningkatkan performa hashtable. "

Menciptakan hashCode()metode yang bekerja dengan baik terbukti sulit; menjadi lebih sulit jika objek yang dipermasalahkan tidak tetap. Anda dapat menghitung kode hash untuk objek tertentu dengan berbagai cara. Metode yang paling efektif mendasarkan nomor pada bidang objek. Selain itu, Anda dapat menggabungkan nilai-nilai tersebut dengan berbagai cara. Berikut dua pendekatan populer:

• Anda dapat mengubah bidang objek menjadi string, menggabungkan string, dan mengembalikan kode hash yang dihasilkan
• Anda dapat menambahkan kode hash setiap bidang dan mengembalikan hasilnya

Meskipun ada pendekatan lain yang lebih menyeluruh, kedua pendekatan yang disebutkan di atas terbukti paling mudah dipahami dan diterapkan.

Tony Sintes adalah konsultan independen dan pendiri First Class Consulting, sebuah perusahaan konsultan yang mengkhususkan diri dalam menjembatani sistem dan pelatihan perusahaan yang berbeda. Di luar Konsultasi Kelas Satu, Tony adalah penulis lepas aktif, serta penulis Sams Teach Yourself Object-Oriented Programming in 21 Days (Sams, 2001; ISBN: 0672321092).

Pelajari lebih lanjut tentang topik ini

• Untuk Hashtable Javadoc, buka

  //java.sun.com/j2se/1.4/docs/api/java/util/Hashtable.html

• Vipan Singla's "Implementing equals () and hashCode ()" memberikan diskusi mendalam tentang mengganti metode equals () dan hashCode ()

  //www.vipan.com/htdocs/hashcode_help.html

• The Object.equals() Javadoc

  //java.sun.com/j2se/1.4/docs/api/java/lang/Object.html#equals(java.lang.Object)

• The Object.hashCode() Javadoc

  //java.sun.com/j2se/1.4/docs/api/java/lang/Object.html#hashCode()

• For Joshua Bloch's Effective Java Programming Language Guide (Addison Wesley Professional, 2001; ISBN0201310058), go to

  //www.amazon.com/exec/obidos/ASIN/0201310058/javaworld

• For more articles on Java classes and methods, browse the APIs section of JavaWorld's Topical Index

  //www.javaworld.com/channel_content/jw-apis-index.shtml

• Want more? See the Java Q&A index page for the full Q&A catalog

  //www.javaworld.com/columns/jw-qna-index.shtml

• Selama lebih dari 100 kiat Jawa wawasan dari beberapa pikiran terbaik dalam bisnis ini, kunjungan JavaWorld' s Java Tips halaman indeks

  //www.javaworld.com/columns/jw-tips-index.shtml

• Pelajari dasar-dasar Java dalam diskusi Pemula Java kami

  //forums.idg.net/[email protected]@.ee6b804

• Mendaftarlah untuk mendapatkan buletin email mingguan gratis JavaWorld Core Java

  //www.javaworld.com/subscribe

• Anda akan menemukan banyak artikel terkait TI dari publikasi saudara kita di .net

Cerita ini, "Hashtables" pada awalnya diterbitkan oleh JavaWorld.