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.