Hash Table and Binary Tree

Hashing

Is a technique used for storing and retrieving keys in a rapid manner.

It is used to index and retrieve items in a database because it is faster to find the item using shorter hashed key than to find it using the original value.

It can also be defined as a concept of distributing keys in an array called a hash table using the hash function

Hash Table is a table or array where we store the original string

Some important methods for constructing hash functions:

- Mid Square

- Division

- Folding

- Digit Extraction

- Rotating Hash

Collision happens when we want to store strings using the previous hash functions, and several strings have the same hash-key

We can handle this by:

- Linear Probing : Search the next empty slot and put the string there

- Chaining : Put the string in a slot as a linked list

Binary Tree

Tree Concept :

- Root : Node at the top

- Edge : A line connecting parent to child

- Leaf : Nodes that don't have children

- Sibling : Nodes that have the same parent

- Degree : Total sub tree of the node

- Height/Depth : Maximum degrees of nodes in a tree

Binary Tree is a rooted tree data structure where each node has at most 2 children

Types of binary tree :

- Perfect : Every level are at the same depth

- Complete : A binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible

- Skewed : Each node has at most one child

- Balanced : No leaf is much farther away the root than any other leaf

Hashing Table Implementation in Blockchain

Hashing helps in defining cryptographic signatures that help determine valid transactions. The hash of a transaction makes it easy to keep track of transactions on the 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. A good example is Bitcoin’s Secure Hashing Algorithm 256 (commonly shortened to SHA-256). Hashing using SHA-256 always gives an output result of a fixed length, which has a 256-bits length (the output is 32 bytes). This is always the case whether the transaction is just a single word or a complex transaction with huge amounts of data. What this means is that keeping track of a transaction becomes easier when you can recall/trace the hash. The size of the hash will depend on the hash function utilized, but the out using a particular hashing algorithm will be of a specific size.

Example:

When you take a YouTube video of say 50 megabytes and hash it using SHA-256, the output will be a hash of 256-bits in length. Similarly, if you take a text message of 5 kilobytes, the output hash will still be 256-bits. The only difference between the two will be the hash pattern. Let’s summarize the above information as follows: Hashing is the umbrella term for Cryptographic hash functions

Here are more examples :

- 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.

- The hash of a transaction makes it easy to keep track of transactions on the blockchain. 

- Instead of looking for a transaction that was the “1030th in block 14573”, it is easier just to copy the hash into a blockchain explorer from where you can view the transaction details.

- Hashing functions are crucial in crypto mining where a valid nonce is discovered by computing several hashes. This helps to form a consensus on the blockchain.

- The use of “hash of the data” helps to store large amounts of data on the blockchain. This data is time-stamped and can be hashed for future reference. It makes the permanent data storage less bulky or simply more economical.

- Hashrate- determining how fast and smoothly-running the mining process is. It is vital in determining difficulty levels during mining.