Hashing & Binary Tree

Hashing
Hashing is an important Data Structure which is designed to use a special function called the Hash function which is used to map a given value with a particular key for faster access of elements. The efficiency of mapping depends of the efficiency of the hash function used.

Hash Table
An array that stores pointers to records corresponding to a given phone number. An entry in hash table is NIL if no existing phone number has hash function value equal to the index for the entry.

Hash Function
A function that converts a given big phone number to a small practical integer value. The mapped integer value is used as an index in hash table. In simple terms, a hash function maps a big number or string to a small integer that can be used as index in hash table.

Collision
Since a hash function gets us a small number for a key which is a big integer or string, there is a possibility that two keys result in the same value. The situation where a newly inserted key maps to an already occupied slot in the hash table is called collision and must be handled using some collision handling technique.

There are two general ways to handle collisions:

Linear Probing : search the next empty slot and put the string there

Chaining          : Put the string in a slot as a chained list (linked list)

Linear Probing

Linear probing is a scheme in computer programming for resolving collisions in hash tables, data structures for maintaining a collection of key-value pairs and looking up the value associated with a given key. In linear probing, we linearly probe for the next slot. Linear probing has a bad search complexity if there are a lot of collisions.

Let us consider a simple hash function as “key mod 7” and sequence of keys as 50, 700, 76, 85, 92, 73, 101.

Chaining

In chaining, we store each string in a chain (linked list). So if there is a collision, we only need to iterate on that chain.

Let us consider a simple hash function as “key mod 7” and sequence of keys as 50, 700, 76, 85, 92, 73, 101.

Hashing in Blockchain

Blockchain technology is without a doubt, one of the most defining technological innovations of our times. It has defined how digital transactions are verified and stored through the use of Distributed Ledger Technologies (DLT). But to understand how blockchain works in cryptocurrency, we need to have in mind one basic concept: hashing.

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 hash function, will take any transaction/data input and rehash it to produce an output of a fixed size. The process of using a given hash function to process a transaction is called hashing. The transactional output of that given hash function is what we call a hash. And that should be it. There is more we need to expound on to demystify hashing in the blockchain. At this point, I want to emphasize that it is good to remember that the basic characteristic of any given hash function lies in the size of its output. This is what gives us the different hash functions.

Cryptographic Hash Function

SHA 256: an output of a 256-bit hash and currently in use on the Bitcoin network

Keccak-256: an output of a 256-bit hash; currently in on the Ethereum network

The cryptographic hash function is an integral part of the blockchain innovation. It is essentially a feature that gives security capabilities to the processed transactions, making them immutable. Hashing is also at the center of “Merkle Trees”, which is an advanced approach to blockchain hashing. It is useful in issues of scalability, and mobile/light wallets.