Hash Table and Binary Trees

Hashing

adalah proses menghasilkan data keluaran (output data) yang panjangnya tetap dan sama, dari data masukan (input data) yang panjangnya berbeda-beda. Hashing digunakan untuk mengindeks dan mengambil item dalam database karena lebih cepat menemukan item menggunakan kunci hash yang lebih pendek daripada menemukannya menggunakan nilai asli. Itu juga digunakan dalam banyak algoritma enkripsi.

Hash Table

sebuah struktur data yang terdiri atas sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel. Menyimpan data pada memori ke dalam baris-baris dan kolom-kolom sehingga membentuk table yang diakses dengan cepat.

Hash Function

 •       Mid-square

Mid-Square hashing adalah teknik hashing di mana kunci unik dihasilkan. Dalam teknik ini, nilai diambil dan dikuadratkan. Kemudian, beberapa digit dari tengah diekstraksi. Angka-angka yang diekstrak ini membentuk angka yang diambil sebagai nilai baru. Teknik ini dapat menghasilkan kunci dengan keacakan tinggi jika nilai yang cukup besar akan diambil.    •       Division (most common)

Jumlah lokasi memori yang tersedia dihitung, kemudian jumlah tersebut digunakan sebagai pembagi untuk membagi nilai yang asli dan menghasilkan sisa. Sisa tersebut adalah nilai hashnya. Secara umum, rumusnya h(k)= k mod m. Dalam hal ini m adalah jumlah lokasi memori yang tersedia pada array. Fungsi hash tersebut menempatkan record dengan kunci K pada suatu lokasi memori yang beralamat h(k). Metode ini sering menghasilkan nilai hash yang sama dari dua atau lebih nilai aslinya atau disebut dengan bentrokan. Karena itu, dibutuhkan mekanisme khusus untuk menangani bentrokan yang disebut kebijakan resolusi bentrokan.

Contoh: asumsikan ukuran tabel = 11 dan satu file dengan 8 record menggunakan nilai kunci sebagai berikut : 12,21,68.

Maka:

(12 mod 11) + 1 = 1 + 1 = 2 ; simpan 12 dilokasi 2

(21 mod 11) + 1 = 10 + 1 = 11 ; simpan 21 dilokasi 11

(68 mod 11) + 1 = 2 + 1 = 3 ; simpan 68 dilokasi 3

(38 mod 11) + 1 = 5 + 1 = 6 ; simpan 38 dilokasi 6

(52 mod 11) + 1 = 9 + 1 = 10 ; simpan 52 dilokasi 10

(70 mod 11) + 1 = 4 + 1 = 5 ; simpan 70 dilokasi 5

(44 mod 11) + 1 = 0 + 1 = 1 ; simpan 44 dilokasi 1

(18 mod 11) + 1 = 7 + 1 = 8 ; simpan 18 dilokasi 8

Sehingga :

Index 1 2 3 4 5 6 7 8 9 10 11

Nilai Key 44 12 68 – 70 38 – 18 52 – 21

 •       Folding

Untuk mendapatkan alamat relatif, nilai key dibagi menjadi beberapa bagian, setiap bagian (kecuali bagian terakhir) mempunyai jumlah digit yang sama dengan alamat relatif. Bagian-bagian ini kemudian dilipat (seperti kertas) dan dijumlah. Hasilnya, digit yang tertinggi dibuang (bila diperlukan).

Contoh : 

Kunci 123456, 234351, 222456, 321654, dilipat menjadi 2 bagian, setiap 3 digit.
Maka :
123+654 = 777 ; simpan 123456 dilokasi 777
234+153 = 387 ; simpan 234351 dilokasi 387
222+654 = 876 ; simpan 222456 dilokasi 876
321+456 = 777; simpan 321654 dilokasi 777
Dari perhitungan terjadi kolisi untuk nomor 123456 dan 321654.

•  Digit Extraction

Digit yang telah ditetapkan dari nomor yang diberikan dianggap sebagai alamat hash.

Contoh:

Misalkan x = 14.568

Jika kita mengekstrak digit pertama, ketiga, dan kelima, kita akan mendapatkan kode hash: 158.

•   Rotating Hash

Gunakan metode hash (seperti metode division atau Mid-Square). Setelah mendapatkan kode hash/alamat dari metode hash, lakukan rotasi. Rotasi dilakukan dengan menggeser digit untuk mendapatkan alamat hash baru.

Contoh:

Misal alamat hash = 20021

Hasil rotasi: 12002 (membalik angka)

Trees & Binary Tree

Following are the important terms with respect to tree :

·      Path − Path refers to the sequence of nodes along the edges of a tree.

·      Root − The node at the top of the tree is called root. There is only one root per tree and one path from the root node to any node.

·      Parent − Any node except the root node has one edge upward to a node called parent.

·      Child − The node below a given node connected by its edge downward is called its child node.

·      Leaf − The node which does not have any child node is called the leaf node.

·      Subtree − Subtree represents the descendants of a node.

·      Visiting − Visiting refers to checking the value of a node when control is on the node.

·      Traversing − Traversing means passing through nodes in a specific order.

·      Levels − Level of a node represents the generation of a node. If the root node is at level 0, then its next child node is at level 1, its grandchild is at level 2, and so on.

·      keys − Key represents a value of a node based on which a search operation is to be carried out for a node.

Binary Tree

Binary Tree atau Pohon Biner adalah sebuah pohon dalam struktur data yang bersifat hirarkis (hubungan one to many). Tree bisa didefenisikan sebagai kumpulan simpul dengan setiap simpul mempunyai paling banyak dua anak. Secara khusus, anaknya dinamakan kiri dan kanan. Binary tree tidak memiliki lebih dari tiga level dari Root.
Binary tree adalah suatu tree dengan syarat bahawa tiap node (simpul) hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Tiap node dalam binary treee boleh memiliki paling banyak dua child (anak simpul), secara khusus anaknya  dinamakan kiri dan kanan.
Pohon biner dapat juga disimpan sebagai struktur data implisit dalam array, dan jika pohon tersebut merupakan sebuah pohon biner lengkap, metode ini tidak boros tempat. Dalam penyusunan yang rapat ini, jika sebuah simpul memiliki indeks i, anaknya dapat ditemukan pada indeks ke-2i+1 dan 2i+2, meskipun ayahnya (jika ada) ditemukan pada indeks lantai ((i-1)/2) (asumsikan akarnya memiliki indeks kosong).

Sekian. Terimakasih

Source : https://www.beritabebas.com/definisi/hashing/

https://www.geeksforgeeks.org/mid-square-hashing/

https://arisistemberkas.blogspot.com/2018/10/teknik-hashing.html

https://www.tutorialspoint.com/data_structures_algorithms/tree_data_structure.htm