Hashing, Hash Table dan Binary Tree

Hashing, Hash Table dan Binary Tree

 Hashing

Hashing adalah teknik yang digunakan untuk secara unik mengidentifikasi objek tertentu dari sekelompok objek serupa. Hashing dilakukan dengan membuat fungsi hash. Hasil dari fungsi hash dimasukkan ke dalam hash table.

Hash Table adalah salah satu contoh implementasi linked list dalam data struktur. Hash table digunakan dalam penyimpanan data sementara.

Ada banyak cara untuk hashing string ke sebuah key:
1. Mid-square
2. Division (most common)
3. Folding
4. Digit Extraction
5. Rotating Hash

Contoh hash table yang kurang efisien dan yang efisien:

Contoh yang kurang efisien

masukkan deskripsi gambar di sini

Contoh fungsi hash yang efisien:

masukkan deskripsi gambar di sini


Sebaik apapun fungsi hash yang kita buat, collision tidak dapat dihindari, oleh karena itu ada banyak teknik untuk menghindari collision:

1. Separate Chaining (Open Hashing)

Separate Chahining adalah teknik yang paling banyak digunakan untuk resolusi tabrakan. Separate Chaining biasanya diimplementasikan menggunakan linked list. Dalam Separare Chaining, setiap elemen dari hash table adalah linked list. Untuk menyimpan elemen ke dalam table hash, kita harus memasukkannya ke linked list tertentu. Jika ada collision (Dua elemen berbeda yang memiliki hash yang sama) maka kita harus menyimpan kedua elemen tersebut ke dalam linked list yang sama.

masukkan deskripsi gambar di sini

enter image description here

2. Linear Probing (Open Addressing or Closed Hashing)

Dalam Open Addressing, daripada menggunakan linked list, semua catatan entri disimpan dalam array itu sendiri. Ketika entri baru harus dimasukkan, indeks hash dari nilai hash dihitung dan kemudian array diperiksa (dimulai dengan indeks hash). Jika slot di indeks hash tidak diisi, maka entri dimasukkan ke dalam slot di indeks yang telah di hashed yang lain itu melanjutkan dalam beberapa urutan penyelidikan sampai menemukan slot kosong.

enter image description here

BINARY TREE

 Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut Root dan node lainnya terbagi menjadi himpunan-himpunan yang saling tak berhubungan satu sama lainnya (disebut subtree). Untuk jelasnya, di bawah akan diuraikan istilah-istilah umum dalam tree :

 A) Predecessor : node yang berada diatas node tertentu.

 B) Successor : node yang berada di bawah node tertentu.

 C) Ancestor : seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama.

 D) Descendant : seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama.
E) Parent : predecessor satu level di atas suatu node.

F) Child : successor satu level di bawah suatu node.

G) Sibling : node-node yang memiliki parent yang sama dengan suatu node.

H) Subtree : bagian dari tree yang berupa suatu node beserat descendatnya dan memiliki semua karakteristik dari tree tersebut.

I) Size : banyaknya node dalam suatu tree.

J) Height : banyaknya tingkatan/level dalam suatu area.

K) Root : satu-satunya node khusus dalam tree yang tidak mempunyai predecessor. 

L) Leaf : node-node dalam tree yang tidak memiliki successor.

M) Degree : banyaknya child yang dimiliki oleh suatu node.


Image result for contoh binary tree

Maksimum node yang dapat dimiliki oleh sebuah level k dalam binary tree adalah 2k.





Sumber:
https://www.hackerearth.com/practice/data-structures/hash-tables/basics-of-hash-tables/tutorial/
http://new-funday.blogspot.com/2012/12/struktur-data-tree-dan-penjelasaanya.html









Comments

Post a Comment

Popular posts from this blog

Heap and Tries

Image
Heap and Tries Heap Heap adalah struktur data khusus berbasis pohon di mana pohon adalah complete binary tree. Umumnya, Heaps dapat dua jenis: Max-Heap: dalam Max-Heap, key yang ada di node root harus terbesar di antara key yang ada di semua child. Properti yang sama harus dapat direkursif untuk semua sub-tree di binary tree. Min-Heap: dalam Min-Heap, key yang ada di node root harus minimum di antara key yang ada di semua child. Properti yang sama harus dapat direkursif  untuk semua sub-tree di binary tree. Min Heap Setiap node lebih kecil dari masing-masing childnya Root merupakan node paling kecil, sedangkan node terbesar terletak pada leaf node Max Heap Setiap node lebih besar dari masing-masing childnya Root merupakan node paling besar, sedangkan node terkecil terletak pada leaf node Min-Max Heap Heap dengan Min heap pada level ganjil dan Max heap pada level genap Heap dapat diimplementasi dengan array maupun de
Read more

Summary of Data Structures

Image
Summary of Data Structures Nama      : Brian Eniko Singgih NIM        : 2301875074 Kelas       : CB01 Lecturer : Ferdinand Ariandy Luwinda (D4522) dan Henry Chong (D4460) Linked List 1. Circular Single Linked List Circular single linked list adalah single linked list yang tidak menerima value NULL yang dikarenakan node terakhir akan menunjuk ke head pointer sehingga circular single linked list tidak menerima value NULL. 2. Doubly Linked List Doubly linked list adalah single linked list yang memiliki 2 arah pointer dimana sebuah node memiliki 2 pointer yaitu next dan prev. Ada 2 cara untuk menyunting doubly linked list: a. Insert Insert digunakan untuk memasukan node baru ke dalam doubly linked list dan mengkoneksikan node tersebut dengan node yang sudah ada. struct tnode *node = (struct tnode*) malloc (sizeof (struct tnode); node->value = x; node->next  = NULL; node->prev  = tail; tail->next = node; tail = node; b. Delete Delete d
Read more

AVL Tree dan B-Tree

Image
AVL Tree AVL Tree adalah binary search tree yang telah disortir menjadi seimbang. AVL Tree merupakan nama dari kedua penemu AVL Tree yaitu G.M.Adelson Veleskii dan E.M.Landis. Contoh AVL Tree: Contoh Binary Search Tree yang belum di sortir: Cara menentukan Height dan Balance Factor : Height : - Jika node (root) tidak memiliki subtree heightnya = 0 - Jika node adalah leaf, height =  1 - Jika internal node, maka height =  height tertinggi dari anak + 1 Balance Factor : -selisih height antara anak kiri dan kanan, jika tidak memiliki anak, dianggap 0. Ada 2 jenis rotation dalam AVL Tree: 1. Single Rotation 2. Double Rotation Rotasi pertama: Rotasi kedua: B-Tree Pada B-Tree dikenal istilah order. Order menentukan jumlah maksimum/minimum anak yang dimiliki oleh setiap node, sehingga order merupakan hal yang cukup penting dalam B-Tree. 2-3 Tree pada postingan sebelumnya yaitu Balanced Binary Search Tree (AVL and RBT) and 2-3 Tree merupakan salah satu B-Tree be
Read more