Hashing Table & Binary Tree

Hashing Table


  • Hash Table is a data structure which stores data in an associative manner. 
  • Data is stored in an array format, where each data value has its own unique index value. 
  • Access of data becomes very fast if we know the index of the desired data.
So, Hash Table is a data structure in which insertion and search operations are very fast where the size of the data doesn't matter. 

Hash Function


  •  A hash function job is to store values in an array with a limited size
  • It does it in a way that the array doesn't need to be searched through to find it. This allows us to enter values in any order and we can find them using a calculation instead of searching through the array

So how does Hash Table & Hash Function work together?

  • Key values are assigned to elements in a Hash Table using a Hash Function
  • Hash function helps calculate the best index an item should go in
Here are a few methods to hash keys from string:
  • Mid-square
  • Division
  • Folding

Mid-square:

In this method firstly key is squared and then mid part of the result is taken as the index. 


Example: consider that if we want to place a record of 3101 and the size of table is 1000. So 3101*3101=9616201 i.e. h (3101) = 162 (middle 3 digit)

Division:


In this the hash function is dependent upon the remainder of a division. 

Example: if the record 52,68,99,84 is to be placed in a hash table and let us take the table size is 10.


Then:
h(key)=record% table size.
 2=52%10
 8=68%10
 9=99%10
 4=84%10
Division method
 

Folding:


In this method, the key is divided into separate parts and by using some simple operations these parts are combined to produce a hash key. 

Example: consider a record of 12465512 then it will be divided into parts i.e. 124, 655, 12. After dividing the parts combine these parts by adding it.
H(key) = 124+655+12 = 791



Characteristics of good hashing function :


    

  1. The hash function should generate different hash values for the similar string.
    2. 

  2. The hash function is easy to understand and simple to compute.
    3. 

  3. The hash function should produce the keys which will get distributed, uniformly over an array.
    4. 

  4. A number of collisions should be less while placing the data in the hash table.
    5. 

  5. The hash function is a perfect hash function when it uses all the input data.
    6. 





Hashing In Blockchain

Hashing in blockchain refers to the process of having an input item of whatever length reflecting an output item of a fixed length. If we take the example of blockchain use in cryptocurrencies, transactions of varying lengths are run through a given hashing algorithm, and all give an output that is of a fixed length. This is regardless of the length of the input transaction. The output is what we call a hash. 


Here are some Hashing implementations in Blockchain :


    

  • Addresses on the blockchain are derived from hashing e.g. Bitcoin addresses use SHA2-256 and RIPEMD 160.
    • 



    

  • Hashing helps in defining cryptographic signatures that help determine valid transactions
    • 


(https://www.onlinehashcrack.com/how-to-hashing-in-blockchain-explained.php)





Binary Tree



A binary tree is a recursive data structure where each node can have 2 children at most.



A common type of binary tree is a binary search tree, in which every node has a value that is greater than or equal to the node values in the left sub-tree, and less than or equal to the node values in the right sub-tree.



Here's a quick visual representation of this type of binary tree:



Binary Tree concepts:




    

  • A binary tree is made of nodes, where each node contains a "left" reference, a "right" reference, and a data element
    • 

  • The topmost node in the tree is called the root
    • 

  • Every node (excluding a root) in a tree is connected by a directed edge from exactly one other node. This node is called a parent
    • 

  • On the other hand, each node can be connected to arbitrary number of nodes, called children
    • 

  • Nodes with no children are called leaves, or external nodes
    • 

  • Nodes which are not leaves are called internal nodes
    • 

  • Nodes with the same parent are called siblings
    • 






Advantages of trees



Trees are so useful and frequently used, because they have some advantages:


    

  • Trees reflect structural relationships in the data
    • 

  • Trees are used to represent hierarchies
    • 

  • Trees provide an efficient insertion and searching
    • 

  • Trees are very flexible data, allowing to move sub-trees around with minimum effort
    •

Comments

Post a Comment

Popular posts from this blog

Binary Search Tree

Image
Binary Search Tree Binary search tree is a data structure that quickly allows us to maintain a sorted list of numbers.  It is called a Binary tree because each tree node has a maximum of 2 children It is called a search tree because it can be used to search for the presence of a number in O(log(n)) time. The properties that separates a binary search tree from a regular binary tree is All nodes of left subtree are less than root node All nodes of right subtree are more than root node Both subtrees of each node are also BSTs meaning they have the above two properties On the picture shown above, the right tree is not a binary search tree because on the right subtree of the root, there's a number with smaller value than the root.  Basic Operations Following are the basic operations of a tree − Search   − Searches an element in a tree. Insert  − Inserts an element in a tree. Pre-order Traversal  − Traverses a tree in a pre-order manner. In-order Traversa
Read more

AVL Tree & B - Tree

Image
AVL Tree AVL tree is a self-balancing binary search tree in which each node maintains extra information called a balance factor whose value is either -1, 0 or +1. AVL tree got its name after its inventor Georgy Adelson-Velsky and Landis.  Since AVL trees are height balance trees, operations like insertion and deletion have low time complexity. AVL tree checks the height of the left and the right sub-trees and assures that the difference is not more than 1. This difference is called the Balance Factor . Balance Factor Balance factor of a node in an AVL tree is the differenc e between the height of the l eft subtree  and that of the  right subtree  of that node Balance Factor = (Height of Left Subtree - Height of Right Subtree) or (Height of Right Subtree - Height of Left Subtree) The self balancing property of an avl tree is maintained by the balance factor. The value of balance factor should always be -1, 0 or +1. If the difference in the height of left and
Read more