HASH TABLE DAN TREE

HASH TABLE

Hash table adalah sebuah struktur data yang terdiri dari sebuah table dan fungsi yang bertujuan untuk memetakan nilai kunci yang unik untuk sebuah record (baris) untuk menjadi sebuah angka (hash) lokasi record tersebut dalam sebuah table.



Keunggulan dari struktur hash table ini yaitu lebih cepat mencari item jika record yang disimpan langsung berada pada angka hash lokasi penyimpanannya.

Tetapi struktur hash memiliki kelemahan, yaitu jika hash table yang record nya memiliki angka hash yang sama sehingga terjadi bentrok (collision).



Benturan tersebut dapat dihindari dengan penerapan resolusi bentrokan (collision resolution policy) untuk menentukan lokasi record dalam table. Umumnya kebijakan tersebut adalah dengan mencari lokasi table yang masih kosong setelah lokasi berbentrokan.



Operasi yang terdapat di hashing table:

Insert                   :               diberikan sebuah key dan nilai, insert nilai dalam table.

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           :               mengembalikan iterator yang memeriksa nilai satu demi satu.



FUNGSI HASH

-          Mid Square : kuadratkan identifier dan gunakan jumlah bit dari tengah kotak untuk mendapatkan hash key.

-          Division : membagi nilai string atau identifier menggunakan operator modulo.

-          Folding : partisi identifier menjadi beberapa bagian lalu tambahkan bagian bersama – sama untuk mendapatkan kunci hash.

-          Digit Extraction : digit yang ditentukan sebelumnya dari nomor yang diberikan maka dianggap sebagai alamat hash.

-          Rotating Hash : fungsi ini hanya membalikkan nilai dari depan ke belakang, berlaku sebaliknya.

TREE

Tree adalah data struktur non linear yang mewakili hubungan hirarki antara objek data. Beberapa hubungan pohon dapat diamati dalam struktur direktori atau hirarki organisasi. Node tidak perlu disimpan secara berdekatan dan disimpan dimana saja yang dihubungkan oleh pointer.



BINARY TREE 


Binary tree terbuat dari node yang setiap node berisi kiri pointer dan kanan pointer. Pointer root menunjuk ke paling atas pohon. Pointer kiri dan kanan menunjuk ke subtree yang lebih kecil dari kedua sisi dengan rekursif.



Jenis jenis binary tree:

a.       Full binary tree

Binary tree yang setiap node nya (kecuali leaf) memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama.

b.       Complete binary search tree

Mirip dengan full binary tree, namun tiap subtree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki  0 atau 2 child.



BINARY SEARCH TREE


Binary search tree adalah binary tree dengan sifat bahwa semua left child harus lebih kecil daripada right child dan parent nya. Juga semua right child harus lebih besar dari left child beserta parentnya.



Source: http://muqoddarsrengmadureh.blogspot.com/2013/01/algoritma-dan-sturktur-data-hashing.html?m=1