Summary of Hashing Table and Binary Tree
Hash Table and Binary Tree
1. Hashing dan Hash Table
Hashing merupakan teknik yang digunakan untuk menyimpan dan mengambil key secara cepat. Dalam hashing, sebuah string diubah ke dalam value yang lebih kecil/pendek yang disebut key. Key sendiri merepresentasikan string tersebut. Dengan hashing, maka pengambilan elemen dalam database akan lebih cepat karena string sudah diubah ke dalam bentuk yang lebih pendek. Teknik hashing didefine dalam Hash Table dan menggunakan function yang disebut Hash Function.
Hash Table merupakan tabel (array) untuk menyimpan string asli. Indexnya disebut key, sedangkan stringnya adalah value. Contoh:
ada 5 string, yaitu "budi","caca","ella","andi",dan"farel". Dengan size hash table sebesar 26. Maka, hash function yang digunakan untuk memasukkan string-string tersebut ke dalam hash table adalah = ubah character pertama dari setiap string menjadi angka 0-25 (a=0, b=1, c=2, ...,z=25). Maka hash table yang terbentuk adalah:
Beberapa operasi yang dapat dilakukan di hash table adalah:
- insert: diberikan sebuah key dan nilai, insert nilai dalam tabel
- find: diberikan sebuah key, temukan nilai yang berhubungan dengan key
- remove: diberikan sebuah key,temukan nilai yang berhubungan dengan key, kemudian hapus nilai tersebut
- getIterator: mengambalikan iterator,yang memeriksa nilai satu demi satu
Selain itu, beberapa cara untuk mengubah string ke dalam key (hash function) adalah:
- Mid-square
- Division
- Folding
- Digit Extraction
- Rotating Hash
Setelah mengetahui tentang Hashing,hash table dan hash function, ada juga istilah "Collision" yaitu kejadian dimana record-record dalam hash table bertabrakan karena memiliki index/key yang sama.
Implementasi hashing table dalam blockchain
Dalam konteks cryptocurrency seperti bitcoin, transaksi diambil sebagai input dan dijalankan melalui algoritma hashing yang memberikan output dengan panjang tetap. Bitcoin menggunakan SHA(Secure Hashing Algorithm) -256. tidak peduli seberapa besar/kecil inputan, output akan selalu memiliki panjang 256-bit. Jadi, hash akan membantu kita untuk tidak perlu mengingat input daya yang bisa jadi besar.
contoh:
input = This is a test
Hash = C7BE1ED902FB8DD4D48997C6452F5D7E509FBCDBE2808B16BCF4EDCE4CO7D14E
input= Hi
Hash = 639EFCD08ABB273B1619E82E78C29A7DF02C1051B1820E99FC395DCAA3326B8
2. Binary Tree
Binary tree adalah tree yang setiap node nya memiliki jumlah maksimal anak yaitu 2. node yang tidak memiliki anak sama sekali disebut leaf.
Beberapa tipe binary tree:
- Perfect binary tree = adalah sebuah pohon biner penuh di mana semua daun memiliki kedalaman yang sama
- Complete binary tree = dapat didefinisikan juga sebagai sebuah pohon biner penuh di mana semua daunnya memiliki kedalaman n atau n-1 untuk beberapa n. Agar sebuah pohon dapat menjadi sebuah pohon biner lengkap, semua anak pada tingkat terakhir harus menempati titik terkiri secara teratur, dengan tidak ada titik yang menganggur di antara keduanya
- Skewed binary tree = binary tree yang setiap nodenya maksimal memiliki 1 anak
- Balanced binary tree = binary tree yang sub kiri dan kanannya memiliki ketinggian sama, atau maksimal berbeda 1 level.
Konsep binary tree dalam data structure dapat diimplementasikan dalam array maupun linked list.
referensi:
Comments
Post a Comment