Saya percaya kebanyakan orang akrab dengan struktur data tabel hash, dan di banyak tempat, tabel hash digunakan untuk meningkatkan efisiensi pencarian. Ada metode di kelas objek Java:
hashcode int asli int ();
Menurut deklarasi metode ini, dapat dilihat bahwa metode ini mengembalikan nilai numerik tipe int dan merupakan metode lokal, sehingga tidak ada implementasi spesifik yang diberikan di kelas objek.
Mengapa kelas objek membutuhkan metode seperti itu? Apa fungsinya? Hari ini kita akan membahas metode kode hashcode secara rinci.
1. Fungsi metode kode hash
Untuk bahasa pemrograman yang mengandung jenis wadah, kode hash pada dasarnya terlibat. Hal yang sama berlaku di Java. Fungsi utama dari metode hashCode adalah bekerja secara normal dengan set berbasis hash, set hash tersebut termasuk hashset, hashmap dan hashtable.
Kenapa kamu bilang begitu? Pertimbangkan situasi di mana ketika suatu objek dimasukkan ke dalam koleksi, bagaimana menentukan apakah objek sudah ada dalam koleksi? (Catatan: Elemen duplikat tidak diizinkan dalam koleksi)
Mungkin kebanyakan orang akan berpikir untuk memanggil metode yang sama untuk membandingkan satu per satu, dan metode ini memang layak. Namun, jika sudah ada sepuluh ribu lembar data atau lebih banyak data dalam set, jika metode yang sama digunakan untuk membandingkan satu per satu, efisiensi pasti akan menjadi masalah. Pada saat ini, fungsi metode hashcode tercermin. Ketika objek baru akan ditambahkan ke koleksi, metode kode hashcode objek dipanggil pertama untuk mendapatkan nilai kode hash yang sesuai. Bahkan, dalam implementasi spesifik hashmap, tabel akan digunakan untuk menyimpan nilai kode hashcode dari objek yang telah disimpan. Jika tidak ada nilai kode hash dalam tabel, itu dapat disimpan secara langsung tanpa perbandingan. Jika nilai hashCode ada, metode yang sama dipanggil untuk membandingkan dengan elemen baru. Jika hal yang sama benar, alamat lain tidak akan disimpan. Karena itu, ada masalah resolusi konflik di sini. Dengan cara ini, berapa kali metode yang sama sebenarnya disebut sangat berkurang. Sederhananya: metode kode hash dalam java memetakan informasi yang terkait dengan objek (seperti alamat penyimpanan objek, bidang objek, dll.) Ke dalam nilai numerik sesuai dengan aturan tertentu, dan nilai ini disebut nilai hash. Kode berikut adalah implementasi spesifik dari metode put di java.util.hashmap:
public v put (key k, nilai v) {if (key == null) return putfornullKey (nilai); int hash = hash (key.hashcode ()); int i = indexfor (hash, table.length); untuk (entri <k, v> e = tabel [i]; e! = null; e = e.next) {objek k; if (e.hash == hash && ((k = e.key) == key || key.equals (k))) {v oldValue = E.Value; E.Value = nilai; E.RecordAccess (ini); Kembalikan OldValue; }} modcount ++; addentry (hash, kunci, nilai, i); kembali nol; } Metode put digunakan untuk menambahkan elemen baru ke hashmap. Dari implementasi spesifik dari metode put, kita dapat mengetahui bahwa metode kode hash akan dipanggil terlebih dahulu untuk mendapatkan nilai kode hashcode dari elemen, dan kemudian periksa apakah nilai kode hash ada dalam tabel. Jika ada, hubungi metode yang sama untuk mengatur ulang apakah elemen ada. Jika ada, perbarui nilai nilai, jika tidak tambahkan elemen baru ke hashmap. Dari sini, kita dapat melihat bahwa metode HashCode ada untuk mengurangi jumlah panggilan ke metode yang sama dan dengan demikian meningkatkan efisiensi program.
Beberapa teman secara keliru berpikir bahwa secara default, kode hashCode mengembalikan alamat penyimpanan objek. Bahkan, pandangan ini tidak lengkap. Memang benar bahwa beberapa JVM secara langsung mengembalikan alamat penyimpanan objek saat diimplementasikan, tetapi ini tidak terjadi sebagian besar waktu. Hanya dapat dikatakan bahwa alamat penyimpanan mungkin terkait dengannya. Berikut ini adalah implementasi menghasilkan nilai hash hash di hotspot jvm:
static inline intptr_t get_next_hash (thread * self, oop obj) {intptr_t value = 0; if (hashCode == 0) {// Formulir ini menggunakan RNG Global Park-Miller yang tidak dijaga, // Jadi dimungkinkan untuk dua utas untuk balapan dan menghasilkan RNG yang sama. // Pada sistem MP kita akan memiliki banyak akses RW ke global, sehingga // mekanisme menginduksi banyak lalu lintas koherensi. value = os :: random (); } lain jika (hashCode == 1) {// Variasi ini memiliki properti menjadi stabil (idempotent) // antara operasi STW. Ini dapat berguna dalam beberapa skema sinkronisasi 1-0 //. intptr_t addrbits = intptr_t (obj) >> 3; value = addrbits ^ (addrbits >> 5) ^ gvars.stwrandom; } lain jika (hashCode == 2) {value = 1; // untuk pengujian sensitivitas} lain jika (hashCode == 3) {value = ++ gvars.hcequence; } else if (hashCode == 4) {value = intptr_t (obj); } else {// skema xor-shift Marsaglia dengan status khusus utas // Ini mungkin implementasi keseluruhan terbaik-kita akan // kemungkinan menjadikan ini default dalam rilis mendatang. unsigned t = self-> _ hashstatex; t ^= (t << 11); Self-> _ hashstatex = self-> _ hashstatey; Self-> _ hashstatey = self-> _ hashstatez; Self-> _ hashstatez = self-> _ hashstateW; unsigned v = self-> _ hashstateW; v = (v ^ (v >> 19)) ^ (t ^ (t >> 8)); Self-> _ hashstateW = v; nilai = v; } value & = markoopdesc :: hash_mask; if (value == 0) value = 0xbad; Assert (value! = Markoopdesc :: no_hash, "invarian"); Tevent (HashCode: Generate); nilai pengembalian;}Implementasi ini terletak di file hotspot/src/share/vm/runtime/synchronizer.cpp.
Oleh karena itu, beberapa orang mungkin mengatakan bahwa dapatkah kita secara langsung menilai apakah dua objek sama berdasarkan nilai kode hashcode? Ini tentu saja tidak mungkin, karena objek yang berbeda dapat menghasilkan nilai kode hash yang sama. Meskipun tidak mungkin untuk menilai apakah dua objek sama berdasarkan nilai kode hashcode, Anda dapat secara langsung menilai bahwa kedua objek tidak sama berdasarkan nilai kode hash. Jika nilai kode hash dari kedua objek tidak sama, mereka harus dua objek yang berbeda. Jika Anda ingin menentukan apakah dua objek benar -benar sama, Anda harus menggunakan metode Equals.
Artinya, untuk dua objek, jika hasil yang diperoleh dengan memanggil metode Equals adalah benar, nilai kode hashcode dari dua objek harus sama;
Jika hasil yang diperoleh dengan metode Equals salah, nilai kode hashcode dari dua objek mungkin tidak berbeda;
Jika nilai kode hash dari kedua objek tidak sama, hasil yang diperoleh dengan metode Equals harus salah;
Jika nilai kode hash dari dua objek sama, hasil yang diperoleh dengan metode Equals tidak diketahui.
2. Metode yang sama dan metode kode hash
Dalam beberapa kasus, ketika merancang kelas, pemrogram perlu menulis ulang metode yang sama, seperti kelas string, tetapi pastikan untuk mencatat bahwa saat menulis ulang metode Equals, mereka harus menulis ulang metode kode hash. Kenapa kamu bilang begitu?
Mari kita lihat contoh di bawah ini:
Paket com.cxh.test1; import java.util.hashmap; import java.util.hashset; import java.util.set; class people {private string name; usia int pribadi; orang publik (nama string, int usia) {this.name = name; this.age = usia; } public void setage (int usia) {this.age = usia; } @Override Public Boolean Equals (objek obj) {// TODO METODE AUTO-DIHOMPOKTIFTICET Kembalikan this.name.equals (((People) Obj) .name) && this.age == ((People) obj) .age; }} kelas publik utama {public static void main (string [] args) {people p1 = orang baru ("jack", 12); System.out.println (p1.hashcode ()); Hashmap <people, integer> hashmap = hashmap baru <people, integer> (); hashmap.put (p1, 1); System.out.println (hashmap.get (orang baru ("jack", 12));}}Di sini saya hanya menulis ulang metode yang sama, yang berarti bahwa jika dua orang objek memiliki nama dan usia yang sama, mereka dianggap orang yang sama.
Tujuan asli dari kode ini adalah untuk menghasilkan hasil "1", tetapi sebenarnya itu menghasilkan "null". Mengapa? Alasannya adalah Anda lupa untuk menulis ulang metode kode hash saat menulis ulang metode Equals.
Meskipun dua objek dengan nama dan usia yang sama ditentukan secara logis untuk menjadi sama (mirip dengan kelas string), harus diketahui bahwa secara default, metode kode hashcode memetakan alamat penyimpanan objek. Maka tidak mengherankan bahwa hasil output dari kode di atas adalah "nol". Alasannya sangat sederhana, objek yang ditunjuk oleh P1 dan
System.out.println (hashmap.get (orang baru ("jack", 12)); orang baru ("jack", 12) dalam kalimat ini menghasilkan dua objek, dan alamat penyimpanannya harus berbeda. Berikut ini adalah implementasi spesifik dari metode GET HashMap:
public v get (kunci objek) {if (key == null) return getFornullKey (); int hash = hash (key.hashcode ()); untuk (entri <k, v> e = tabel [indexfor (hash, table.length)]; e! = null; e = e.next) {objek k; if (e.hash == hash && ((k = e.key) == key || key.equals (k))) mengembalikan E.Value; } return null; }Oleh karena itu, ketika hashmap digunakan untuk mendapatkan, karena nilai hashcdoe yang diperoleh berbeda (perhatikan bahwa kode di atas mungkin mendapatkan nilai kode hash yang sama dalam beberapa kasus, tetapi probabilitasnya relatif kecil, karena meskipun alamat penyimpanan dari kedua objek tersebut tidak akan dieksekusi dalam hal yang akan dijalankan dan tidak akan dieksekusi.
Oleh karena itu, jika Anda ingin kode di atas untuk menghasilkan hasil "1", itu sangat sederhana. Anda hanya perlu menulis ulang metode kode hash dan membuat metode yang sama dan metode kode hash selalu konsisten secara logis.
Paket com.cxh.test1; import java.util.hashmap; import java.util.hashset; import java.util.set; class people {private string name; usia int pribadi; orang publik (nama string, int usia) {this.name = name; this.age = usia; } public void setage (int usia) {this.age = usia; } @Override public int hashCode () {// TODO METODE AUTO-AUTO-ENTEERATED Stub return name.HashCode ()*37+usia; } @Override Public Boolean Equals (objek obj) {// TODO METODE AUTO-DIHOMPOKTIFTICET Kembalikan this.name.equals (((People) Obj) .name) && this.age == ((People) obj) .age; }} kelas publik utama {public static void main (string [] args) {people p1 = orang baru ("jack", 12); System.out.println (p1.hashcode ()); Hashmap <people, integer> hashmap = hashmap baru <people, integer> (); hashmap.put (p1, 1); System.out.println (hashmap.get (orang baru ("jack", 12))); }}Dengan cara ini, hasil output akan menjadi "1".
Bagian berikut dikutip dari buku Java yang efektif:
Selama pelaksanaan program, selama informasi yang digunakan dalam operasi perbandingan metode Equals belum dimodifikasi, metode kode hashcode harus secara konsisten mengembalikan bilangan bulat yang sama.
Jika kedua objek tersebut sama sesuai dengan metode yang sama, maka memanggil metode kode hashcode dari dua objek harus mengembalikan hasil integer yang sama.
Jika kedua objek dibandingkan ketidaksetaraan sesuai dengan metode yang sama, metode kode hash tidak selalu mengembalikan bilangan bulat yang berbeda.
Sangat mudah untuk memahami artikel kedua dan ketiga, tetapi artikel pertama sering diabaikan. Ada juga bagian yang mirip dengan yang pertama di halaman P495 dalam buku "Java Programming Thought"::
Faktor terpenting saat merancang hashcode () adalah: setiap kali Anda memanggil kode hashcode () pada objek yang sama, nilai yang sama harus dihasilkan. Jika suatu objek ditambahkan ke hashmap dengan put (), dan nilai hashcode lain yang dihasilkan, jika ada data yang dihasilkan oleh mereka, jika ada objek. Metode hashcode () akan menghasilkan kode hash yang berbeda. "
Inilah contohnya:
paket com.cxh.test1; impor java.util.hashmap; import java.util.hashset; import java.util.set; class people {name string private; usia int pribadi; orang publik (nama string, int usia) {this.name = name; this.age = usia; } public void setage (int usia) {this.age = usia; } @Override public int hashCode () {// TODO METODE AUTO-AUTO-ENTEERATED Stub return name.HashCode ()*37+usia; } @Override Public Boolean Equals (objek obj) {// TODO METODE AUTO-DIHOMPOKTIFTICET Kembalikan this.name.equals (((People) Obj) .name) && this.age == ((People) obj) .age; }} kelas publik utama {public static void main (string [] args) {people p1 = orang baru ("jack", 12); System.out.println (p1.hashcode ()); Hashmap <people, integer> hashmap = hashmap baru <people, integer> (); hashmap.put (p1, 1); p1.setage (13); System.out.println (hashmap.get (p1)); }}Hasil output kode ini adalah "nol", dan semua orang harus jelas tentang alasannya.
Oleh karena itu, ketika merancang metode kode hash dan sama dengan metode, jika data dalam objek mudah berubah, yang terbaik adalah tidak mengandalkan bidang ini dalam metode yang sama dan metode kode hash.
Di atas adalah semua konten artikel ini. Saya berharap ini akan membantu untuk pembelajaran semua orang dan saya harap semua orang akan lebih mendukung wulin.com.