Hashing & Binary Tree

• Hashing 
• Hashing is a technique to store retrieve key in a faster way. 
• It's transforming a string into a shorter length value/key. (hashed key)

• Hash Table
• Hash table is an array that stores the original value of a string.
• The hash table size is lower than the total number of possible string (some string can have the same key).

• Hash Function
• There are several methods to hash a string into a key:
• Mid-square
• Square the string, then obtain the key from number of bits taken from the middle of the square.
• Division
• This is the most common and simplest method.
• We can obtain the key by dividing the string with modulus operator.
• Folding
• We can obtain the hash key by dividing the key value into parts. Every parts has the same number of digits(except for the last one). Then add every parts except the last one.
• ex: x= 1264 ; then the parts is 12 & 64 ; then the sum is 76(hash value).
• Digit Extraction
• Considering some digits as a hash address from the given number.
• ex: x=15.769 ; If we extract the first, third and fifth digit, we will obtain the hash code which is 179
• Rotating Hash
• Use any hash method to find the hash code. Then rotate the value from front to back.
• ex: hash address=19920 ; then the rotation result is 02991.
• Collision
• There are two ways to handle collision:
• Linear Probing
• Searching for next empty slot and store the string there.
• Chaining
• Inserting string to a slot as chained list.

• Tree
• Tree is a form of non-linear data structure that describes the relationship that is hierarchical between the elements.
• Tree can be defined as a collection of nodes with a special element called root and other nodes are divided into sets that are not related to each other (called as sub-tree).

• Binary Trees
• A binary tree is made of nodes where each node contains a left pointer and right pointer. The root pointer points to top of tree. 
• Left and right pointers point to sub-tree smaller than both sides with recursive.

• Hashing Implementation in Blockchain
• When we are talking about hashing in blockchain, we are talking about 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.