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.
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
- 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.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
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 :
- The hash function should generate different hash values for the similar string.
- The hash function is easy to understand and simple to compute.
- The hash function should produce the keys which will get distributed, uniformly over an array.
- A number of collisions should be less while placing the data in the hash table.
- The hash function is a perfect hash function when it uses all the input data.
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
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