Hashing and Binary Tree


Hashing

   What is hashing? Hashing is the transformation of a string of characters into a usually shorter fixed-length value or key that represents the original string. Hashing is used to index and retrieve items in a database because it is faster to find the item using the shorter hashed key than o find it using the original value. It is also used in many encryption algorithms.

   The hashing algorithm is called the hash function. The hash function is used to index the original value or key and then used later each time the data associated with the value or key is to be retrieved.
A good hash function also should not produce the same hash value from two different inputs. If it does, this is known as a collision and must be handled using some collision handling technique. Following are the ways to handle collisions:

  • Chaining: The idea is to make each cell of hash table point to a linked list of records that have the same hash function value. Chaining is simple but requires additional memory outside the table.
  • Open Addressing: In open addressing, all elements are stored in the hash table itself. Each table entry contains either a record or NIL. When searching for an element, we one by one examine table slots until the desired element is found or it is clear that the element is not in the table.
   Here are some relatively simple hash functions:
  • Division-remainder method: The size of the number of items in the table is estimated. That number is then used as a divisor into each original value or key to extract a quotient and a remainder. The remainder is the hashed value.
  • Folding method: This method divides the original value into several parts, adds the parts together, and then uses the last four digits as the hashed value or key.
  • Radix transformation method: Where the value or key is digital, the number base can be changed resulting in a different sequence of digits. High-order digits could be discarded to fit a hash value of uniform length.
  • Digit rearrangement method: This is simply taking part of the original value or key such as digits in positions 3 through 6, reversing their order, and then using that sequence of digits as the hash value or key.
   Is hashing used in blockchain technology? Yes, it is. Hashing is an important thing in blockchain technology. It is a mathematical process that is used to write new transactions into a blockchain. The process is expected by a hash function with the help of a hashing algorithm. So basically, data is stored in blockchains. And of course, it will have a data structure also. There are mainly two data structures used in blockchain, pointers, and linked lists. We know pointers are variables that store the address of the other variables. In blockchain, the pointers also store the hash value of the previous block. In the data structure level view, we can say that blockchain is basically a linked list in which each node stores a hash pointer and a data header. While the data header will store the data of that block, the pointer will have the address of the preceding block as well as the hash value.
Binary Tree

    So, now we know what hashing is. Then what about binary tree? Well, a tree is a hierarchical data structure. Main uses of trees include maintaining hierarchical data, providing moderate access and insert/delete operations. Hence, binary trees are special cases of tree where every node has at most two children.

   Following are common types of binary trees:
  • Full binary tree: A binary tree is full if every node has 0 or 2 children. We can also say a full binary tree is a binary tree in which all nodes except leaves have two children.
  • Complete binary tree: A binary tree is a complete binary tree if all levels are completely filled except possibly the last level and the last level has all keys as left as possible.
  • Perfect binary tree: A binary tree is a perfect binary tree in which all internal nodes have two children and all leaves are at the same level.
  • Balanced binary tree: A binary tree is balanced if the height of the tree is O (log n) where n is the number of nodes.
  • A degenerate (or pathological) tree: A tree where every internal node has one child.

Comments

Post a Comment

Popular posts from this blog

Hash Table

   Today, I am going to explain about hash tables. If you are still confused about hashing, you can go and check my "Hashing and Binary Tree" post/blog. Well then, let's get started.    Hash table is a data structure that stores data in an associative manner. In a hash table, 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.  Thus, it becomes a data structure in which insertion and search operations are very fast irrespective of the size of the data. Hash table uses an array as a storage medium and uses the hash technique to generate an index where an element is to be inserted or is to be located.    The hashing technique may be used to create an already used index of the array. In such a case, we can search the next empty location in the array by looking into the next cell until we find an empty cell. This technique is called linear pr...
Read more

AVL Tree

Image
   Today let's talk about what an AVL tree is.  An AVL tree is a subtype of the binary search tree. Named after it's inventors Adelson, Velskii, and Landis, and that's how they made the name AVL, taken by their initials. AVL trees have the property of dynamic self-balancing in addition to all the properties exhibited by binary search trees. Here are the operations of an AVL tree: Insertion Deletion Insertion    Inserting a new node can cause the balance factor of some node to become 2 or -2. In that case, we fix the balance factors by use of rotations. Also, only the heights of the nodes on the path from the insertion point to the root can be changed. So, after inserting, we go back up to the root and update heights of the nodes and if we find any node with a balance factor of 2 or -2, we fix it by rotation. There are two rotations, which are the left rotation and the right rotation.    Here are steps to follow for insertion:    ...
Read more