Fungsi Hash dan Kod Hash

Fungsi cincang biasa mula-mula menukar kunci carian kepada nilai integer yang dipanggil kod cincang, kemudian memampatkan kod cincang ke dalam indeks kepada jadual cincang. Kelas akar Java Objek mempunyai kaedah hashCode, yang mengembalikan kod cincang integer. Secara lalai, kaedah mengembalikan alamat memori untuk objek. Kontrak am untuk kaedah hashCode adalah seperti berikut:

1. Anda harus mengatasi kaedah kod cincang apabila kaedah sama dengan ditindih untuk memastikan dua objek yang sama mengembalikan kod cincang yang sama.
2. Semasa pelaksanaan program, menggunakan kaedah hashCode berbilang kali mengembalikan integer yang sama, dengan syarat data objek tidak diubah.
3. Dua objek yang tidak sama rata mungkin mempunyai kod cincang yang sama, tetapi anda harus melaksanakan kaedah Kod cincang untuk mengelakkan terlalu banyak kes sedemikian.

Kod Hash untuk Jenis Primitif

Untuk kunci carian jenis bait, pendek, int dan char, hanya hantar ke int . Oleh itu, dua kekunci carian berbeza daripada mana-mana jenis ini akan mempunyai kod cincang yang berbeza.

Untuk kunci carian jenis float, gunakan Float.floatToIntBits(key) sebagai kod cincang. Ambil perhatian bahawa floatToIntBits(float f) mengembalikan nilai int yang perwakilan bitnya sama dengan perwakilan bit untuk nombor terapung f. Oleh itu, dua kekunci carian berbeza jenis terapung akan mempunyai kod cincang yang berbeza.

Untuk kunci carian jenis panjang, hanya menghantarnya ke int bukanlah pilihan yang baik, kerana semua kunci yang berbeza hanya dalam 32 bit pertama akan mempunyai kod hash yang sama. Untuk mengambil kira 32 bit pertama, bahagikan 64 bit kepada dua bahagian dan lakukan operasi eksklusif atau untuk menggabungkan dua bahagian. Proses ini dipanggil melipat. Kod cincang untuk kunci panjang ialah

int hashCode = (int)(key ^ (key >> 32));

Perhatikan bahawa >> ialah operator anjakan kanan yang mengalihkan bit 32 kedudukan ke kanan. Contohnya, 1010110 >> 2 menghasilkan 0010101. ^ ialah pengendali eksklusif atau bitwise. Ia beroperasi pada dua bit yang sepadan bagi operan binari. Contohnya, 1010110 ^ 0110111 menghasilkan 1100001.

Untuk kunci carian jenis double, tukarkannya kepada nilai panjang menggunakan kaedah Double.doubleToLongBits dan kemudian lakukan lipatan sebagai berikut:

bit panjang = Double.doubleToLongBits(key);
int hashCode = (int)(bit ^ (bit >> 32));

Kod Hash untuk Rentetan

Kekunci carian selalunya merupakan rentetan, jadi adalah penting untuk mereka bentuk fungsi cincang yang baik untuk rentetan. Pendekatan intuitif ialah menjumlahkan Unicode semua aksara sebagai kod cincang untuk rentetan. Pendekatan ini mungkin berfungsi jika dua kekunci carian dalam aplikasi tidak mengandungi huruf yang sama, tetapi ia akan menghasilkan banyak perlanggaran jika kekunci carian mengandungi huruf yang sama, seperti tod dan titik .

Pendekatan yang lebih baik ialah menjana kod cincang yang mengambil kira kedudukan aksara. Khususnya, biarkan kod cincang menjadi

s0*b(n - 1) + s1*b(n - 2) + c + sn-1

di mana si s.charAt(i). Ungkapan ini ialah polinomial untuk beberapa b positif, jadi ini dipanggil kod cincang polinomial. Menggunakan peraturan Horner untuk penilaian polinomial (lihat Kajian Kes: Menukar Heksadesimal kepada Perpuluhan), kod cincang boleh dikira dengan cekap seperti berikut:

(...((s0*b + s1)b + s2)b + ... + sn-2)b + sn-1

Pengiraan ini boleh menyebabkan limpahan untuk rentetan panjang, tetapi limpahan aritmetik diabaikan di Jawa. Anda harus memilih nilai b yang sesuai untuk meminimumkan perlanggaran. Eksperimen menunjukkan bahawa pilihan yang baik untuk b ialah 31, 33, 37, 39 dan 41. Dalam kelas String, Kod cincang ditindih menggunakan kod cincang polinomial dengan b ialah 31.

Memampatkan Kod Hash

Kod cincang untuk kunci boleh menjadi integer besar yang berada di luar julat untuk indeks jadual cincang, jadi anda perlu mengecilkannya agar muat dalam julat indeks. Andaikan indeks untuk jadual cincang adalah antara 0 dan N-1. Cara paling biasa untuk menskalakan integer kepada antara 0 dan N-1 ialah menggunakan

h(Kod cincang) = Kod cincang % N

Untuk memastikan indeks tersebar sama rata, pilih N untuk menjadi nombor perdana lebih besar daripada 2.

Sebaik-baiknya, anda harus memilih nombor perdana untuk N. Walau bagaimanapun, ia memakan masa untuk mencari nombor perdana yang besar. Dalam pelaksanaan API Java untuk java.util.HashMap, N ditetapkan kepada nilai kuasa 2. Terdapat sebab yang baik untuk pilihan ini. Apabila N ialah nilai kuasa 2,

h(Kod cincang) = Kod cincang % N

sama dengan

h(Kod cincang) = Kod cincang & (N – 1)

Ampersan, &, ialah pengendali DAN secara bitwise. DAN bagi dua bit yang sepadan menghasilkan 1 jika kedua-dua bit adalah 1. Sebagai contoh, anggap N = 4 dan Kod cincang = 11, 11 % 4 = 3, yang sama dengan 01011 & 00011 = 11. Pengendali & boleh dilakukan dengan lebih pantas daripada pengendali %.

Untuk memastikan pencincangan diagihkan secara sama rata, fungsi cincang tambahan juga digunakan bersama-sama dengan fungsi cincang utama dalam pelaksanaan java.util.HashMap. Fungsi ini ditakrifkan sebagai:

int statik peribadi supplementalHash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
kembali h ^ (h >>> 7) ^ (h >>> 4);
}

^ dan >>> adalah operasi anjakan kanan bitwise eksklusif-atau dan tidak ditandatangani. Operasi bitwise jauh lebih cepat daripada operasi pendaraban, bahagi dan baki. Anda harus menggantikan operasi ini dengan operasi bitwise apabila boleh.

Fungsi cincang yang lengkap ditakrifkan sebagai:

h(Kod hash) = tambahanHash(Kod cincang) % N

Ini sama dengan

h(Kod cincang) = Hash tambahan(Kod cincang) & (N – 1)

kerana N ialah nilai kuasa 2.

Atas ialah kandungan terperinci Fungsi Hash dan Kod Hash. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!