HASHING & BINARY TREE

Hashing

Hashing merupakan Teknik untuk menyimpan dan mengambil keys dengan cara yang cepat.

Hashing menyimpan keysnya di array yang bernama hash table dan menggunakan function yang sudah ditentukan yaitu hash function.

Hashing terdapat 5 jenis:

• Mid-square
• Division (paling sering digunakan)
• Folding
• Digit Extraction
• Rotating Hash

Mid square caranya adalah dengan mempangkatkan angka yang ingin disimpan yang kemudian akan diambil angka tengahnya.

Divison caranya adalah dengan memodulus angka yang ingin disimpan dengan ukuran dari size table yang diberikan/digunakan.

Folding caranya adalah dengan membagi setiap angka menjadi 2 bagian yang kemudian akan saling ditambahkan.

Digit extraction caranya adalah mengambil digit pada letak-letak terntetu yang sudah ditentukan sebelumnya dan angka tersebut kemudian akan menjadi hash addressnya.

Rotating hash caranya adalah menggunakan mid-square atau division terlebih dahulu buat dapet hash adressnya dan kemudian dibalik angkanya.

Hashing pada saat ini digunakan dalam blockchain, terutama dalam cryptocurrency. Hashing sangatlah penting dalam pengaturannya. Hash bagaikan backbone dalam cryptocurrency.

Hash membantu dalam menyimpan data yang sangat banyak dalam blockchain.

Collision

Collasion terjadi ketika ada string yang memiliki hash key yang sama contohnya seperti float dan floor dimana sama-sama berawalan f.

Collison bisa diatasi dengan 2 cara:

• Linear probing
• Chaining

Linear probing adalah mencari tempat kosong selanjutnya dan menaruhnya disana. Namun, cara ini sangatlah tidak efisien karena ketika string tersebut ingin dicari looping yang dilakukan akan banyak.

Chaining adalah meletakkan string tersebut sebagai linked list jadi apa bila floor terletak di hash key 5 maka ia linked list ke float jadi tidak membuang-buang waktu untuk mencarinya.

Tree

Tree merupakan struktur yang menunjukan hirarki antar non-linear data.

Node dalam tree tidak perlu disimpan secara berurut, ia dapat disimpan secara asal dan kemudian dihubungkan dengan pointer.

Konsep tree

• Node yang paling diatas disebut root.
• Line yang menghubungankan antara parent dan child disebut edge.
• Node yang tidak memiliki children disebut leaf.
• Node yang memiliki parent yang sama disebut sibling.
• Degree of node mereupakan jumlah dari sub tree sebuah node.
• Height/Depth merupakan maksimum degree dalam sebuah tree.
• Jika ada line yang menghubungkan antara p dan q, maka p disebut ancestor dari  q, dan q adalah descendant dari p.

Binary tree

Konsep binary tree

• Binary tree merupakan struktur data tree dimana setiap node maksimal memiliki 2 node.
• Setiap 2 children tersebut biasanya dibedakan sebagai left child atau right child.
• Node yang tidak memiliki children disebut leaf.

Tipe binary tree

• Perfect binary tree
• Complete binary tree
• Skewed binary tree
• Balanced binary tree

Perfect binary tree adalah dimana setiap level mempunyai height/depth yang sama.

Complete binary tree adalah binary tree yang setiap levelnya, kecuali yang terakhir terisi penuh dan semua node dipenuhkan pada sisi kiri tree. Semua perfect binary tree merupakan complete binary tree.

Skewed binary tree merupakan tree yang setiap nodenya maksimal memiliki 1 child.

Balanced binary tree merupakan tree dimana leaf yang satu tidak boleh lebih jauh levelnya dari leaf yang lain jadi harus seimbang.

Pada coding diberikut akan terbentuk seperti ini

       1    <-- root

     /   \

    2     3  

   /   

  4