Petani x Jagung: Hashing Table and Binary Tree

Pengertian Hash Table

Hash table dalam ilmu komputer merupakan sebuah struktur data yang digunakan untuk menyimpan data sementara. Hashing adalah teknik untuk melakukan penambahan, penghapusan dan pencarian dengan constant average time. Hashing digunakan untuk menyimpan data yang cukup besar pada abstract data type (ADT). Selain itu, hashing juga digunakan untuk mempercepat pencarian dalam tabel data atau pembandingan data seperti di dalam database, mencari kesamaan dan sebagainya.

Fungsi Hash

1. Mid square

Mid square adalah teknik hashing yang menghasilkan key unik. Teknik ini dapat mengambil nilai dan dapat dikuadratkan. Sehingga dapat menghasilkan key dengan keacakan tinggi jika mengambil nilai yang cukup besar. Untuk mendapatkan alamat relatif, nilai key dikuadratkan lalu beberapa digit diambil dari tengah.

Fungsi : h(k) = s

Contoh :

Key	Squared Value	Middle Part
3121	9740641	406
3122	9746884	468
3123	9753129	531

2. Division

Fungsi : h(z) = z mod M

Metode division sering menghasilkan nilai hash yang sama dari dua atau lebih nilai aslinya (bentrokan). Sehingga, dibutuhkan mekanisme khusus untuk menangani bentrokan tersebut yaitu dengan kebijakan resolusi bentrokan. Alamat relatif dari nilai key adalah sisa dari hasil pembagian nilai key dengan bilangan pembagi.

Contoh :

ABCD	(64 + 1 + 64 + 2 + 64 + 3 + 64 + 4) % 97	76
HIKE	( 64 + 8 + 64 + 9 + 64 + 11 + 64 + 5) % 97	2
PPQQ	( 64 + 16 + 64 +16 + 64 + 17 + 64 + 17) % 97	35
COBB	( 64 + 3 + 64 + 15 + 64 + 2 + 64 + 2) % 97	88

3. Folding

Folding dapat dipecah menjadi beberapa bagian, kemudian tiap bagian akan digabungkan lagi ke dalam bentuk yang lain untuk mendapatkan hash key.

Contoh :

Phone Number	3 Group	Index
5373737	53 + 73 + 737	863
5125858	51 + 25 + 858	934
5315151	53 + 15 + 151	219

4. Collision

Bila terjadi collision (tabrakan) akan diselesaikan dengan menggunakan collision resolution. Collision terjadi jika dua buah keys dipetakan pada sebuah sel. Ada 2 buah cara untuk menangai collision :

1) Linear Probing

Linear probing adalah salah satu cara untuk menemukan lokasi record yang tak dapat disimpan di home addressnya. Linear probing ini merupakan sebuah pencarian secara sequential (linear) dari home address sampai lokasi 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

2) Chaining

Chaining dapat mengakses synonym dengan fasilitas link list untuk record daam kelas ekivalen. Link list record dengan home address yang sama tidak akan mengurangi jumlah collision, melainkan akan mengurangi waktu akses untuk me-retrieve record yang tidak terdapat di home addressnya.

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

Implementasi Hashing Table Pada Block Chain

Implementasi hashing table pada block chain dapat menggunakan algoritma hashing SHA-256. Ini dapat memberikan bukti kriptografi untuk otentikasi dan integritas data. Fungsi hash kriptografi tersebut adalah untuk mengambil data dari blok sebelumnya dan mengubahnya menjadi compact string yang memungkinkan sistem mendeteksi adanya sabotase. Hash ini merupakan sebuah algoritma yang memetakan data secara acak ke dalam bentuk string yang berukuran tetap. Hash ini dirancang untuk dapat menjadi sebuah fungsi satu arah. Hash memungkinkan setiap blok dapat memverifikasi integritasnya sehingga setiap blok tidak perlu memiliki nomor seri.

Binary Tree

Dalam ilmu komputer, binary tree (bahasa Indonesia : pohon biner) adalah sebuah pohon dalam struktur data yang memiliki simpul paling banyak dua anak pada setiap simpulnya. Binary tree ini setiap nodenya memiliki paling banyak dua anak dan dinamakan dengan anak kiri dan anak kanan.

Node Pada Binary Tree

(Gambar : http://syafrinafarahdila.blogspot.com/2018/04/tree.html)

Tipe Binary Tree

1. Perfect Binary Tree

Perfect binary tree adalah sebuah binary tree yang semua daunnya memiliki kedalaman yang sama.

2. Complete Binary Tree

Complete binary tree adalah sebuah binary tree yang di mana semua daunnya memiliki kedalman n atau n-1 untuk beberapa n. Semua anak pada tingkat terakhir harus menempati titik paling kiri secara teratur dengan tidak ada titik yang menganggur di antara keduanya.