Hashing adalah teknik yang digunakan untuk menyimpan dan mengambil keys dengan cepat.
Dalam hashing, sebuah string dirubah menjadi value yang lebih kecil atau key yang merepresentasikan string awalnya.
Metode Hashing digunakan untuk mengambil data dalam sebuah database karena lebih cepat untuk mengakses data menggunakan key daripada string originalnya.
Hashing sendiri dapat didefinisikan sebagai konsep mendistribusi key dalam sebuah array yang diberi nama Hash Table menggunakan fungsi yang disebut Hash Function.
Hash Table
Merupakan array untuk menyimpan string original. Index tabel merupakan hashed key, sedangkan isi index adalah string originalnya.
Ukuran hash table biasanya beberapa urutan lebih sedikit dibandingkan dari jumlah total string yang memungkinkan, jadi beberapa string bisa memiliki key yang sama.
Hash Function
Ada beberapa cara untuk meng-hash string menjadi key. Berikut adalah beberapa metode penting untuk membuat hash functions.
- Mid-Square
Metode ini dilakukan dengan cara mengkuadratkan string (dirubah menjadi integer terlebih dahulu) kemudian menggunakan beberapa bit dari tengah hasil kuadrat untuk mendapatkan hash keynya.
Fungsi : h(k) = s
k = key
s = hash key yang didapat dari r bit hasil k kuadrat.
Contoh :
- Division / Pembagian
Penentuan hash key dilakukan dengan membagi string menggunakan operator modulus (biasanya dibagi dengan size tablenya)
Fungsi ; h(z) = z mod M
z = key
M = nilai yang digunakan untuk membagi key
Contoh : Misalkan M = 12
hash key dari angka 30 adalah 6 (30 % 12 = 6)
hash key dari angka 40 adalah 4 (40 % 12 = 4)
- Folding / Lipatan
Metode yang memecah-mecah string menjadi beberapa bagian, kemudian menjumlahkan bagian-bagiannya untuk mendapatkan hash key
Contoh :
Jika suatu hash table hanya memiliki 100 lokasi penyimpanan, maka data hanya bisa disimpan pada lokasi yang memiliki 2 digit saja, oleh sebab itu string/data dipecah menjadi 2 digit
untuk key 5786 akan dipecah menjadi 57 + 86 yang menghasilkan 143, karena hanya dipakai 2 digit maka yang terpakai adalah 43.
untuk ke 12345 akan dipecah menjadi 12 + 34 + 5 yang menghasilkan 51, maka lokasinya menjadi 51,
- Digit Extraction
Penentuan lokasi hash dilakukan dengan cara menentukan digit-digit yang akan dijadikan sebagai alamat hash
Contoh :
Jika key = 235146
Digit yang akan diekstrak adalah digit ke 1, 4, 5, dan 6. Maka alamat hash key diatas adalah 2146.
- Rotating Hash
Gunakan metode fungsi hash manapun yang sudah diterangkan diatas, kemudian hasil hash address tersebut akan dilakukan rotasi.
Rotasi dilakukan dengan menggeser digit-digit untuk mendapatkan alamat hash baru
Contoh :
Hasil hash address = 20021
Hasil rotasi = 12002
Collision
Collision adalah hal yang terjadi ketika ada beberapa data yang memiliki hash key yang sama.
Untuk menyelesaikan masalah tersebut, ada 2 metode yang dapat dilakukan :
1. Linear Probing
Mencari slot array yang kosong untuk menempatkan string
Contoh :
2. Chaining
Meletakkan string didalam slot yang sama menggunakan linked list
Contoh :
Binary Tree
Binary Tree adalah struktur data yang menyerupai tree dimana tiap nodenya memiliki paling banyak dua children, yaitu left dan right. Node yang tidak memiliki children disebut leaf.
Jenis-jenis binary tree :
- Perfect Binary Tree : binary tree yang setiap tingkatnya memiliki kedalaman yang sama.
- Complete Binary Tree : binary tree yang pada tiap tingkatnya, kecuali yang paling terakhir terisi semua, semua nodenya terposisi paling kiri sebisanya. Perfect Binary Tree termasuk Complete Binary Tree.
- Skewed Binary Tree : binary tree yang tiap nodenya memiliki paling banyak 1 child. Secara tidak langsung, skewed tree akan membentuk relasi linked list biasa.
Penggunaan Binary Tree :
- Melakukan penghitungan operasi prefix dan postfix
- Melakukan searching dengan menggunakan BST (Binary Search Tree)
Aplikasi Hashing pada Blockchain
1. Industri Makanan
Saat ini banyak pusat perbelanjaan seperti Walmart bekerja sama dengan IBM untuk menggabungkan blockchain dalam sistem manajemen makanan mereka. Semakin banyak orang yang tidak memedulikan asal makanan mereka. Ini menyebabkan banyak masalah tidak hanya bagi konsumen tetapi juga pemasok.
2. Aplikasi Blockchain pada Cyber Security
Terdapat 3 fitur blockchain yang bisa membantu mencegah serangan keamanan cyber.
Fitur #1: Sistem yang Tidak Terpercaya
Sistem blockchain berjalan tanpa konsep ‘kepercayaan manusia’. Seperti pernah dituliskan Derin Cag dalam artikelnya yang berjudul Richtopia, “Ini mengasumsikan bahwa insider atau outsider dapat berkompromi dengan sistem kapanpun, karenanya ini bersifat bebas dari ‘etika manusia’.”
Fitur #2: Kekekalan
Blockchain membolehkan untuk menyimpan data dan mengamankannya menggunakan aturan kriptografi seperti digital signature dan hashing. Satu dari fitur terbaik adalah ketika data memasuki block dalam blockchain, data tidak bisa dirusak. Ini disebut ‘kekekalan’.
Fitur #3: Desentralisasi dan Konsensus
Blockchain adalah sistem terdistribusi yang bersifat desentralisasi. Blockchain terbuat dari banyak node. Untuk mengambil keputusan, mayoritas node harus mencapai konsensus dan mengambil keputusan. Sehingga, kita memiliki sistem demokrasi dan bukan figur otoritatif yang terpusat.
Untuk mempelajari lebih lanjut, dapat dilihat pada web berikut ini :
Tidak ada komentar:
Posting Komentar