Hashing Table & Binary Tree

Hash Table

Hash Table adalah 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.

Keunggulan dari struktur hash table ini adalah waktu aksesnya yang cukup cepat, jika record yang dicari langsung berada pada angka hash lokasi penyimpanannya. Akan tetapi pada kenyataannya sering sekali ditemukan hash table yang record-recordnya mempunyai angka hash yang sama atau disebut dengan Collision (bertabrakan).
Collision berarti ada lebih dari satu data yang memiliki hash index yang sama, padahal seperti yang kita ketahui, satu alamat / satu index array hanya dapat menyimpan satu data saja.
Untuk meminimalkan collision gunakan hash function yang dapat mencapai seluruh indeks/alamat.

Berikut ini cara-cara yang digunakan untuk mengatasi collision :

1.   Closed hashing (Open Addressing)

Close hashing menyelesaikan collision dengan menggunakan memori yang masih ada tanpa menggunakan memori diluar array yang digunakan. Closed hashing mencari alamat lain apabila alamat yang akan dituju sudah terisi oleh data.
Kelemahan dari closed hashing adalah ukuran array yang disediakan harus lebih besar dari jumlah data. Selain itu dibutuhkan memori yang lebih besar untuk meminimalkan collision.

2.   Open hashing (Separate Chaining)

Pada dasarnya separate chaining membuat tabel yang digunakan untuk proses hashing menjadi sebuah array of pointer yang masing-masing pointernya diikuti oleh sebuah linked list, dengan chain (mata rantai) 1 terletak pada array of pointer, sedangkan chain 2 dan seterusnya berhubungan dengan chain 1 secara memanjang.
Kelemahan dari open hashing adalah bila data menumpuk pada satu/sedikit indeks sehingga terjadi linked list yang panjang.


Operasi Pada Hash Tabel

• insert: diberikan sebuah key dan nilai, insert nilai dalam tabel
• find: diberikan sebuah key, temukan nilai yang berhubungan dengan key
• remove: diberikan sebuah key,temukan nilai yang berhubungan dengan key, kemudian hapus nilai tersebut
• getIterator: mengambalikan iterator,yang memeriksa nilai satu demi satu

Binary Tree

Binary Tree adalah Sebuah binary tree adalah sebuah pengorganisasian secara hirarki dari beberapa buah simpul, dimana masing-masing simpul tidak mempunyai anak lebih dari 2. Simpul yang berada

di bawah sebuah simpul dinamakan anak dari simpul tersebut. Simpul yang berada di atas sebuah

simpul dinamakan induk dari simpul tersebut.

 Masing-masing simpul dalam binary tree terdiri dari tiga bagian yaitu sebuah data dan

dua buah pointer yang dinamakan pointer kiri dan kanan. Simpul juga mempunyai sibling,

descendants, dan ancestors. Sibling dari sebuah simpul adalah anak lain dari induk simpul

tersebut. Descendants dari sebuah simpul adalah semua simpul-simpul merupakan cabang

(berada di bawah) simpul tersebut. Anchestors dari sebuah simpul adalah semua simpul yang

berada di atas antara simpul tersebut dengan root. 

Dalam data structure, Binary Tree adalah  struktur data yang hampir mirip juga dengan Linked List untuk menyimpan koleksi dari data. Linked List dapat dianalogikan sebagai rantai linier sedangkan

Binary Tree bisa digambarkan sebagai rantai tidak linier. Binary Tree dikelompokkan menjadi

unordered Binary Tree (tree yang tidak berurut) dan ordered Binary Tree (tree yang terurut).