Hashing Tables and Binary Tree

GLSC 10 Maret 2020

Hashing Tables & Binary Tree

Hash Table

Hashing adalah metode untuk menyimpan data di alam sebuah array agar penyimpanan, pencarian , penambahan , dan penghapusan data dapat dilakukan dengan cepat.Hash table merupakan salah satu struktur data yang digunakan dalam penyimpanan data sementara. Tujuan dari hash table adalah untuk mempercepat pencarian kembali dari banyak data yang disimpan. Hash table menggunakan suatu teknik penyimpanan sehingga waktu yang dibutuhkan untuk penambahan data (insertions), penghapusan data (deletions), dan pencarian data (searching) relatif sama dibanding struktur data atau algoritma yang lain.

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

Kelebihan Dari Hash Table :

1.waktu akses relatif cepat

2.kecepatan insertion dan eletion relatif sama

3.cocok untuk merepresentasikan data dengan frekuensi insert, delete , dan search yang tinggi.

Kelemahan Dari Hash Table :

1.sering ditemukan hash table yang recordnya bertabrakan

2.tidak efisien mencetak seluruh elemen pada table hash

3.tidak efisisne untuk mencari elemen maksimum dan minimum

contoh coding fungsi hash :

int hash(String key, int tableSize)

{

int hashVal = 0;

for (int i=0; i < key.length(); i++)

{

hashVal = (hashVal * 128 + key.charAt(i)) % tableSize;

}

return hashVal % tableSize;

}

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.