Hashtables

21 Jun 2002

S: Apabila saya menggunakan objek sebagai kunci dalam Meja Hash, apa yang mesti saya ganti di kelas Objek dan mengapa?

J: Apabila anda membuat objek kunci anda sendiri untuk digunakan di Hashtable, anda mesti mengganti Object.equals()dan Object.hashCode()kaedah kerana Hashtablemenggunakan kombinasi kunci hashCode()dan equals()kaedah untuk menyimpan dan mengambil entri dengan cepat. Ini juga merupakan peraturan umum bahawa apabila anda mengatasi equals(), anda selalu mengatasi hashCode().

Lebih banyak mengenai mengapa

Penjelasan yang sedikit lebih mendalam akan membantu anda memahami Hashtablemekanisme penyimpanan dan pengambilan. Secara Hashtabledalaman mengandungi baldi di mana ia menyimpan pasangan kunci / nilai. The Hashtablekegunaan kodcincang utama untuk menentukan mana baldi pasangan kunci / nilai perlu peta.

Rajah 1 menunjukkan a Hashtabledan baldi. Apabila anda memberikan kunci / nilai ke Hashtable, ia akan menanyakan kod hash kunci. The Hashtablekegunaan yang kod untuk menentukan baldi di mana untuk meletakkan kunci / nilai. Jadi, sebagai contoh, jika kod hash sama dengan sifar, Hashtablemeletakkan nilainya ke dalam Bucket 0. Begitu juga, jika kod hash adalah dua, Hashtablemeletakkan nilainya ke dalam Bucket 2. (Ini adalah contoh ringkas; yang Hashtableakan mengurut kod hash terlebih dahulu sehingga Hashtabletidak cuba memasukkan nilai di luar baldi.)

Dengan menggunakan kod hash dengan cara ini, kaleng Hashtablejuga dapat menentukan dengan cepat di mana baldi itu telah menempatkan nilainya ketika anda cuba mengambilnya.

Walau bagaimanapun, kod Hash hanya mewakili separuh gambar. Kod hash hanya memberitahu ke Hashtabledalam baldi mana untuk menurunkan kunci / nilai. Namun, kadangkala, beberapa objek boleh dipetakan ke baldi yang sama, suatu peristiwa yang dikenali sebagai perlanggaran. Di Jawa, Hashtabletindak balas terhadap perlanggaran dengan meletakkan beberapa nilai ke dalam baldi yang sama (implementasi lain dapat menangani perlanggaran secara berbeza). Gambar 2 menunjukkan bagaimana Hashtablerupa selepas beberapa perlanggaran.

Sekarang bayangkan bahawa anda memanggil get()dengan kunci yang memetakan ke Bucket 0. HashtableSekarang keperluan untuk melakukan carian berurutan melalui pasangan kunci / nilai di Bucket 0 untuk mencari nilai yang anda minta. Untuk melakukan carian ini, lakukan Hashtablelangkah-langkah berikut:

  1. Pertanyaan kod hash kunci
  2. Dapatkan senarai kunci / nilai yang terdapat di dalam baldi yang diberikan oleh kod hash
  3. Imbas setiap entri secara berurutan sehingga kunci yang sama dengan kunci yang dihantar get()dijumpai

Jawapan panjang untuk soalan pendek yang saya tahu, tetapi semakin teruk. Mengatasi dengan betul equals()dan hashCode()merupakan latihan yang tidak biasa. Anda mesti sangat berhati-hati untuk menjamin kontrak kedua kaedah.

Semasa melaksanakan sama ()

Menurut equals()Javadoc, kaedah itu mesti mematuhi peraturan berikut:

" equals()Kaedah ini menerapkan hubungan kesetaraan:
  • Ini adalah refleksif: Untuk sebarang nilai rujukan x, x.equals(x)hendaklah dikembalikan benar
  • Ia adalah simetrik: Untuk sebarang nilai rujukan x dan y, x.equals(y)harus kembali benar jika dan hanya jika y.equals(x)kembali benar
  • Ia bersifat transitif: Untuk sebarang nilai rujukan x, y, dan z, jika x.equals(y)mengembalikan true dan y.equals(z)mengembalikan true, maka x.equals(z)harus kembali true
  • Ini adalah konsisten: Untuk sebarang nilai rujukan x dan y, pelbagai doa x.equals(y)secara konsisten mengembalikan benar atau secara konsisten mengembalikan palsu, dengan syarat tidak ada maklumat yang digunakan dalam perbandingan yang sama pada objek yang diubah
  • Untuk mana-mana nilai rujukan x-nol, x.equals(null)hendaklah dikembalikan palsu "

Di Java Berkesan, Joshua Bloch menawarkan resipi lima langkah untuk menulis equals()kaedah yang berkesan . Inilah resipi dalam bentuk kod:

kelas awam EffectiveEquals {private int valueA; nilai int swastaB; . . . boolean awam sama dengan (Objek o) {if (ini == o) {// Langkah 1: Lakukan pengujian == pengembalian benar; } if (! (o instanceof EffectiveEquals)) {// Langkah 2: Contoh pengembalian cek palsu; } EffectiveEquals ee = (EffectiveEquals) o; // Langkah 3: Hujah argumen // Langkah 4: Untuk setiap bidang penting, periksa untuk melihat apakah itu sama // Untuk penggunaan primitif == // Untuk objek menggunakan sama () tetapi pastikan juga // menangani kes nol pulangan pertama ee.valueA == nilaiA && ee.valueB == nilaiB; }. . . }

Catatan: Anda tidak perlu melakukan pemeriksaan nol kerana null instanceof EffectiveEqualsakan dinilai menjadi salah.

Akhirnya, untuk Langkah 5, kembali ke equals()kontrak dan tanyakan pada diri anda apakah equals()kaedah ini refleksif, simetrik, dan transitif. Sekiranya tidak, betulkan!

Semasa melaksanakan hashCode ()

Untuk hashCode()kontrak umum, Javadoc mengatakan:

  • "Setiap kali ia dipanggil pada objek yang sama lebih dari sekali selama pelaksanaan 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 pelaksanaan aplikasi ke pelaksanaan lain dari aplikasi yang sama.
  • Sekiranya dua objek sama mengikut equals(Object)kaedah, maka memanggil hashCode()kaedah pada setiap dua objek mesti menghasilkan hasil bilangan bulat yang sama.
  • Tidak diharuskan bahawa jika dua objek tidak sama menurut equals(java.lang.Objectkaedahnya, maka memanggil hashCode()kaedah pada setiap dua objek tersebut mesti menghasilkan hasil bilangan bulat yang berbeza. Namun, pengaturcara harus sedar bahawa menghasilkan hasil bilangan bulat yang berbeza untuk objek yang tidak sama dapat meningkatkan prestasi hashtables. "

Membuat hashCode()kaedah yang betul berfungsi sukar; ia menjadi lebih sukar sekiranya objek yang dimaksudkan tidak berubah. Anda boleh mengira kod hash untuk objek tertentu dengan banyak cara. Kaedah yang paling berkesan mendasarkan nombor pada medan objek. Lebih-lebih lagi, anda boleh menggabungkan nilai-nilai ini dengan pelbagai cara. Berikut adalah dua pendekatan popular:

  • Anda boleh mengubah medan objek menjadi rentetan, menggabungkan rentetan, dan mengembalikan kod hash yang dihasilkan
  • Anda boleh menambahkan kod hash setiap bidang dan mengembalikan hasilnya

Walaupun pendekatan yang lain, lebih teliti ada, dua pendekatan yang disebutkan di atas membuktikan yang paling mudah difahami dan dilaksanakan.

Tony Sintes adalah perunding bebas dan pengasas First Class Consulting, sebuah syarikat perunding yang pakar dalam merapatkan sistem dan latihan perusahaan yang berbeza. Di luar Konsultasi Kelas Pertama, Tony adalah penulis bebas yang aktif, dan juga pengarang Pengaturcaraan Sams Teach Yourself Object-Oriented dalam 21 Hari (Sams, 2001; ISBN: 0672321092).

Ketahui lebih lanjut mengenai topik ini

  • Untuk Hashtable Javadoc, pergi ke

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

  • Vipan Singla's "Implementing equals () dan hashCode ()" memberikan perbincangan mendalam mengenai cara mengatasi kaedah sama dengan () 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

  • Lebih daripada 100 tips Java berwawasan dari beberapa minda terbaik dalam perniagaan, lawatan JavaWorld ' s Java Tips halaman indeks

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

  • Pelajari asas-asas Java dalam perbincangan Pemula Java kami

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

  • Daftar untuk mendapatkan buletin e-mel Core Java mingguan percuma JavaWorld

    //www.javaworld.com/subscribe

  • Anda akan mendapat banyak artikel berkaitan IT dari penerbitan saudara kami di .net

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