Data Structure GSLC March 10th, 2020

Hashing and Hash Tables, Trees, & Binary Tree

1. Hashing and Hash Tables

Jadi, Hashing adalah metode untuk menyimpan dan mengambil kembali data dengan cepat karena dalam hashing, data yang disimpan diberikan kode (selanjutnya disebut key) yang lebih pendek dari data tersebut. Key tersebut bisa didapatkan dengan beberapa metode yang nanti akan dibahas selanjutnya pada laman ini. Nah, hashing ini digunakan karena akan lebih gampang untuk mengakses database saat ingin mencari data ketika kita menggunakan key dibandingkan nilai data yang asli. Hash table adalah array yang menyimpan key sebagai index dan value sebagai data asli. Hash function adalah fungsi yang mengubah data awal (string), menjadi key. Berikut adalah beberapa hash function yang umumnya dipakai:

A. Mid-Square

Jika datanya dalam bentuk string maka kita harus mengubahnya dahulu menjadi angka.

Berikut adalah langkah-langkahnya:

• pangkat 2 kan nilai dari key.
• Kemudian, ambil r bits tengah dari hasil pangkat 2 tadi.

Contohnya:

  Data      squared value     middle part

  3121         9740641              406

  3122         9746884              468

  3123         9753129              531

Dari hasil tersebut dapatlah key yang akan kita pakai

B. Division

Metode ini sering dipakai untuk menghash data berupa integer.

      Function: h(z) = z mod M

                          z  = key

                         M = the value using to divide the key, usually using a prime number
                                 the table size or the size of memory used.

contohnya: M=97 maka,

“COBB” would be stored at the location

  ( 64+3 + 64+15 + 64+2 + 64+2) % 97 = 88

“HIKE” would be stored at the location

  ( 64+8 + 64+9 + 64+11 + 64+5) % 97 = 2

“PPQQ” would be stored at the location

  ( 64+16 + 64+16 + 64+17 + 64+17) % 97 = 35

“ABCD” would be stored at the location

              ( 64+1 + 64+2 + 64+3 + 64+4) % 97 = 76 

C. Folding

Cara untuk metode ini cukup mudah, hanya dengan membagi key menjadi beberapa bagian (terserah) yang terdiri dari beberapa digit (terserah). Kemudian, bagian-bagian tersebut dijumlahkan hingga hash yang didapat muat dalam jangkauan hash table tersebut. 

Contohnya: hash tablenya ada 100 lokasi, keynya kita akan bagi ke beberapa bagian yang terdiri dari 2 digit.

    Key                           6789                     321                    34567

    Parts                     67 and 89            32 and 1           34, 56, and 7

    Sum                           156                       33                        97

    Hash value                 56                        33                        97

                            (ignore last carry)

D. Digit Extraction

Hash addressnya ditentukan oleh digit tertentu. Contohnya:

If we extract the 1st, 3rd, and 5th digit, we will get a hash code of : 158.

E. Rotating Hash

Hash key value dengan metode Mid-square atau Division, kemudian hasilnya di putar (rotasikan).

Contohnya:

– Given hash address = 20021

– Rotation result: 12002 (fold the digits)

F. Collision

Ketika kita menyimpan data, kemudian terjadi penindihan data maka ada 2 hal yang bisa kita lakukan yaitu, Linear probing dan Chaining.

Linear probing dilakukan dalam array. Lokasi alternatif bagi data yang memiliki key yang sama adalah menempatkannya di lokasi kosong terdekat.

Chaining adalah cara menggunakan linked list untuk menghubungkan data yang sudah ada terebih dahulu pada key tersebut dengan data yang baru yang memiliki key yang sama.

2. Tree & Binary Tree

Tree adalah Data Structure non-linear yang menunjukkan tingkat dari tiap data.

Contohnya pada gambar disamping, bisa kita lihat bahwa ada hubungan hierarki/ tingkatan antara tiap data dalam konteks ini, node.

Data yang berada di tingkatan yang paling atas(level 0), adalah akar. Sedangkan semua
sub-node yang bercabang dari sebuah node disebut child. Jumlah cabang dari sebuah node disebut degree. Jumlah degree maksimal sebuah node dalam tree disebut depth.

Binary Tree adalah tree yang tiap nodenya paling banyak memiliki 2 child. Node yang tidak memiliki child disebut leaf. Contohnya pada gambar disamping.

Binary Tree memiliki beberapa tipe, antara lain:
1. Perfect Binary tree. Binary tree yang tiap tingkatannya memiliki depth yang sama.

2. Complete Binary tree. Binary tree yang tiap levelnya terisi lengkap (2 node), namun pada level terakhir hanya ada child kiri dan child kanan tidak ada.
3. Skewed Binary tree. Binary tree yang tiap nodenya memiliki paling banyak 1 child.