Hashing & Binary Tree

Ø  Hashing

Hashing merupakan teknik yang digunakan untuk mengidentifikasi objek tertentu dari sekelompok objek serupa, contohnya :

-        Di universitas, setiap siswa diberi nomor gulungan unik yang dapat digunakan untuk mengambil informasi tentang mereka.

-    Di perpustakaan, setiap buku diberi nomor unik yang dapat digunakan untuk menentukan informasi tentang buku, seperti posisinya yang tepat di perpustakaan atau pengguna yang telah dikeluarkannya, dll.

Dalam melakukan aktifitas hashing, terdapat dua komponen penting yang harus diperhatikan, yaitu hash table dan hash function.

Hash Table

Hash table atau biasa dikenal sebagai hash map merupakan struktur data yang mengimplementasikan tipe data abstrak array asosiatif, struktur yang dapat memetakan kunci ke nilai. Hash table menggunakan fungsi hash untuk menghitung indeks, juga disebut hash code, ke dalam array dari bucket atau slot, dari mana nilai yang diinginkan dapat ditemukan.

Secara ideal, fungsi hash akan menetapkan setiap kunci ke bucket yang unik, tetapi sebagian besar desain tabel hash menggunakan fungsi hash yang tidak sempurna, yang dapat menyebabkan hash collisions di mana fungsi hash menghasilkan indeks yang sama untuk lebih dari satu kunci.

Dalam hash table berdimensi baik, biaya rata-rata (jumlah instruksi) untuk setiap pencarian tidak tergantung pada jumlah elemen yang disimpan dalam tabel. Banyak desain tabel hash juga memungkinkan penyisipan dan penghapusan sewenang-wenang pasangan nilai kunci, pada biaya rata-rata konstan per operasi. 

Hash Function

Fungsi hash adalah fungsi yang dapat digunakan untuk memetakan kumpulan data dari ukuran arbitrer ke kumpulan data dengan ukuran tetap, yang termasuk dalam Hash table. Nilai yang dikembalikan oleh fungsi hash disebut nilai hash, kode hash, jumlah hash, atau hanya hash.

Persyaratan dasar adalah bahwa fungsi harus menyediakan distribusi nilai hash yang seragam. Distribusi yang tidak seragam meningkatkan jumlah tabrakan dan biaya penyelesaiannya.

Distribusi harus seragam hanya untuk ukuran tabel yang terjadi dalam aplikasi. Secara khusus, jika seseorang menggunakan pengubahan ukuran dinamis dengan penggandaan yang tepat dan membagi dua ukuran tabel, maka fungsi hash harus seragam hanya jika ukurannya adalah kekuatan dua. Di sini indeks dapat dihitung sebagai beberapa rentang bit dari fungsi hash. Di sisi lain, beberapa algoritma hashing lebih suka ukurannya menjadi bilangan prima. Operasi modulus dapat memberikan beberapa pencampuran tambahan; ini sangat berguna dengan fungsi hash yang buruk.

Untuk skema pengalamatan terbuka, fungsi hash juga harus menghindari pengelompokan, pemetaan dua atau lebih kunci ke slot berturut-turut. Pengelompokan seperti itu dapat menyebabkan biaya pencarian meroket, bahkan jika faktor beban rendah dan tabrakan jarang terjadi.

Ø  Binary Tree

Dalam ilmu komputer, pohon biner adalah struktur data pohon di mana setiap simpul memiliki paling banyak dua anak, yang disebut sebagai anak kiri dan anak kanan. Definisi rekursif dengan menggunakan teori himpunan teori adalah bahwa pohon biner (non-kosong) adalah tupel (L, S, R), di mana L dan R adalah pohon biner atau himpunan kosong dan S adalah himpunan tunggal. Beberapa penulis mengizinkan pohon biner sebagai set kosong juga.

Dari perspektif teori grafik, pohon biner (dan K-ary) sebagaimana didefinisikan di sini sebenarnya adalah arborescences. Pohon biner dengan demikian dapat disebut juga bifurcating arborescence - sebuah istilah yang muncul dalam beberapa buku pemrograman yang sangat tua, sebelum terminologi ilmu komputer modern menang. Juga dimungkinkan untuk menafsirkan pohon biner sebagai grafik yang tidak diarahkan, dan bukan diarahkan, dalam hal ini pohon biner adalah pohon berakar yang tertata dan berakar. Beberapa penulis menggunakan pohon biner yang di-rooting alih-alih pohon biner untuk menekankan fakta bahwa pohon itu ber-root, tetapi seperti yang didefinisikan di atas, pohon biner selalu berakar. Pohon biner adalah kasus khusus dari pohon K-ary yang tertata, di mana k adalah 2.

Dalam ilmu komputer, pohon biner digunakan dalam dua cara berbeda:

1.     Sebagai cara mengakses node berdasarkan nilai atau label yang terkait dengan setiap node. Pohon biner berlabel cara ini digunakan untuk mengimplementasikan pohon pencarian biner dan tumpukan biner, dan digunakan untuk pencarian dan penyortiran yang efisien. Penunjukan node non-root sebagai anak kiri atau kanan bahkan ketika hanya ada satu anak yang hadir dalam beberapa aplikasi ini, khususnya itu penting dalam pohon pencarian biner.

2.    Sebagai representasi data dengan struktur bifurkasi yang relevan. Dalam kasus seperti itu, susunan khusus simpul di bawah dan / atau ke kiri atau kanan simpul lain adalah bagian dari informasi