Hashing didefinisikan sebagai proses menetapkan nilai numerik ke string alfanumerik dengan terlebih dahulu mengubahnya menjadi nilai numerik lain dan menyimpannya dalam tabel yang diindeks untuk membuat pengambilan data lebih cepat dan/atau menutupi data untuk enkripsi, yang dilakukan oleh fungsi hash.
Apa itu Hashing?
Hashing adalah proses menetapkan nilai numerik ke string alfanumerik dengan terlebih dahulu mengubahnya menjadi nilai numerik lain dan menyimpannya dalam tabel yang diindeks untuk membuat pengambilan data lebih cepat dan/atau menutupi data untuk enkripsi, yang dilakukan oleh fungsi hash.
Hashing digunakan untuk mengubah kunci atau string karakter menjadi nilai lain. Hal ini sering direfleksikan oleh nilai atau variabel dengan panjang tetap yang lebih kecil yang mencerminkan string asli dan membuatnya lebih mudah untuk ditemukan atau digunakan.
Penggunaan hashing yang paling umum adalah pembuatan tabel hash. Tabel hash menyimpan pasangan kunci-nilai dalam koleksi yang dapat diakses oleh indeksnya. Mengingat pasangan kunci-nilai tidak terbatas, fungsi hash dapat mencocokkan nilai dengan ukuran tabel. Nilai hash kemudian digunakan sebagai pointer untuk elemen tertentu.
Fungsi hash menciptakan nilai baru berdasarkan teknik hashing matematis, sering disebut nilai hash atau hash. Hash yang baik selalu menggunakan teknik hashing satu arah untuk menghindari konversi hash ke kunci asli.
Hashing berlaku untuk pencarian dan pengambilan data, tanda tangan digital, keamanan siber, dan kriptografi, di antara banyak aplikasi lainnya.
Mengapa hashing diperlukan?
Jumlah data di internet meningkat secara eksponensial, dan menjaga data ini secara efektif selalu menjadi tantangan. Kuantitas data ini mungkin tidak terlalu besar untuk pemrograman rutin. Namun, itu tetap harus disimpan, diambil, dan diproses dengan mudah dan efisien. Model data array adalah struktur data yang relatif sering digunakan untuk tujuan ini.
Kumpulan hal-hal yang disimpan di wilayah memori yang berdekatan merupakan sebuah array. Tujuannya adalah untuk mengelompokkan beberapa entri yang termasuk dalam satu kategori.
Jadi muncul pertanyaan tentang mengapa struktur data baru diperlukan jika model data array sudah ada! Pertanyaan ini dijawab dengan istilah ‘efisiensi.’ Meskipun menyimpan dalam array membutuhkan O(1) waktu, mencari di dalamnya membutuhkan setidaknya O(log n) waktu.
O(1) menunjukkan waktu konstan, yang menunjukkan bahwa algoritma waktu konstan akan selalu berjalan untuk jumlah waktu yang sama. Kompleksitas waktu konstan menjelaskan algoritma yang waktu eksekusinya tidak bergantung pada jumlah input. Sebaliknya, waktu O(log n) menunjukkan bahwa jumlah total operasi meningkat perlahan seiring bertambahnya panjang input. Ini berarti bahwa waktu meningkat secara linier sementara ‘n’ tumbuh secara eksponensial.
O(log n) tampaknya lebih sedikit, namun dengan kumpulan data yang besar dapat menimbulkan banyak masalah, membuat model data array menjadi tidak efisien.
Mencari model data yang dapat menyimpan data dan melakukan pencarian dalam waktu konstan, atau waktu O(1), diperlukan. Inilah mengapa struktur data hashing diperkenalkan. Dengan pengembangan model data hash, sekarang dimungkinkan untuk menyimpan dan mengambil informasi secara terus-menerus dengan relatif mudah.
Apa itu struktur data hash?
Arsitektur hash adalah model data tabular untuk menyimpan data secara asosiatif. Data disimpan dalam format array di dalam tabel. Namun, tidak seperti array pada umumnya, setiap elemen data diberi nomor indeks yang unik. Begitu kita memiliki indeks data yang dibutuhkan, akses informasi menjadi sangat cepat.
Dengan demikian, ini berkembang menjadi model data di mana tindakan penambahan dan pengambilan cepat terlepas dari ukuran datanya. Itu menggunakan array, seperti fasilitas penyimpanan, dan menggunakan algoritma hashing untuk membangun indeks untuk memasukkan atau menemukan elemen.
Misalnya, jika nilai kuncinya adalah Jane dan isinya adalah nomor telepon, kami meneruskannya sebagai berikut saat memberikan nilai kunci ke fungsi hash:
Hash(key) = index;
Saat kami memproses kunci melalui fungsi hash, itu menghasilkan indeks.
Hash(Jane) = 2461;
Contoh di atas menambahkan kunci, Jane, pada indeks 2461.
Seluruh proses hashing bekerja menggunakan tiga komponen:
– Key: Key dapat berupa teks atau angka apa pun yang diberikan sebagai input ke fungsi hash, yang menentukan indeks item atau posisi penyimpanan dalam struktur data. Dalam skenario ini, Jane adalah kuncinya.
– Hash Function: Hash Function menerima kunci sebagai input dan menghasilkan indeks komponen dalam array yang dikenal sebagai tabel hash. Indeks ini disebut sebagai indeks hash.
– Hash Table: Hash Table mengacu pada model data yang menghubungkan kunci ke nilai melalui fungsi hash. Hash menyimpan data secara asosiatif dalam array dengan indeks unik untuk setiap nilai data.
Untuk apa hashing digunakan?
Hashing memiliki beberapa aplikasi utama, seperti:
1. Hashing dalam keamanan siber
Hashing digunakan oleh beberapa teknik enkripsi untuk meningkatkan keamanan siber. Tanpa kunci dekripsi, peretas tidak dapat menginterpretasikan pesan dan input yang di-hash. Misalnya, jika peretas mengakses basis data dan menemukan informasi seperti ‘Jane Doe, Nomor telepon 2461’, mereka dapat langsung menggunakannya untuk tujuan jahat. Nilai hash seperti ‘b4gh8’ tidak ada artinya bagi pelaku ancaman tanpa kunci dekripsi. Karenanya, hashing melindungi kata sandi yang disimpan dalam database.
2. Hashing untuk operasi data yang lebih cepat
Hashing adalah pemetaan data objek ke nilai representasi menggunakan fungsi atau algoritma. Hash dapat digunakan untuk membatasi pencarian saat mencari objek ini di peta data objek. Ini secara signifikan mempercepat proses data. Misalnya, dengan tabel hash, pemrogram menyimpan data sebagai pasangan kunci-nilai, seperti catatan pelanggan. Kuncinya mengidentifikasi data dan fungsi seperti input, sedangkan kode hash atau bilangan bulat dipetakan untuk menghasilkan output.
3. Hashing dalam kriptografi
Untuk melindungi data, ilmu kriptografi menggunakan banyak algoritma hash. Algoritme hash aman (SHA), misalnya, adalah teknik tipikal yang digunakan untuk menghasilkan intisari pesan 160-bit (replika numerik berukuran tetap dari substansi pesan). SHA-2 digunakan untuk menghasilkan intisari pesan yang lebih besar (224 bit). SHA-3 adalah penerus SHA-2, dan semua algoritme ini dibangun di atas hashing.
4. Hashing dalam tanda tangan digital
Salah satu komponen mendasar dari sistem tanda tangan digital adalah hashing. Fungsi hash dapat digunakan dengan enkripsi untuk menawarkan nilai hash (message digest), yang berfungsi sebagai sidik jari digital yang berbeda. Ini menunjukkan bahwa setiap modifikasi pada input data akan menghasilkan hasil yang sama sekali berbeda (nilai hash). Akibatnya, ini membantu dalam memvalidasi sertifikat digital dan sumbernya.
5. Hashing dalam cryptocurrency
Penambangan Bitcoin menggunakan fungsi hash SHA-256 ganda. Ketika sebuah transaksi telah selesai, node blockchain tertentu diberi dua nomor yang dipilih secara acak. Nonce, bilangan bulat 32-bit, disematkan terlebih dahulu. Ini membuat hash, atau nomor 256-bit, yang berisi informasi tentang instance, termasuk waktu, lokasi, dan penulis (disampaikan oleh). Sebelum menambahkan blok ke rantai, penambang harus membuat Proof-of-Work. Beginilah cara kerja Bitcoin.
Bagaimana Cara Kerja Hashing?
Untuk memahami bagaimana fungsi hashing, lihat contoh berikut. Asumsikan kita ingin menyimpan kumpulan string ‘ab,’ ‘cd,’ dan ‘efg’ dalam sebuah tabel.
Tujuan hashing, dalam hal ini, adalah untuk mencari atau memperbarui data yang terdapat dalam tabel dengan cepat dalam waktu O(1), dan urutan string dalam tabel tidak relevan. Kumpulan string yang ditentukan dapat berfungsi sebagai kunci, dan string itu sendiri akan berfungsi sebagai nilai kunci. Bagaimana kita menyimpan nilai yang cocok dengan kunci adalah pertanyaannya. Di sini, kami akan menggunakan rumus matematika sederhana: mod.
Mod adalah operasi komputasi yang menghitung sisa ketika satu input dibagi dengan yang lain. Misalnya, 14 mod 6 = 2. Dalam contoh kita, kita akan menggunakan mod sebagai algoritme untuk menghitung pasangan nilai kunci. Namun, algoritma dunia nyata menggunakan formula yang sangat kompleks yang sulit untuk didekode atau didekripsi.
– Kita tahu bahwa fungsi hash (yang merupakan rumus matematika) digunakan untuk mendapatkan nilai hash. Untuk formula kami, kami telah memilih mod.
– Jadi mari kita tetapkan ‘a’ = 1, ‘b’= 2, dll., untuk semua karakter alfabet.
Nilai numerik dengan penjumlahan semua karakter string dihitung sebagai berikut:
‘bc’ = 2 + 3 = 5
‘cd’ = 3 + 4 = 7
‘fh’ = 6 + 8 = 14
– Asumsikan sekarang kita memiliki tabel 6 sel untuk menampung string ini. Fungsi hash yang digunakan dalam contoh ini adalah jumlah digit dalam (kunci) mod 6 (ukuran tabel). Dengan menghitung total numerik dari setiap string dalam himpunan, dibagi dengan 6 untuk mendapatkan sisanya, kita dapat mengetahui posisi string dalam array.
– Kami kemudian menghitung lokasi tabel tempat kami akan menyimpan setiap nilai string:
‘ab’ adalah 5 mod 6 = 6
‘cd’ adalah 7 mod 6 = 1
‘fh’ adalah 14 mod 6 = 2
– Struktur data hash (yang berupa tabel) akan terlihat seperti ini:
Sekarang, bagaimana jika Anda harus menyimpan fg, bukan fh? Hashing akan berfungsi sebagai berikut:
6 + 7 = 13
Oleh karena itu, fg adalah 13 mod 6 = 1.
Namun, string cd sudah menempati 1 di tabel hashing. Skenario seperti itu dikenal sebagai tabrakan, yang dihasilkan dari fungsi algoritmik yang dipikirkan dengan buruk.
Bentrokan dalam kerja hashing?
Tabrakan atau bentrokan hash terjadi dalam ilmu komputer ketika dua bit data dalam tabel hash memiliki nilai hash yang sama. Meskipun algoritme hash dirancang agar tahan benturan, algoritme terkadang dapat menerjemahkan data yang berbeda ke hash yang sama. Alasan untuk ini adalah prinsip sarang merpati.
Prinsip sarang merpati menegaskan bahwa jika ‘n’ benda ditempatkan dalam wadah ‘m’ dan n lebih dari m, minimal satu wadah harus menampung lebih dari satu barang. Ini terkadang dapat menghasilkan hasil yang tidak terduga. Dengan asumsi bahwa populasi New York City lebih dari jumlah maksimum helai rambut yang dapat ada di kepala manusia, prinsip sarang merpati menetapkan bahwa setidaknya harus ada dua individu di London dengan jumlah helai rambut yang sama.
Pengguna dengan niat jahat mungkin menggunakan fenomena benturan hash untuk meniru, mengakses, atau mengubah data. Untuk mengatasi hal ini dan menjamin integritas hasil terenkripsi, pakar keamanan siber mungkin menyertakan nomor acak dalam algoritme hash. Teknik ini, yang dikenal sebagai ‘salting’, memastikan keluaran yang berbeda meskipun datanya serupa (seperti fg = 1 dan cd = 1 dalam contoh).
Jenis Hashing
Hashing dapat terdiri dari empat jenis berikut:
1. Trivial hashing
Informasi langsung diterjemahkan ke indeks di dalam tabel hash dalam hashing sepele, sering disebut pemetaan indeks. Pendekatan ini biasanya menggunakan fungsi hash identitas, yang menerjemahkan setiap data input ke dirinya sendiri. Dalam hal ini, kunci data digunakan sebagai indeks dalam tabel hash sementara nilai yang sesuai disimpan di posisi itu.
Algoritme hashing yang naif hanya akan menerjemahkan kunci ‘b’ ke indeks ‘2’ di tabel hash dan menyimpan nilai ‘apel’ di posisi itu.
Kesederhanaan hashing sepele adalah salah satu manfaat utamanya. Fungsi hash mudah dipahami dan diterapkan, dan mengambil data menggunakan kunci sangatlah mudah. Namun, itu juga memiliki batasan tertentu. Karena persyaratan bahwa panjang tabel hash tetap sama dengan jumlah kunci, itu dibatasi untuk digunakan dengan kumpulan data kecil. Selain itu, tabrakan tidak ditangani. Ini berarti bahwa jika dua kunci menerjemahkan ke indeks yang identik, salah satu nilai akan ditimpa.
2. Double hashing
Tabel hash menggunakan hashing ganda sebagai pendekatan resolusi tabrakan. Menggunakan dua fungsi hash membuat dua hasil hash yang berbeda untuk kunci tertentu. Fungsi hash pertama digunakan untuk menentukan nilai hash awal, sedangkan yang kedua digunakan untuk menentukan panjang langkah urutan probing (daftar periksa lokasi yang akan dilihat sebagai alternatif jika terjadi tabrakan).
Karena menggunakan dua fungsi hash untuk menghitung nilai hash dan ukuran langkah, hash ganda memberikan potensi tingkat tabrakan yang rendah. Ini berarti kemungkinan tabrakan lebih rendah dibandingkan dengan metode resolusi tabrakan lainnya.
Namun, hashing ganda memiliki beberapa kelemahan. Ini mengharuskan penggunaan dua algoritme hash, yang mungkin meningkatkan upaya komputasi operasi penyisipan dan pencarian. Kedua, untuk mendapatkan kecepatan yang sangat baik, diperlukan pemilihan fungsi hash yang sesuai. Tingkat tabrakan bisa terus menjadi besar jika algoritma hash dibangun dengan buruk.
3. Chained hashing
Chaining adalah strategi untuk mencegah tabrakan. Dengan hashing berantai, setiap slot dalam tabel hash berfungsi sebagai simpul utama untuk data, yang akan dimasukkan setelahnya. Konsekuensinya, jika node kosong, data ditambahkan ke root node. Sebaliknya, jika data sudah ada, data yang masuk dilampirkan atau disisipkan setelah node kepala yang ada. Dalam contoh kita, fg akan ditambahkan ke cd sebagai linked list atau ‘chain.’
4. Closed hashing
Hashing tertutup, sering disebut pengalamatan terbuka, adalah teknik yang digunakan untuk menyelesaikan tabrakan dalam tabel hash. Pendekatan ini menyelesaikan tabrakan hash dengan menjelajahi (atau memindai) posisi alternatif di dalam larik (urutan probe) hingga indeks target atau slot yang tidak digunakan ditemukan.
Probing ini dapat terjadi dalam bentuk:
– Probing linier, di mana interval antar probe biasanya ditentukan pada 1 unit.
– Probing kuadrat, di mana jarak antara probe bertambah secara kuadrat (sebagaimana digariskan oleh fungsi kuadrat).
– Pencirian ganda, di mana interval di antara probe ditentukan untuk setiap catatan tetapi dihitung menggunakan algoritme hash lain, seperti yang dibahas di atas.
Fungsi Hash
Fungsi hash adalah algoritma matematika yang mengompresi nilai input numerik. Panjang input ke fungsi hash fleksibel, sedangkan panjang output selalu tetap. Intisari pesan dan nilai hash adalah nilai yang dihasilkan oleh algoritma hash.
Beberapa fungsi hash yang khas adalah:
1. Metode pembagian
Misalkan seseorang memiliki tabel hash dengan ukuran ‘S’ dan ingin merekam pasangan (kunci, nilai) di dalamnya. Menurut pendekatan pembagian, fungsi hash akan menjadi H(k) = key mod N. N adalah bilangan bulat positif yang digunakan untuk menghitung nilai hash, yang harus lebih besar dari S. Terkadang, S diganti dengan N, seperti dalam kasus ini.
2. Metode pertengahan persegi
Perhitungan nilai hash membutuhkan dua langkah. Dengan pasangan (kunci, nilai), fungsi hash dihitung dengan menghitung kuadrat kunci, atau kunci*kunci. Kode kemudian memilih beberapa digit dari pusat bilangan bulat untuk menghasilkan nilai hash.
3. Metode pelipatan digital
Jenis fungsi hashing ini melibatkan dua langkah. Awalnya, kita mempartisi nilai kunci k dan membuat beberapa bagian: k1, k2, k3, k4, …, kn, di mana setiap bagian memiliki jumlah digit yang sama kecuali untuk bagian terakhir, yang mungkin menyertakan digit yang lebih pendek. Setelah ini, masing-masing komponen ditambahkan. Nilai hash ditentukan dengan mengabaikan carryover sebelumnya, jika ada.
4. Metode perkalian
Jenis fungsi ini memiliki beberapa langkah, tidak seperti tiga langkah pertama.
– Pilih nilai konstanta A sehingga 0 lebih kecil dari A dan lebih besar dari 1.
– Kalikan nilai kunci dengan A.
– Hitung (k*A) mod 1 untuk mendapatkan bagian pecahan atau desimal dari k*A.
– Kalikan hasil dari langkah sebelumnya dengan ukuran tabel hash, seperti M.
– Nilai hash dihasilkan dengan mengambil lantai (yaitu, nilai bilangan bulat lengkap, bukan desimal) dari hasil dari langkah 4.
Rumus untuk fungsi ini terlihat seperti ini: h(K) = lantai (M (kA mod 1)), dengan h(K) adalah kunci hash.
Hashing adalah salah satu konsep dasar yang menggerakkan kriptografi dan enkripsi saat ini. Itu ditemukan pada 1950-an ketika seorang insinyur IBM menyadari bahwa menempatkan semua data dalam keranjang tunggal yang diindeks akan membuat pencarian dan pengambilan lebih cepat. Saat ini, hashing adalah teknik yang digunakan oleh mesin telusur, layanan cloud, dan sebagian besar aplikasi konsumen dan perusahaan lainnya yang melibatkan operasi data
