GSLC - Hashing

1. Hashing

Hashing adalah sebuah metode dimana kita bisa menyimpan dan mengambil sebuah data atau kunci dengan cepat, biasanya kita menemukan sebuah string yang digunakan untuk metode tersebut dalam sebuah key yang pendek. Hashing juga bisa didefinisikan sebagai konsep distribusi kunci di dalam array yang kita sebut sebagai Has Table yang sudah ditentukan menggunakan fungsi bernama Hash function.

Contoh pengunaan Hash:

Sebagai contoh, kita membuah fungsi hash yang mengubah sebuah kode dalam alfabet dan mengubahnya menjadi sebuah bilangan bilat.

Misal String = ("AABBCC")
fungsi_Hash(String) = {
          (banyak'a')*1 + (banyak'b')*2 + (banyak'c') *3 + ... (banyak'z') * 26 } mod 1000000

jadi jika kita masukkan string kita yang tadi
fungsi_Hash(AABBCC) = {
          (2*1 + 2*2 + 3*2 + 0*4 + .. + 0*26) } mod 1000000 = 12

Di dalam pembelajaran Fungsi hash, ada beberapa sub topic bagaimana cara kita mengubah string menjadi sebuah kunci. Terdapat 5 cara yaitu:

1. Mid - square = Kita menggunakan cara ini jika kunci yang akan kita gunakan adalah sebuah string dan string tersebut harus di ubah ke sebuah angka. Pertama kita kuadratkan kuncinya lalu mengekstratkkan ke tengah bits 
2. Division = Kita membagi sebuah string menggunakan operasi modulus, sama seperti yang sudah diterapkan sebelumnya
3. Folding = Kita membagi sebuah string menjadi beberapa part lalu mengabungkannya menjadi 1 part untuk mendapatkan sebuah kunci hash
4. Digit Extraction = Kita mengunakan sebuah digit yang sudah diberikan sebagai dengan sebuah alamat
5. Rotation Hash = Kita mengunakan metode Division untuk mendapatkan codenya yang nantinya akan kita putar.

2. Collision

Terdapat 2 metode dalam Collision, 

a. Linear Probing

    Metode ini digunakan untuk mencari sebuah tempat yang kosong lalu menaruhkan sebuah string kedalamnya

b. Chaining

    Metode ini digunakan menaruh sebuah string kedalam tempat yang terhubung pada linked list

3. Tree

Tree adalah sebuah non-linear data struktur yang merepresentasikan sebuah sususan yang bertingkat-tingkat diantara objek data. Untuk menentukan Tree, diperlukan beberapa consep yaitu:

a. Node yang ada diatas disebut sebagai Roor

b. Garis yang menghubungkan induk kepada anak disebut Edge

c. Node yang tidak mempunyai sebuah anak disebut dengan Leaf

d. Node yang mempunyai induk yang sama disebut Sibling

e. Degree dalam sebuah Node adalah total sub Tree dari sebuah Node

f. Depth adalah maximum degree dari Nodes di dalam Tree

g. Jika ada sebuah garis yang menghubungkan p ke q, maka p disebut dengan ancestor dari q dan q adalah sebuah descendant dari p.

Referensi:
http://kupaskode.blogspot.com/2015/09/tentang-hashing.html
PPT Hash Binus