HASHING TABLE & TREE

Nama               : Jason

NIM                : 2301852953

HASHING TABLE & BINARY TREE

A.    HASHING TABLE

Hashing adalah transformasi string karakter menjadi nilai panjang tetap yang lebih pendek atau key yang mewakili string asli. Hashing sering kali digunakan dalam berbagai bidang kehidupan saat ini, contohnya dalam pengelolahan data base dari suatu universitas dimana setiap mahasiswa dan staffnya memiliki data ( profil ) diri masing-masing yang kemudian dilakukan proses Hashing untuk mempermudah pengelolahan seperti pencarian atau penggantian data dari data base yang sudah dimiliki oleh universitas tersebut.

Hash Table adalah sebuah struktur data yang terdiri atas sebuah table dan fungsi bertujuan untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah table.

Operasi Pada Hash Tabel

·         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

Beberapa method yang digunakan untuk membangun fungsi has:

·         Mid-square

·         Division (paling sering digunakan)

·         Folding

·         Digit extraction

·         Rotating hash

·                                   Struktur dan Fungsi pada Hast Tabel

Hash table menggunakan struktur data array asosiatif yang mengasosiasikan record dengan sebuah field kunci unik berupa bilangan (hash) yang merupakan representasi dari record tersebut. Misalnya, terdapat data berupa string yang hendak disimpan dalam sebuah hash table. String tersebut direpresentasikan dalam sebuah field kunci k.

Cara untuk mendapatkan field kunci ini sangatlah beragam, namun hasil akhirnya adalah sebuah bilangan hash yang digunakan untuk menentukan lokasi record. Bilangan hash ini dimasukan ke dalam hash function dan menghasilkan indeks lokasi record dalam tabel.

a.      k(x) = fungsi pembangkit field kunci (1)

b.     h(x) = hash function (2)

B.    BINARY TREE

Tree adalah struktur data non-linear yang mewakili hubungan hierarkis di antara objek data. Beberapa hubungan dalam tree dapat diamati dalam struktur direktori atau hierarki organisasi. Node pada tree tidak perlu disimpan secara berdekatan dan dapat disimpan di mana saja dan dihubungkan oleh pointer.

Tree memiliki elemen-elemen:

·         Node

·         Node paling atas disebut root

·         Node yang tidak memiliki children (anak) disebut leaf (daun)

·         Node yang memiliki parent yang sama disebut sibling

·         Degree (tingkat) dari suatu node merupakan total subtree dari node

·         Height/depth merupakan degree maximum dari node dalam tree

·         Jika terdapat suatu garis yang menghubungkan p ke q, maka p disebut ancestor (leluhur) dari q, dan q merupakan descendant (keturunan) dari p.

Binary Tree memiliki beberapa tipe yang salah satunya yaitu sebagai berikut:

·         Perfect Binary Tree ( semua node memiliki kedalaman level yang sama)

·         Complete Binary Tree ( semua node selain yang leaf terisi)

·         Skewed Binary Tree ( disaat dimana setiap node memiliki minimal satu anak)

·         Balanced Binary Tree ( disaat dimana setiap leaf tidak lebih jauh ke root dari pada leaf yang lainnya.