Hashing and Tree

HASH TABLE DAN BINARY TREE

Hashing adalah teknik dalam struktur data, dimana teknik ini digunakan untuk menyimpan dan mengambil / mencari kata kunci dengan cepat dan efisien. Dalam hashing, string akan ditransformasikan menjadi sebuah kunci yang mewakili string aslinya. Hashing digunakan untuk mengindeks dan menemukan suatu value dengan kata kunci yang lebih pendek. Hashing dilakukan untuk menyimpan data, mencari data, menambah data, dan menghapus data dengan lebih efisien.

Hash Table adalah sebuah struktur data yang terdiri atas table dan fungsi yang digunakan untuk menyimpan / menaruh key value yang unik untuk setiap record (baris) menjadi angka (hash).

Contoh simplenya :

arr[ ]	value
0	algo
1	bahaha
2	cat
3	NULL
4	NULL
5	fly
6	go
…
25	zebra

algo terletak pada arr[0] karena dimulai dengan huruf ‘a’, dimana pemetaan array dimulai dari 0 untuk abjad ‘a’, 1 untuk abjad ‘b’, dst hinggal 25 untuk ‘z’

ada beberapa cara untuk melakukan hash pada sebuah sebuah string, yaitu :

1.      Mid-square -> teknik hashing dengan mengkuadratkan value dari string, kemudian diambik digit tengahnya dan dijadikan sebagai key value. Namun, dalam teknik ini ada batasannya, yaitu saat value yang dikuadratkan memiliki 6 digit, maka saat dikuadratkan akan mencapai 12 digit. Tentu saja ini akan mengakibatkan overflow pada int. Hal ini harus diurus, seperti dengan mengganti int menjadi long. Cara ini cukup efisien karena kemungkinan key value sama sangatlah rendah.

2.      Divison (paling sering digunakan) -> teknik hashing dengan memodulo nilai asli dengan jumlah lokasi memori yang tersedia. Rumusnya secara umum adalah h(k) = k mod m, dimana k merupakan  key nya dan m merupakan jumlah lokasi memori yang tersedia pada array. Metode ini sering kali menghasilkan nilai unik yang sama, sehingga diperlukan mekanisme khusus untuk menanganinya.

3.      Folding -> teknik hashing dengan memagi nilai kunci menjadi beberapa bagian dimana setiap bagiannya memiliki jumlah digit yang sama dengan alamat relative.

4.      Digit Extraction -> teknik hashing dengan menentukan digit dari angka yang diberikan sebagai hash address.

5.      Rotating hash

TREE

Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hirarkis. Tree bias didefinisikan sebagai kumpulan simpul node dengan satu elemen khusus yang disebut Root dan dnode lainnya.

Ada beberapa istilah dalam tree, yaitu sbb :

1.      Parent : Node yang berada 1 level diatas suatu node

2.      Child : Node yang berada 1 level dibawah suatu node

3.      Sibling : Node yang memiliki parent sama

4.      Root : Node khusus yang tidak memiliki node diatasnya

5.      Degree : Banyaknya child yang dimiliki oleh suatu node