Hash Tables & Binary Tree
Hash Table
Hash table adalah sebuah struktur data yang menyimpan data dalam sifat yang asosiatif. Dalam hash table, data disimpan di dalam format array, dimana setiap data value memiliki indeks unik. Akses ke data (searching) menyadi sangat cepat kalau kita tau index / key dari data yang dimaksud.Contoh: Katakanlah data yang ingin di store adalah nama nama orang sebanyak 11.
Dari nama nama ini kita bisa generate secara manual key yang dapat membuat searching menjadi lebih cepat.
- Bea = 264 % 11 = 0
- Tim = 562 % 11 = 1
dst.
Dalam kasus ini tidak ada data yang memiliki key index yang sama, bila ada 2 data atau lebih yang memiliki key yang sama maka terjadilah COLLISION. Ada banyak cara untuk menangani collision yang paling simpel adalah array probing, yaitu jika A memiliki key 0, lalu selanjutnya diinput B dengan key yang juga 0, maka B digeser ke kanan sampai menemukan array yang kosong. Tapi cara ini sangat beresiko untuk data yang berjumlah sangat banyak.
Cara yang lebih efisien untuk menangani collision dalam array berjumlah banyak adalah dengan menggunakan linked list di setiap key. Jadi jika A memiliki key 0, lalu selanjutnya diinput B dengan key yang juga 0, maka kita bentuk linked list di array indeks 0, dengan head sebagai A dan node/data selanjutnya sebagai inputan lain yang memiliki key 0.
0 - A > B > ...
https://www.youtube.com/watch?v=KyUTuwz_b7Q
Binary Tree
Binary Tree adalah graf pohon yang setiap elemennya memiliki tidak lebih dari 2 child.
Dalam pemrograman node node di dalam binary tree dapat berisikan Data dan alamatChild (tidak lebih dari 2). Biasanya diberi nama *leftChild dan *rightChild
Comments
Post a Comment