Hash tables dan binary tree adalah kedua jenis struktur data yang memiliki ciri khasnya masing-masing. Apa itu mereka? Bagaimana aplikasinya di dunia blockchain?
Hashing
Hashing adalah sebuah teknik untuk menyimpan dan mengambil informasi secepat mungkin. Hashing biasanya dipakai untuk melakukan pencarian secara optimal. Hashing dilakukan dengan menggunakan hash function. Hash function mengubah data menjadi nilai arbitrer (acak) yang disebut sebagai hash value. Terdapat 2 jenis hash function:
Program tersebut akan menampilkan keluaran yaitu "1068500645 622728166 4286329124". Keluaran tersebut merupakan hash value untuk string "Ayam", "Sapi", dan "Udang" secara berurutan.
Hash Table
Hash Table adalah sebuah struktur data yang menyimpan data secara assosiatif. Indeks dalam struktur data array biasanya berupa angka, sedangkan dalam hash table bisa berupa data apapun, yang dinamakan key. Sedangkan data yang diakses menggunakan key disebut sebagai value.
Hash table biasanya menggunakan di-wrap di dalam struktur data array. Non-cryptographic hash function digunakan untuk mengkonversikan key menjadi indeks array. Cryptographic hash function sebenarnya juga dapat digunakan dalam implementasi hash table, sehingga akan menghasilkan hash table dengan karakteristik yaitu jarang mengalami collision yang diakibatkan oleh hash function, namun tidak efisien waktu, yang diakibatkan oleh lambatnya kalkulasi cryptographic hash function.
Contoh implementasi hash table dengan non-cryptographic hash function menggunakan algoritma FNV-1a dalam bahasa pemrograman C:
Compile test: https://www.codiva.io/p/e4e0b9da-8f46-4dd5-876c-4febf413f3ee (HashTable.c)
Program tersebut akan menampilkan keluaran yaitu "pedas gurih", yang merupakan value dari key "makaroni" dan "pasta". Perhatikan key yang menjadi indeks pada array adalah string.
Ukuran hash table biasanya jauh lebih kecil dibandingkan kombinasi hash value yang dihasilkan oleh sebuah hash function. Hal tersebut mengakibatkan beberapa key dapat mengakses ruang yang sama di hash table, yang disebut sebagai collision. Mengapa bisa terjadi collision? Seberapa mungkin terjadi collision? Hal tersebut dijelaskan dalam teori probabilitas dalam matematika yang disebut sebagai birthday problem.
Untuk memitigasi efek dari birthday problem dalam implementasi hash table, maka hal-hal yang dapat dilakukan adalah:
Open Addressing
Open addressing adalah metode mencari indeks kosong dalam array dengan melakukan hashing ulang apabila slot yang sebelumnya sudah terisi. Jika pada akhirnya ditemukan indeks kosong, indeks kosong tersebut digunakan untuk menyimpan value. Pencarian dilakukan dengan linear probing atau quadratic probing.
Implementasi linear probing menggunakan rehashing dengan algoritma sebagai berikut:
Direct chaining yaitu menggunakan array of linked list, dibandingkan array dengan tipe data primitif sesuai dengan value. Setelah indeks diketahui, implementasi operasi seperti insersi, delesi, dan sebagainya sama persis seperti pada linked list pada umumnya. Hal ini dimaksudkan agar suatu indeks array dapat menyimpan lebih dari satu value. Linked list pada suatu indeks array of linked list akan semakin panjang seiring dengan collision yang terjadi. Node pada linked list menyimpan key dan value.
Contoh struktur dari array of linked list menggunakan doubly linked-list untuk menyimpan key dalam bentuk string dan value dalam bentuk int, dengan ukuran hash table sebanyak 10000 indeks dalam bahasa pemrograman C yaitu:
Compile test: https://www.codiva.io/p/e4e0b9da-8f46-4dd5-876c-4febf413f3ee (DCNode.c)
Tree
Tree adalah suatu struktur data yang memiliki hierarki. Dalam implementasinya, tree memiliki beberapa pointer yang menunjuk ke node lainnya. Tree yang setiap nodenya menunjuk ke dua node dinamakan binary tree. Di dalam struktur data tree, urutan data tidaklah penting. Jika membutuhkan urutan yang terurut, struktur data lainnya seperti array, linked list, stack, queue, dan sebagainya dapat digunakan.
Anatomi Tree
Binary Tree adalah tree yang setiap nodenya menunjuk ke paling banyak dua node. Jenis-jenis binary tree yaitu:
Hashing
Hashing adalah sebuah teknik untuk menyimpan dan mengambil informasi secepat mungkin. Hashing biasanya dipakai untuk melakukan pencarian secara optimal. Hashing dilakukan dengan menggunakan hash function. Hash function mengubah data menjadi nilai arbitrer (acak) yang disebut sebagai hash value. Terdapat 2 jenis hash function:
- Cryptographic Hash Function (CHF)
Cryptographic hash function adalah hash function yang didesain supaya aman. Cryptographic hash function memiliki ciri khas sebagai berikut: - Deterministik, artinya key yang sama selalu memiliki hash value yang sama.
- Searah, artinya hanya suatu key yang bisa mendapatkan suatu hash value.
- Cepat, artinya dapat menghasilkan hash value secara cepat.
- Avalanche effect, artinya perubahan key sedikit saja dapat mengakibatkan perubahan yang besar pada hash value.
- Collision-resistant, artinya tidak boleh ada dua atau lebih key yang menghasilkan hash value yang sama.
- Pre-image attack resistant, artinya tidak mungkin dilakukan pencarian key yang menghasilkan suatu hash value.
- Non-Cryptographic Hash Function
Non-cryptographic hash function adalah hash function yang didesain supaya cepat. Berbeda dengan cryptographic hash function, non-cryptographic hash function memiliki toleransi collision yang lebih tinggi, sebagai tradeoff kecepatan dengan keamanan. Non-cryptographic hash function biasanya yang digunakan untuk key hashing dalam struktur data hash tables. Contoh algoritma non-cryptographic hash function adalah modulo, mid-square, division, parity-bit, Djb2, FNV-1a, CRC32, dan sebagainya.
Compile test: https://www.codiva.io/p/e4e0b9da-8f46-4dd5-876c-4febf413f3ee (ContohHashing.c)
Program tersebut akan menampilkan keluaran yaitu "1068500645 622728166 4286329124". Keluaran tersebut merupakan hash value untuk string "Ayam", "Sapi", dan "Udang" secara berurutan.
Hash Table
Hash Table adalah sebuah struktur data yang menyimpan data secara assosiatif. Indeks dalam struktur data array biasanya berupa angka, sedangkan dalam hash table bisa berupa data apapun, yang dinamakan key. Sedangkan data yang diakses menggunakan key disebut sebagai value.
Hash table biasanya menggunakan di-wrap di dalam struktur data array. Non-cryptographic hash function digunakan untuk mengkonversikan key menjadi indeks array. Cryptographic hash function sebenarnya juga dapat digunakan dalam implementasi hash table, sehingga akan menghasilkan hash table dengan karakteristik yaitu jarang mengalami collision yang diakibatkan oleh hash function, namun tidak efisien waktu, yang diakibatkan oleh lambatnya kalkulasi cryptographic hash function.
Contoh implementasi hash table dengan non-cryptographic hash function menggunakan algoritma FNV-1a dalam bahasa pemrograman C:
Program tersebut akan menampilkan keluaran yaitu "pedas gurih", yang merupakan value dari key "makaroni" dan "pasta". Perhatikan key yang menjadi indeks pada array adalah string.
Ukuran hash table biasanya jauh lebih kecil dibandingkan kombinasi hash value yang dihasilkan oleh sebuah hash function. Hal tersebut mengakibatkan beberapa key dapat mengakses ruang yang sama di hash table, yang disebut sebagai collision. Mengapa bisa terjadi collision? Seberapa mungkin terjadi collision? Hal tersebut dijelaskan dalam teori probabilitas dalam matematika yang disebut sebagai birthday problem.
Birthday problem
Birthday problem adalah suatu problem dalam statistika, yaitu jika terdapat n orang secara acak, berapa kemungkinan diantara mereka tersebut memiliki ulang tahun yang sama? Di dalam satu tahun terdapat 365 hari. Dengan prinsip rumah burung (pigeonhole principle), dibutuhkan 366 orang (atau 367 orang dalam tahun kabisat) untuk mencapai probabilitas 100%. Prinsip rumah burung sendiri adalah prinsip dalam matematika yang menjelaskan, bahwa jika jumlah barang diisi lebih banyak daripada ruang yang tersedia (barang > ruang), maka terdapat dapat dipastikan terdapat setidaknya dua barang di dalam salah satu ruang tersebut.Di dalam kasus ini, yang menarik adalah hanya dibutuhkan 23 orang untuk mencapai kemungkinan 50% diantara orang-orang tersebut memiliki ulang tahun yang sama, dan 70 orang untuk mencapai kemungkinan 99.9% diantara orang-orang tersebut memiliki ulang tahun yang sama.
Untuk memitigasi efek dari birthday problem dalam implementasi hash table, maka hal-hal yang dapat dilakukan adalah:
- Menggunakan minimally perfect hash function (contohnya cryptographic hash function), sehingga menghilangkan tendensi suatu hash function memberikan hash value yang sama untuk key tertentu, yang pada akhirnya meningkatkan kemungkinan menempatkan key di ruang yang sama akibat ruang yang tersedia secara efektif berkurang.
- Memperbesar ukuran ruang (table size), sehingga mengurangi kemungkinan penempatan di ruang yang sama.
- Open addressing, yaitu dengan mencari ruang yang masih kosong. Pencarian ruang dilakukan dengan metode linear probing, quadratic probing, dan sebagainya.
- Direct chaining, yaitu mengimplementasikan array of linked list. Linked list dalam suatu indeks akan semakin panjang node-nya seiring dengan collision yang terjadi.
Open Addressing
Open addressing adalah metode mencari indeks kosong dalam array dengan melakukan hashing ulang apabila slot yang sebelumnya sudah terisi. Jika pada akhirnya ditemukan indeks kosong, indeks kosong tersebut digunakan untuk menyimpan value. Pencarian dilakukan dengan linear probing atau quadratic probing.
Implementasi linear probing menggunakan rehashing dengan algoritma sebagai berikut:
rehash(key) = (n+1) % tablesize
Sedangkan quadratic probing menggunakan rehashing dengan algoritma sebagai berikut:
rehash(key) = (n+k2) % tablesize
Dengan k adalah bilangan kuadrat.
Direct ChainingDirect chaining yaitu menggunakan array of linked list, dibandingkan array dengan tipe data primitif sesuai dengan value. Setelah indeks diketahui, implementasi operasi seperti insersi, delesi, dan sebagainya sama persis seperti pada linked list pada umumnya. Hal ini dimaksudkan agar suatu indeks array dapat menyimpan lebih dari satu value. Linked list pada suatu indeks array of linked list akan semakin panjang seiring dengan collision yang terjadi. Node pada linked list menyimpan key dan value.
Contoh struktur dari array of linked list menggunakan doubly linked-list untuk menyimpan key dalam bentuk string dan value dalam bentuk int, dengan ukuran hash table sebanyak 10000 indeks dalam bahasa pemrograman C yaitu:
Tree
Tree adalah suatu struktur data yang memiliki hierarki. Dalam implementasinya, tree memiliki beberapa pointer yang menunjuk ke node lainnya. Tree yang setiap nodenya menunjuk ke dua node dinamakan binary tree. Di dalam struktur data tree, urutan data tidaklah penting. Jika membutuhkan urutan yang terurut, struktur data lainnya seperti array, linked list, stack, queue, dan sebagainya dapat digunakan.
Anatomi Tree
- Parent node adalah node yang memiliki kedudukan yang lebih tinggi daripada child node.
- Root adalah node yang tidak memiliki parent node. Hanya boleh ada satu root di dalam sebuah tree.
- Edge adalah hubungan antara node ke node lainnya.
- Node yang tidak memiliki child node dinamakan leaf node.
- Node yang bersebelahan dan memiliki parent node yang sama dinamakan siblings.
- Suatu node X adalah keturunan dari node Y lainnya apabila terdapat jalan untuk menuju node X dari node Y. Pada tree di atas, C, G, K adalah ancestor dari root.
- Setiap node memiliki kedudukan (level). Pada tree di atas, Root node (A) memiliki level 0, node B, C, D berada pada level 1, dan seterusnya.
Binary Tree adalah tree yang setiap nodenya menunjuk ke paling banyak dua node. Jenis-jenis binary tree yaitu:
- Generic Binary Tree
Generic Binary Tree adalah suatu tree yang memiliki maksimal dua buah child. Binary tree jenis ini hanya sekedar memenuhi definisi dari binary tree. Tree yang kosong juga dapat dikatakan sebagai generic binary tree.
- Strict Binary Tree
Strict Binary Tree adalah binary tree yang memiliki tidak ada atau dua node child. Dengan kata lain, suatu tree yang nodenya hanya memiliki satu child bukanlah strict binary tree.
- Full Binary Tree
Full Binary Tree adalah binary tree yang setiap node hanya memiliki dua buah child node dan semua leaf nodenya berada di level yang sama.
- Complete Binary Tree
Complete Binary Tree adalah binary tree yang setiap levelnya memiliki dua buah child node, kecuali level terakhir, dan seluruh node level terakhir harus berada di sebelah kiri.
Comments
Post a Comment