Fungsi Hash
Petakan kunci ke bucket.
Fungsi Hash adalah pelajaran C Academy gratis di CoddyKit. Ini adalah pelajaran 1 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar C Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus C Academy mencakup 4 pelajaran total.
Apa Itu Fungsi Hash
Fungsi hash menerima kunci dan menghasilkan indeks bilangan bulat ke dalam larik bucket. Fungsi ini merupakan inti tabel hash, yang mengubah kunci sembarang seperti string menjadi posisi larik yang dapat diakses dengan cepat.
- Masukan: sebuah kunci (string, bilangan bulat, dan sebagainya)
- Keluaran: indeks bucket dalam
[0, capacity)
Sifat Hash yang Baik
Fungsi hash yang baik bersifat deterministik, cepat, dan menyebarkan kunci secara merata ke seluruh bucket.
- Kunci yang sama selalu menghasilkan indeks yang sama
- Perubahan kecil pada kunci menyebabkan perubahan indeks yang besar (efek longsoran)
- Sedikit tabrakan untuk data pada umumnya
Memetakan ke Bucket
Setelah menghitung nilai hash mentah, petakan nilai tersebut ke dalam tabel menggunakan operator modulo: index = hash % capacity.
Gunakan tipe unsigned agar modulo tidak pernah menghasilkan indeks negatif.
#include <stdio.h>
int main(void) {
unsigned long hash = 123456789UL;
unsigned capacity = 16;
unsigned index = (unsigned)(hash % capacity);
printf("bucket = %u\n", index);
return 0;
}Hash Jumlah Sederhana
Hash string paling sederhana menjumlahkan nilai karakter. Cara ini mudah, tetapi distribusinya buruk karena anagram mengalami tabrakan.
Jalankan untuk melihat dua string berbeda yang menghasilkan hash dengan nilai berdekatan.
#include <stdio.h>
unsigned long sum_hash(const char *s) {
unsigned long h = 0;
while (*s) h += (unsigned char)*s++;
return h;
}
int main(void) {
printf("%lu\n", sum_hash("abc"));
printf("%lu\n", sum_hash("cba"));
return 0;
}Hash DJB2
DJB2 adalah hash string klasik dengan distribusi baik, karya Daniel J. Bernstein. Hash ini dimulai dari 5381 dan menggunakan hash * 33 + c.
Perkalian dan penjumlahan mencampur bit jauh lebih baik daripada penjumlahan biasa.
#include <stdio.h>
unsigned long djb2(const char *s) {
unsigned long h = 5381;
int c;
while ((c = (unsigned char)*s++))
h = ((h << 5) + h) + c; /* h * 33 + c */
return h;
}
int main(void) {
printf("%lu\n", djb2("hello"));
printf("%lu\n", djb2("world"));
return 0;
}Hash FNV-1a
FNV-1a melakukan XOR pada setiap byte, lalu mengalikannya dengan bilangan prima. Cara ini sederhana, cepat, dan banyak digunakan.
Urutannya: lakukan XOR terlebih dahulu, lalu perkalian (itulah varian 1a).
#include <stdio.h>
unsigned long fnv1a(const char *s) {
unsigned long h = 1469598103934665603UL;
while (*s) {
h ^= (unsigned char)*s++;
h *= 1099511628211UL;
}
return h;
}
int main(void) {
printf("%lu\n", fnv1a("key1"));
printf("%lu\n", fnv1a("key2"));
return 0;
}Melakukan Hash pada Bilangan Bulat
Kunci bilangan bulat tetap memerlukan pencampuran, karena x % capacity saja akan mengelompokkan nilai saat kunci memiliki pola yang sama. Pencampuran multiplikatif (Knuth) menyebarkan bit.
#include <stdio.h>
unsigned hash_int(unsigned x, unsigned cap) {
x *= 2654435761u; /* Knuth multiplicative */
return x % cap;
}
int main(void) {
for (unsigned i = 0; i < 5; i++)
printf("%u -> %u\n", i, hash_int(i, 8));
return 0;
}Kapasitas Pangkat Dua
Saat kapasitas merupakan pangkat dua, Anda dapat mengganti % capacity dengan AND bitwise yang cepat: hash & (capacity - 1).
Ini hanya berfungsi karena bit rendah dari pangkat dua dikurangi satu membentuk masker penuh.
#include <stdio.h>
int main(void) {
unsigned long hash = 123456789UL;
unsigned capacity = 16; /* power of two */
unsigned index = (unsigned)(hash & (capacity - 1));
printf("bucket = %u\n", index);
return 0;
}Mengapa Modulo Bisa Lambat
Operator % dikompilasi menjadi instruksi pembagian, yang lebih lambat daripada AND. Dalam perulangan ketat, hal ini berpengaruh.
- Tabel berpangkat dua: gunakan masker AND
- Tabel berukuran prima: gunakan modulo (distribusi lebih baik untuk hash yang lemah)
Tabrakan Tidak Terhindarkan
Berdasarkan prinsip sarang merpati, pemetaan banyak kunci ke jumlah bucket yang lebih sedikit pasti menghasilkan tabrakan. Hash yang baik meminimalkannya, tetapi tidak dapat menghilangkannya.
Pelajaran berikutnya membahas cara menangani tabrakan.
Demonstrasi Distribusi
Mari kita hitung bagaimana DJB2 mendistribusikan beberapa kunci ke 8 bucket. Hash yang baik menyebarkan nilai dengan cukup merata.
#include <stdio.h>
unsigned long djb2(const char *s) {
unsigned long h = 5381;
int c;
while ((c = (unsigned char)*s++)) h = ((h << 5) + h) + c;
return h;
}
int main(void) {
const char *keys[] = {"apple", "banana", "cherry", "date"};
int counts[8] = {0};
for (int i = 0; i < 4; i++)
counts[djb2(keys[i]) % 8]++;
for (int i = 0; i < 8; i++)
printf("bucket %d: %d\n", i, counts[i]);
return 0;
}Pemeriksaan Singkat
Uji pemahaman Anda tentang dasar-dasar fungsi hash.
Ringkasan
Anda telah mempelajari fungsi hash dan cara memetakan kunci ke bucket.
- Hash yang baik bersifat deterministik, cepat, dan merata
- DJB2 dan FNV-1a adalah hash string yang andal
- Gunakan
% capacity, atau& (capacity-1)untuk pangkat dua - Gunakan tipe unsigned; tabrakan tidak dapat dihindari
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Fungsi Hash” gratis?
Ya — teks lengkap “Fungsi Hash” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus C Academy, upgrade ke CoddyKit PRO. Kursus C Academy mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Fungsi Hash”?
Petakan kunci ke bucket. Kamu berlatih C Academy dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai C Academy?
Tidak diperlukan pengalaman sebelumnya. C Academy di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 1 dari 4.
Berapa lama pelajaran “Fungsi Hash” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran C Academy ini?
Ya. Setiap pelajaran C Academy menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.