Hash Table
Hashing adalah teknik yang digunakan untuk secara unik mengidentifikasi objek tertentu dari sekelompok objek serupa. Beberapa contoh bagaimana hashing digunakan dalam kehidupan kita termasuk:
- Di universitas, setiap siswa diberi nomor gulungan unik yang dapat digunakan untuk mengambil informasi tentang mereka.
- Di perpustakaan, setiap buku diberi nomor unik yang dapat digunakan untuk menentukan informasi tentang buku, seperti posisinya yang tepat di perpustakaan atau pengguna yang telah dikeluarkannya, dll.
Dalam kedua contoh ini, siswa dan buku di hash ke nomor unik.
Asumsikan bahwa Anda memiliki objek dan Anda ingin menetapkan kunci untuk mempermudah pencarian. Untuk menyimpan pasangan kunci / nilai, Anda dapat menggunakan larik sederhana seperti struktur data tempat kunci (bilangan bulat) dapat digunakan secara langsung sebagai indeks untuk menyimpan nilai. Namun, dalam kasus di mana kunci besar dan tidak dapat digunakan secara langsung sebagai indeks, Anda harus menggunakan hashing .
Dalam hashing, kunci besar dikonversi menjadi kunci kecil dengan menggunakan fungsi hash . Nilai-nilai ini kemudian disimpan dalam struktur data yang disebut tabel hash . Gagasan hashing adalah untuk mendistribusikan entri (pasangan kunci / nilai) secara seragam di seluruh array. Setiap elemen diberi kunci (kunci yang dikonversi). Dengan menggunakan kunci itu Anda dapat mengakses elemen dalam O (1) waktu. Menggunakan kunci, algoritma (fungsi hash) menghitung indeks yang menunjukkan di mana entri dapat ditemukan atau dimasukkan.
Hashing diimplementasikan dalam dua langkah:
- Elemen dikonversi menjadi integer dengan menggunakan fungsi hash. Elemen ini dapat digunakan sebagai indeks untuk menyimpan elemen asli, yang jatuh ke tabel hash.
- Elemen disimpan di tabel hash di mana ia dapat dengan cepat diambil menggunakan kunci hash.
hash = hashfunc (key)
index = hash% array_size
Dalam metode ini, hash tidak tergantung pada ukuran array dan kemudian dikurangi menjadi indeks (angka antara 0 dan array_size - 1) dengan menggunakan operator modulo (%).
Fungsi hash kriptografi memang dirancang untuk mencegah mengembalikan checksum yang sudah di hash kembali ke teks asli. Namun, meskipun hampir tidak mungkin dibalik, itu bukan berarti nilai hash 100% dijamin aman.
Seperti sekarang banyak software yang memungkinkan untuk menterjemahkan kembali fungsi hash, seperti Rainbow Table yang dapat digunakan untuk mengcrack plaintext checksum. Rainbow Table pada dasarnya adalah kamus yang mengeluarkan ribuan, jutaan, atau bahkan milyaran dari ini di samping nilai plainteks yang sesuai.
Di sini, dibutuhkan O (n) waktu (di mana n adalah jumlah string) untuk mengakses string tertentu. Ini menunjukkan bahwa fungsi hash bukan fungsi hash yang baik.
Mari kita coba fungsi hash yang berbeda. Indeks untuk string tertentu akan sama dengan jumlah nilai ASCII karakter dikalikan dengan urutan masing-masing dalam string setelah itu adalah modulo dengan 2069 (bilangan prima).
Fungsi String Hash Indeks
abcdef (97 1 + 98 2 + 99 3 + 100 4 + 101 5 + 102 6)% 2069 38
bcdefa (98 1 + 99 2 + 100 3 + 101 4 + 102 5 + 97 6)% 2069 23
cdefab (99 1 + 100 2 + 101 3 + 102 4 + 97 5 + 98 6)% 2069 14
defabc (100 1 + 101 2 + 102 3 + 97 4 + 98 5 + 99 6)% 2069 11
bcdefa (98 1 + 99 2 + 100 3 + 101 4 + 102 5 + 97 6)% 2069 23
cdefab (99 1 + 100 2 + 101 3 + 102 4 + 97 5 + 98 6)% 2069 14
defabc (100 1 + 101 2 + 102 3 + 97 4 + 98 5 + 99 6)% 2069 11
Tabel
Tabel hash adalah struktur data yang digunakan untuk menyimpan kunci / pasangan nilai. Tabel hash menggunakan fungsi hash untuk menghitung indeks ke dalam array di mana elemen akan dimasukkan atau dicari. Dengan menggunakan fungsi hash yang baik, hashing dapat bekerja dengan baik. Di bawah asumsi yang masuk akal, waktu rata-rata yang diperlukan untuk mencari elemen dalam tabel hash adalah O (1) .
Mari kita pertimbangkan string S. Anda harus menghitung frekuensi semua karakter dalam string ini.
string S = “ababcd”
Cara paling sederhana untuk melakukan ini adalah untuk mengulangi semua karakter yang mungkin dan menghitung frekuensi mereka satu per satu. Kompleksitas waktu dari pendekatan ini adalah O (26 * N) di mana N adalah ukuran string dan ada 26 karakter yang mungkin.
void countFre(string S)
{
for(char c = ‘a’;c <= ‘z’;++c)
{
int frequency = 0;
for(int i = 0;i < S.length();++i)
if(S[i] == c)
frequency++;
cout << c << ‘ ‘ << frequency << endl;
}
}
Hasil outputnya akan seperti ini :
a 2
b 2
c 1
d 1
e 0
f 0
…
z 0
Sumber referensi :











