Hashing table & Binary Tree (Rangkuman Week 4)

Hashing & Hash Table

Hashing merupakan sebuah teknik untuk menyimpan dan mengambil data didalam kelompok tipe object yang serupa, dalam kehidupan teknik ini sebenarnya sudah sering di lakukan, salah satu contohnya adalah dalam perkuliahan setiap mahasiswa memiliki NIM yang berbeda - beda dengan tujuan jika dibutuhkan mencari data diri mahasiswa pihak perkuliahan dapat langsung menggunakan NIM tersebut, dan contoh lainnya seperti No KTP yang biasanya digunakan untuk mengetahui informasi tentang kependudukan orang tersebut. Dalam pemrograman hashing digunakan pada saat kita ingin menyimpan sebuah object dalam suatu array tetapi ada kondisi dimana indexnya atau key sangat besar sehingga membutuhkan hashing. Dan disinilah disaat kita menggunakan teknik hashing untuk menyimpan sebuah object, maka object tersebut akan disimpan di dalam yang namanya hash table.

Hash Table merupakan sebuah tempat untuk menyimpan 2 pasang data (key / value).

Dalam hashing data menjadi sebuah key, ada terdapat beberapa fungsi (hash function) yang dapat dilakukan, yaitu:

• Mid-square (dipangkatkan dan diambil yang tengah)
• Division (operasi modular)
• Folding (membagi lalu di gabung)
• Digit Extraction (menggunakan digit index)
• Rotating Hash (menggunakan metode mid-square atau division lalu hash key di reverse)
• ...

Ada situasi dimana saat ingin menyimpan sebuah data string menggunakan fungsi - fungsi diatas tetapi terdapat hash-key yang sama, hal ini di sebut dengan Collision dan biasanya ada dua cara untuk menangani hal tersebut, dan cara tersebut yaitu:

• Linear Probing (Dengan mencari slot lain yang kosong dan di letakkan disana)
• Chaining (menggunakan linked list pada slot tersebut dan string yang mengalami collision tersebut ditaru dislot selanjutnya (linked list))

Ada beberapa keuntungan dan kerugian dari menggunakan Hash Table, salah satunya adalah:

• Keuntungan:
• Mengakses data lebih cepat
• Kecepatan dalam mengedit data (insertion, deletion, dan searching)
• Kekurangan:
• Sering terjadi Tabrakan atau yang namanya Collision
• Sulit jika ingin mencetak semua isi dari hash table
• Sulit dilakukan jika mencari nilai Min dan Max

Blockchain merupakan salah satu bukti bahwa Hash sangat digunakan pada jaman sekarang karena kita bisa ambil contoh aslinya sepeti bitcoin menggunakan konsep ini dari lama untuk mengamankan semua data - datanya yang penting. Bahkan ada beberapa perusahaan di Indonesia yang sudah menggunakan konsep ini, salah satunya adalah Ledger Now, BlockChain Zoo, IBM, Core-Chain.

Trees & Binary Tree

Trees merupakan struktur data non-linier menunjukkan relasi dari hirarki object - object data. Trees menggunakan teknik pointer untuk menyambungkan node dengan node di dalam tree.

Akan dijelaskan sedikit tentang konsep dari tree. (1) disebut sebagat root karena terletak di paling atas, garis - garis yang menghubungkan node - node diatas di sebut sebagai edge, untuk (4,6,7,9,10) disebut sebagai leaf karena tidak memiliki yang dinamakan anak, untuk salah satu contohnya yaitu (2,3) merupakan sibling karena memiliki parent yang sama.

Binary Tree Mirip dengan konsep atau bentuk Tree pada umumnya, tetapi setiap parent (node) memiliki minimal 2 anak, dan 2 anak tersebut biasanya dianggap menjadi left child dan right child dan sama seperti konsep tree node yang tidak memiliki anak disebut leaf.

Binary Tree memiliki beberapa tipe yang salah satunya yaitu sebagai berikut:

• Perfect Binary Tree ( semua node memiliki kedalaman level yang sama)
• Complete Binary Tree ( semua node selain yang leaf terisi)
• Skewed Binary Tree ( disaat dimana setiap node memiliki minimal satu anak)
• Balanced Binary Tree ( disaat dimana setiap leaf tidak lebih jauh ke root dari pada leaf yang lainnya.

Salah satu keuntungan dari konsep Binary Tree ini adalah lebih menghemat memori dan waktu pada komputer dibandingkan konsep yang biasa, dapat dengan mudah untuk menemukan parent dari sebuah node atau anak, mempermudah terjadinya lintasan linier pada Tree.