Hashing and Hash Tables

Hashing

Hashing merupakan teknik untuk menyimpan dan mengambil key dengan cara yang cepat.

Dalam Hashing, string karakter akan diubah value yang lebih pendek, atau menjadi sebuah key yang merepresentasikan string yang asli.

Hashing juga dilakukan untuk mengambil data dari suatu database yang besar, karena mencari data yang diinginkan lebih mudah dengan menggunakan key daripada mencarinya menggunakan valuenya yang asli.

Hashing juga dapat didefinisikan sebagai konsep dari mendistribusikan key-key dalam suatu array yang disebut hash table menggunakan fungsi yang sudah ditentukan sebelumnya yang disebut hash function

Hash Table

Hash Table adalah tabel ( array ) dimana kita menyimpan string yang asli.

Contoh :

Kita mau menyimpan 5 string : define, float, exp, char, atan menjadi hash table berukuran 26. Hash function yang akan kita gunakan adalah "transform the first character of each string into a number between 0..25" ( a --> 0, b --> 1, c --> 2, ..., z --> 25)

Berikut adalah tabel dari permasalahan tersebut :

h[ ]	Value
0	atan
1
2	char
3	define
4	exp
5	float
6
…
25

    

atan disimpan di h[0] karena a adalah 0

char disimpan di h[2] karena c adalah 2

define disimpan di h[3] karena d adalah 3

dan seterusnya

kita hanya mengambil karakter pertama dari masing2 string

Hash Function

Ada banyak cara untuk meng-hash string menjadi sebuah key. Berikut adalah beberapa metode yang penting untuk membuat hash function.

• Mid-square
• Division ( ini merupakan fungsi yang paling umum)
• Folding
• Digit Extraction
• Rotating Hash

1. Mid-square

Kalikan kuadrat string / identifier lalu gunakan bits di tengah2 hasil perkalian kuadrat yang tepat untuk mendapatkan hash-key

Apabila keynya merupakan string, ubahlah ke angka

Langkah-langkah : 

1. Kalikan Kuadrat nilai dari key (k x k)
2. Keluarkan bits tengah dari hasil perkalian di langkah 1

Function : h(k) = s

k = key

s = hash key yang didapatkan melalui memilih bits tengah dari k2

  2. Division

Bagi string / identifier dengan operator modulus. Ini merupakan metode yang paling sederhana untuk meng-hash integer x

  3. Folding

Partisikan string / identifier menjadi beberapa bagian, lalu sambungkan bagian-bagian itu untuk mendapatkan hash key-nya

  1. Divide the key value into a number of parts

  2. Add the individual part (usually the last carry is ignored)

  4. Digit Extraction

Digit tertentu dari angka yang sudah diberikan akan dianggap sebagai hash address

Contoh : 

x = 14,568

Apabila kita extract digit ke-1, 3, dan 5, kita akan mendapatkan hash code 158

  5. Rotating Hash

Gunakan method hash apapun ( seperti division atau mid-square )

Setelah mendapatkan hash code atau alamat dari hash method, lakukan rotasi

Rotasi dilakukan dengan menggeser digit-digit untuk mendapatkan hash address yang baru

Contoh :
hash address : 20021

hasil rotasi    : 12002 (digit-digit tersebut difold)

Collision

Apabila kita memilikki hash function : define, float, exp, char, atan, ceil, acos, floor.

Collision terjadi apabila ada beberapa string yang memilikki hash-key yang sama 

Ada beberapa string yang memilikki hash-key yang sama, seperti : atan, acos, char, ceil, float, floor.

Ada 2 cara yang dapat kita lakukan : 

  1. Linear Probing

h[ ]	Value
0	atan
1	acos
2	char
3	define
4	exp
5	float
6	ceil
7	floor

Ini merupakan hash-table dari string-string tersebut, ceil diletakkan di h[6] dan floor diletakkan di h[7] karena char sudah ada di h[2] dan float sudah ada di h[5], maka ceil dan floor diletakkan di slot yang kosong

h[ ]	Value	Step
0	atan	1
1	acos	2
2	char	1
3	define	1
4	exp	1
5	float	1
6	ceil	5
7	floor	3

Linear probing tidak efektif apabila banyak collision yang terjadi, tabel di atas (step) menunjukan berapa looping yang diperlukan untuk mencari string tersebut

  2. Chaining

0	atan --> acos
1	NULL
2	char --> ceil
3	define
4	exp
5	float --> floor
6	NULL
7	NULL

Dalam chaining, kita menyimpan setiap string di linked list, jadi apabila ada collision, kita hanya peru mengulang di chain itu

Rangkuman Materi Data Structures Sesi 6 (Stack and Queue)

Stack and Queue

1. Stack
Stack adalah Data Structure dengan elemen yang disimpan secara berurutan (ditumpuk).

Analogi :

Contohnya kita menaruh tumpukan piring dalam satu kontainer, pasti akan ada suatu saat kontainer itu penuh dan tidak dapat ditambahkan piring yang lain. Untuk mengubah komponen dari kontainer itu, kita dapat menambahkan atau mengganti piring yang paling atas dengan piring yang lain. AKAN TETAPI proses pengubahan komponen itu hanya dapat kita lakukan di piring yang paling atas

Gambar di atas merupakan representasi dari Stack

Kita juga dapat mengrepresentasikan Stack dengan Array.

Stack dalam Array memiliki 2 variabel : TOP & MAX

TOP : Posisi elemen terakhir dari suatu Stack. Apabila TOP = NULL, stack dikatakan kosong.

MAX : Ini merupakan batas penambahan elemen array dari suatu stack

Berdasarkan gambar di atas

MAX (batas penambahan elemen) dari stack tersebut adalah 8.

TOP (posisi elemen terakhir) dari stack tersebut adalah 4, dimana penambahan dan pengurangan elemen akan terjadi.

Stack juga dapat direpresentasikan dengan Linked List. Metode ini lebih sulit daripada Array, namun lebih efektif, karena dengan metode Array, kita harus mendeklarasikan ukurannya yang tetap.

Dalam Linked List Stack, setiap node memilikki 2 bagian ; Bagian yang menyimpan data, dan bagian yang menyimpan alamat ke node berikutnya

Pointer START dari linked list akan digunakan sebagai TOP, dan semua proses penambahan dan pengurangan  elemen akan dilakukan disini.

Stack Operations

Ada juga Stack Operations, yang merupakan fungsi-fungsi dalam memanipulasi Stack.

1. push(x) : menambahkan elemen x ke TOP dari suatu Stack

2. pop()    : menghapus elemen dari TOP dalam suatu Stack

3. top()     : menyatakan elemen di urutan tertentu sebagai TOP

Untuk lebih jelasnya, dapat dilihat dari gambar berikut

2. Queue

Perbedaan utama antara Stack dan Queue adalah : Elemen yang keluar.

Dalam Stack diterapkan sistem First In Last Out (FILO), yang artinya data yang pertama kali masuk ke dalam stack akan menjadi data yang terakhir untuk keluar.

Sedangkan dalam Queue diterapkan sistem First In First Out(FIFO), yang artinya data yang pertama kali masuk ke dalam queue juga akan menjadi data yang pertama kali keluar dari queue.

Analogi sederhananya bisa dilihat dari orang yang mengantri untuk ke bus (masuk ke tempat menunggu bus), orang yang berada di paling depan barisan akan menjadi yang pertama untuk masuk ke dalam bus (meninggalkan tempat menunggu bus).

Variabel dalam Stack terdiri atas TOP dan MAX, sedangkan variabel dalam Queue terdiri atas Front dan Rear

Dalam Linked List, pointer START akan digunakan sebagai Front.

Penambahan akan dilakukan di Rear.

Penghapusan akan dilakukan di Front.

Apabila FRONT = END = NULL, queue dapat dikatakan kosong.

Queue Operations

1. push(x) : untuk menambahkan sebuah elemen ke Rear dari Queue.

2. pop() : untuk menghilangkan sebuah elemen di Front dari Queue.

3. front() : fungsi ini mirip dengan fungsi top() dari Stack, yaitu untuk menyatakan elemen di urutan tertentu sebagai Front.

Berikut adalah contoh penggunaan Queue Operation dalam suatu Queue (Front = L ; Rear = R).

Kita juga dapat melakukan Circular Queue. Apa itu Circular Queue?

Bayangkan kasus dimana kita terus melakukan pop push, index array akan terlampaui sehingga data baru akan disimpan di luar jangkauan array, yang merupakan cara yang tidak efektif.

Untuk mengatasi ini, kita dapat melakukan Circular Queue, dalam Circular Queue, apabila R sudah mencapai index array yang terakhir, kita akan mengubah R menjadi index 0, lakukan hal yang sama terhadap L.

Gambar di bawah merupakan representasi dari Circular Queue

Terima Kasih.