Hashing Table and Binary Tree


Hashing

Hashing is a technique used for storing and retrieving keys in a rapid manner. The string of characters is made shorter in length value but still represents its original string.

Hash Table

Hash table is a table of array where a string is stored and can be hashed. Its size is usually smaller that the total number of possible string, so several string might have a same hashed-key.

Hash Function

There are a lot of ways to hash a string into a key, the most common is Division.

Division

Division is one of the methods used to hash a string into a key, which is done by dividing the string/identifier by using the modulus operator and the value that is usually used is a prime number, the table size or the size of memory used.

“HIKE” would be stored at the location
                        ( 64+8 + 64+9 + 64+11 + 64+5) % 97 = 2

Binary Tree
Binary tree is rooted tree data structure in which each node has at most two children and the two children usually distinguish themselves as left child and right child. The node that doesn’t have any child is called leaf.
Types of binary tree
-        Perfect Binary Tree
            It is a binary tree which every level are at the same depth
-        Complete Binary Tree
It is a binary tree in which every level except the last is completely filled and all    nodes are as far left as possible. A perfect binary tree is a complete binary tree
-        Skewed Binary Tree
It is a binary tree in which each node has at most one child
-        Balanced Binary Tree
It is a binary tree in which no leaf is much farther away from the root than any other leaf.

The Research

A hash is a function that converts an input of letters and numbers into an encrypted output of a fixed length. A hash is created using an algorithm and is essential to blockchain management in cryptocurrency. It helps in storing data of transaction (Time, Date, Who etc.). The blockchain technology is probably one of the most defining technological innovations of our time. It has changed the ways how digital transactions are managed and arranged. Hashing in blockchain refers to the process of having an input of whatever length reflecting an output item of a fixed length. Example : When you take video of 100 megabytes and hash it using SHA-256 the output will be a hash of 256-bits in length and if you take a video of 50 megabytes the output will be the same. The difference will lie on the hash pattern


Comments

Post a Comment

Popular posts from this blog

AVL Tree and B-Tree

Image
AVL Tree and B-Tree AVL Tree ·        Introduction Before we dive into the AVL tree, we should review Binary Tree. The binary tree is one of the data structures, it features sorting, ease insertion and deletion, and searching, although being able to search at a fast rate, the binary tree has a weakness. The quickness of the methods in a binary tree depends on the height of the tree, moreover it can be as large as n-1 when it's skewed, furthermore, if this happens the searching, deletion, and insertion method’s rate will be comparable to linear search. The AVL Tree takes to resolve the weakness of the binary tree by commencing rotation’s when the tree is Imbalance. The goal of this balancing is to rotate the binary tree until it has the minimum height and. ·        Balance Factor Balance Factor is a method to adjust the balance of an AVL Tree from an imbalance state. The formula is as stated below: Balance factor = height of the left subtree – height of right sub
Read more

Stack and Infix, Prefix, Postfix Notation

Stack is one of the basic flow of data that can come from an array list or a linked list. Imagine if there was a stack of boxes or plate. The last box or plate will be the first one to be used (LiFo: Last in First out). Just like that analogy, the "Stack" concept have only one place where the data can enter and exit which is the top. We also learned about Infix, Prefix and Postfix which is the shifting of the operators in a certain expression notation and the answer to the question at the meeting was pref : / + 1 3 ^ * 100 5 30 post: 1 3 + 100 5 * 30 ^ /
Read more

Linked List II Summary

Linked list is a process or a way that enables us to easily edit an array  without using looping (e.g for) to count from zero to the point where we want to edit the data (also shifting is needed when editing an array).  So far, we have learned about two types of linked list. Doubly and single linked list, the first one is the circular single linked list. In circular single linked list, the last node contains a pointer to the first node which can help determine whether the data is located in the middle or in the end and also there is no storing of NULL value in the list. Secondly there is double linked list, which is a two way linked list that points to the nest data while also pointing to the previous data. Thirdly there is circular doubly linked list which is very similar to the single linked list but differ on the amount of pointer in each node (2). Just as I stated above, linked list gives us the ability to edit an array far more efficient rather than using a looping process. The r
Read more