Hash and Trees

This GSLC Session, My lecturer asking us to make a blog about Hashing and Trees. So here it is, my take on Hashing and Trees Data structure.

What is Hashing?
Hashing is a technique used for temporary storing and retrieving keys in a rapid and fast manner. Hashing is used as a data structure because for example, if you want to find if there is a certain string that exists in an array, we could make a key to connect it with so it's easier and more efficient to do search function for it. Hashing is used to index and retrieve items in a database because it is faster to find the item using shorter hashed keys than to find it using the original value. The example of hashing in real-life implementation is cryptocurrency.

Hash Table
A hash table is a data structure that consists of a table and a function to map unique key values for each row and become the number of record locations in a table. The advantage of hash tables is that the time to access is faster because the records that are searched are in the hash number of the storage location.

Hash Key
The hash key is an identifier that is used for mapping.

Hash Function
Hash Function is a Function that used to process a mapping that takes a key as an input, and then uses that input to locate the index that is desired. There are a lot of ways to hash a key:
  • Mid-Square Method
The Mid Square Method utilizes The ASCII Value of a string that is inputted. That parsed-to-int string is then squared. With the value that is squared, we pick the r bits of the middle of the number.
  • The Division Method
This method is pretty simple, The key in an integer that you inputted is divided using modulo, which resulted in the remainder of the division, used in indexing
  • The Folding Method
This method involves cutting the inputted number into several parts. Then, the parts are added together to generate a key that can be used to find the index of the desired data.
  • The Digit Extraction Method 
The digit extraction method uses a certain number as a key, then the digits are extracted
Example: in 236747 digits, the first, third and fifth digit is extracted, hence we can get 264 as the hash key.
  • The Rotating Method
The digit that is inputted are reversed. Example: 23301 rotated to 10332, then it is used as a key. 

Collision
Collision are a condition that happens when some data had the same key. This is a problem because it could mess the order of data that wanted to be inserted. To fic this, there are two solutions than can be used.

  • Linear Probing
Linear Probing utilizes empty array slots to fill the next similar hash key data.
  • Chaining
Chaining method utilizes Linked List, where the the same hash key data are linked next.

Tree
A tree is a non-linear data structure that represents relationships between one node to another.
Concept of Tree

  • Node at the top is called as root. 
  • A line connecting the parent to the child is edge. 
  • Nodes that do not have children are called leaf. 
  • Nodes that have the same parent are called sibling. 
  • Degree of node is the total sub tree of the node. 
  • Height/Depth is the maximum degree of nodes in a tree. 
  • If there is a line that connects p to q, then p is called the ancestor of q, and q is a descendant of p. 

Binary Tree

A binary tree is a hierarchical data structure in which each node has at most two children generally referred as left child and right child.
Each node contains three components:
  1. Pointer to left subtree
  2. Pointer to right subtree
  3. Data element
The topmost node in the tree is called the root. An empty tree is represented by NULL pointer.

Types Of Binary Trees

  • Perfect Binary Tree
In which, Every node that is currently present in this binary tree, had the complete set and the same depth in terms of their child amount.
  • Complete Binary Tree
A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. 
  • Skewed Binary Tree
A binary tree which, each node has at most 1 child node.
  • Balanced Binary Tree
Balanced binary tree is a binary tree in which no leaf is much farther away from the root than any other leaf.



Komentar

Posting Komentar

Postingan populer dari blog ini

Heap (Max And Min) & Tries

Gambar
Heap Heap is a Tree Type data structure that has a complete set of nodes. Heaps are used in store array. What so special about Heaps is that every time we inserted value to it, it used its own  Algorithm to sort itself and the way of indexing them is through left to right nodes in every level. You can access a parent of the node by dividing their index by 2. Types of Heap  A. Max Heap In Max Heap Binary Tree, The parent of the node child holds a value that is greater than its child value. The Max Value of the Tree is located at the Root of the tree. B. Min Heap In Max Heap Binary Tree, The parent of the node child holds a value that is smaller than its child value. The Min Value of the Tree is located at the  Root  of the tree. Min Max Heap C. Min Max Heap Min Max Heap is a special case of Heap. It lets you build a tree structure that has an alternating structure where odd heights of the tree prioritize minimum value while the even h...
Baca selengkapnya

Linked List : Is it an Array?

Gambar
Apa itu Linked List? Seperti namanya, Linked list adalah struktur data yang dimodelkan linier, hampir sama dengan Array, well, keduanya adalah struktur data linier. Mereka mungkin terdengar sama, tetapi ada perbedaan di antara mereka. Apa yang membedakan antara array dan Linked List? Sementara kita tahu bahwa array disimpan dalam bentuk pada memori yang berdekatan, ini berbeda dalam kasus daftar tertaut, di mana mereka tidak benar-benar menggunakan lokasi yang berdekatan, melainkan, mereka menautkan satu sama lain menggunakan pointer. Uniknya, Linked list dapat melakukan penambahan dan penghapusan dari elemen apapun di lokasi manapun, asalkan mereka terhubung. Linked list dapat dibagi menjadi 4 jenis : 1. Singular Linked List 2. Double Linked List 3. Circular Single Linked List 4. Circular Double Linked List Singular Linked List Adalah linked list yang paling umum, dimana suatu linked list memiliki ujung pertama node yang bernama head dan memiliki ujung ...
Baca selengkapnya