Hashing & Binary Tree

Hashing

Hashing merupakan proses mengubah data yang berjumlah besar ke dalam tabel yang lebih kecil. Fungsi dari hashing adalah untuk mempercepat pencarian data, penambahan data, dan penghapusan data. 


Hal-hal yang perlu di perhatikan dalam pembuatan hash table adalah ukuran array (m), key value/nilai yang di dapat dari data (k), dan indeks yang dituju (h).



Hash Function

Hash function adalah fungsi hash yang diterapkan untuk menghasilkan sebuah integer (bilangan bulat) yang digunakan sebagai alamat dari alamat hash table.

Contoh-contoh hash function adalah :

• Mid-square
• Division
• Folding
• Digit Extraction
• Rotating Hash

Hash Table

Hash table adalah struktur data yang digunakan untuk menyimpan dan mengakses data berbentuk tabel.

Namun dalam pembuatan hash table dapat terjadi tabrakan atau dapat disebut collision. Collision berarti ada data yang memiliki hash index yang sama, padahal satu index array hanya dapat menyimpan satu buah data saja. Berikut cara untuk mengatasi terjadinya collision :

1. Closed Hashing (Open Addressing)

Closed hashing akan mencari alamat lain apabila alamat yang dituju sudah terisi oleh sebuah data. Pencarian alamat tersebut memiliki 3 cara yaitu :

• Linear Probing

Linear probing akan menggeser 1 indeks dari indeks sebelumnya hingga menemukan alamat yang belum terisi oleh data dengan rumus

(h+1) modulus m

• Quadratic Probing

Quadratic probing mencari alamat baru dengan perhitungan kuadratik yang kompleks. Untuk menggunakan quadratic probing kita dapat menentukan rumus yang akan digunakan.

• Double Hashing

Double hash mencari alamat dengan cara melakukan hash lagi hingga menemukan alamat yang belum terisi dengan data.

2. Open Hashing (Seperate Chaining)

Open hashing membuat tabel untuk proses hashing menjadi array of pointer yang masing-masing pointer diikuti oleh linked list. Chain 1 terletak pada array of pointer sedangkan chain 2 dan seterusnya akan berhubungan dengan chain 1 seperti rantai.

Binary Tree

Binary tree merupakan sebuah struktur data tree yang hanya mempunyai maksimal 2 cabang saja. Sifat bilangan biner pada binary tree selalu bernilai 0 atau 1 maka dari itu binary tree hanya mempunyai 2 cabang.

Jenis-jenis binary tree :

• Perfect Binary Tree
• Complete Binary Tree
• Skewed Binary Tree
• Balanced Binary Tree

Perfect Binary tree

Perfect binary tree merupakan binary tree yang mempunyai masing masing 2 child dan memiliki level yang sama rata.

Complete Binary Tree

Complete binary tree adalah binary tree yang setiap nodenya mempunyai 2 child dan harus mempunyai panjang path yang sama.

Skewed Binary Tree

Skewed binary tree adalah binary tree yang setiap nodenya hanya mempunyai 1 child (kecuali leaf)

Sekian penjelasan singkat dari hashing dan binary tree semoga dapat membantu.