Hash,Hashing Table,Binary tree

Nama : Sofyan Adrianto

NIM : 2301869121

Jurusan : TI Statistika

HASHING TABLE

Hash table merupakan salah satu struktur data yang digunakan dalam penyimpanan data sementara. Tujuan dari hash table adalah untuk mempercepat pencarian kembali dari banyak data yang disimpan. Hash table menggunakan suatu teknik penyimpanan sehingga waktu yang dibutuhkan untuk penambahan data (insertions), penghapusan data (deletions), dan pencarian data (searching) relatif sama dibanding struktur data atau algoritma yang lain.

Ide Dasar

Ide utama dari hashing adalah mengubah suatu string menjadi suatu bilangan dengan suatu fungsi. Misalkan kita memiliki string "abca", dan fungsi f yang memetakan string ke bilangan bulat berikut:

f(S) = (

(banyaknya 'a')*1 +

(banyaknya 'b')*2 +

(banyaknya 'c')*3 +

... +

(banyaknya 'z')*26

) mod 1000000

Artinya:

f("abca") = (2*1 + 1*2 + 1*3 + 0*4 + 0*5 + ... + 0*26) mod 1000000

= 7

Kita berhasil mengubah string "abca" menjadi sebuah angka, yaitu 7. Hal ini juga akan dilakukan untuk setiap nama mahasiswa dalam setiap operasi; sebelumnya di-hash terlebih dahulu. Dengan demikian, direct addressing table dapat kembali digunakan! Kini kompleksitas untuk setiap operasi adalah O(K), dengan K adalah kompleksitas menghitung nilai hash melalui fungsi hashing. Untuk contoh di atas, K = panjang string. Jika panjang setiap string cukup kecil, setiap operasi bisa dianggap O(1).

Hashing

Dapat diartikan sebagai aktivitas untuk mengubah suatu objek menjadi serangkaian angka/karakter/sejenisnya. Pada contoh sebelumnya, kita melakukan hash pada string menjadi bilangan.

Anda mungkin menyadari bahwa tabel T pada contoh sebelumnya bekerja seperti array. Kita seakan-akan dapat melakukan operasi:

T["Sofyan"] = 3;

printf("%d\n", T["Sofyan"]);

Pada ilmu komputer, tabel seperti ini disebut sebagai hash table. Struktur data ini erat kaitannya dengan konsep "key value". Key adalah hal yang menjadi indeks, dan value adalah nilai yang berasosiasi dengannya. Pada contoh permasalahan sebelumnya, nama mahasiswa merupakan key, dan IPK merupakan value.

Perhatikan bahwa key tidak harus berupa string. Tipe data apapun dapat didukung, asalkan didefinisikan fungsi hash-nya. Kalau untuk value, tentu saja datanya bisa bertipe apapun.

Operasi minimal yang perlu didukung oleh hash table adalah:

Diberikan key X dan value Y, catat bahwa value dari X adalah Y. Operasi ini dapat dianggap "T[X] = Y".

Diberikan key X, cari value-nya. Operasi ini dapat dianggap seperti mengakses "T[X]".

Kedua operasi ini akan saya sebut sebagai update dan read. Kompleksitas operasi-operasi ini adalah O(K), dengan O(K) adalah kompleksitas melakukan hash pada suatu key.

Fungsi Hashing

Pada bagian sebelumnya, saya memberi contoh fungsi hashing sederhana. Sebenarnya fungsi hashing itu bebas, terserah Anda ingin mendefinisikannya seperti apa. Namun, diharapkan fungsi hashing memiliki kriteria sebagai berikut:

Untuk dua buah key yang sama, hasil hashing-nya selalu sama.

Memiliki kompleksitas rendah.

Meminimalkan collision (akan dijelaskan pada bagian selanjutnya).

Pada kebanyakan kasus, kompleksitas fungsi hash dapat dianggap O(1). Sehingga operasi update dan read bekerja dalam O(1).

Hashing Table pada Blockchain

Secara sederhana, hashing berarti mengambil string input dengan panjang berapapun dan memberikan output dengan panjang tetap. Dalam konteks cryptocurrency seperti bitcoin, transaksi diambil sebagai input dan dijalankan melalui algoritma hashing (bitcoin menggunakan SHA-256) yang memberikan output dengan panjang tetap. 

Binary tree

Binary Tree atau Pohon Biner adalah sebuah pohon dalam struktur data yang bersifat hirarkis (hubungan one to many). Tree bisa didefenisikan sebagai kumpulan simpul dengan setiap simpul mempunyai paling banyak dua anak. Secara khusus, anaknya dinamakan kiri dan kanan. Binary tree tidak memiliki lebih dari tiga level dari Root.

Binary tree adalah suatu tree dengan syarat bahawa tiap node (simpul) hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Tiap node dalam binary treee boleh memiliki paling banyak dua child (anak simpul), secara khusus anaknya  dinamakan kiri dan kanan.

Konsep tree:

Root : Node di paling atas

Edge: Garis yang menghubungkan parent dengan child

Leaf: node yang tidak mempunyai anak

Siblings: node yang mempnyai parent yang sama

Degree: total subtree dari sebuah node

Height/depth: maksimum degree dari sebuah tree

jika ada garis yang menghubungkan a kepada b, a disebut ancestor dari b dan b adalah descendant dari a.

Jenis-jenis Binary Tree

1. Full Binary Tree, yaitu Binary Tree yang tiap nodenya ( kecuali leaf) memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama.
2. Complete Binary Tree, Mirip dengan Full Binary Tree, namun tiap subtree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child.
3. Skewed Binar Tree, Yakni Binary Tree yang semua nodenya(kecuali leaf) hanya memiliki satu child.

Binary Search Tree Adalah binary tree dengan sifat bahwa semua left child harus lebih kecil dari right child dan parentnya. Juga semua right child harus lebih besar dari left child serteparentnya. Binary search tree dibuat untuk mengatasi kelemahan pada binary tree biasa, yaitu kesulitan dalam searching / pencarian node tertentu dalam binary tree.  Pada dasarnya, operasi dalam binary search tree dama dengan binary tree biasa, kecuali pada operasi insert, update, dan delete.

1. Operasi insert, Pada binary search tree, insert dilakukan setelah ditemukan lokasi yang tepat. (loksi tidak ditemukan oleh user sendiri )
2. Operasi search, Seperti pada binary tree, biasa, namun disini. Update akan berpengaruh pada posisi node tersebut selanjutnya. Bila setelah diupdate mengakibatkan tree tersebut bukan binary  search tree lagi, maka harus dilakuakn perubahan pada tree dengan melakukan perubahan rotasi supaya tetap menjadi binary  seacrh tree.
3. Operasi Delete, Seperti halnya update, delete dalam binary search tree juga turut mempengaruhi struktur dati tree tersebut. Pada operasi delete, diakukan terhadap node dengan 2 child, maka untuk menggantikannya, diambil node paling kiri dari right subtree.