Hashing

•      Hashing is a technique used for storing and retrieving keys in a rapid manner.
•     Hashing can also be defined as a concept of distributing keys in an array called a hash table using a predetermined function called hash function.

Hash Table 

•      Hash table is a table (array) where we store the original string. Index of the table is the hashed key while the value is the original string.
•     The size of hash table is usually several orders of magnitude lower than the total number of possible string, so several string might have a same hashed-key.           example of hash fuction:                                                                                                                    

There are many ways to hash a string into a key for constructing hash functions:

1.      Mid-Square                                                                                                Square the string/identifier and then using an appropriate number of bits from the middle of the square to obtain the hash-key. 
    Steps:1. Square the value of the key. (k2)
   2. Extract the middle r bits of the result obtained in Step 1.                    

                 Function : h(k) = s

k = key

s = the hash key obtained by selecting r bits from k2

           

            2.  Division  

              Divide the string/identifier by using the modulus operator.

          It’s the most simple method of hashing an integer x. 

                 Function: h(z) = z mod M

z  = key

M = the value using to divide the key, usually using a prime number, the table size or the size of memory used.                                                       

            

            3. Folding 

             The Folding method works in two steps :

a.     Divide the key value into a number of parts where each part has the same number of digits except the last part which may have lesser digits than the other parts.

b.    Add the individual parts. That is obtain the sum of part1 + part2 + ... + part n. The hash value produced by ignoring the last carry, if any. 

           4. Digit Extraction

             A predefined digit of the given number is considered as the hash address. 

           5. Rotating Hash

            Use any hash method (such as division or mid-square method)

       After getting the hash code/address from the hash method, do rotation.

       Rotation is performed by shifting the digits to get a new hash address.

Collision

         What happened if we want to store these strings using the previous hash function         (use the first character of each string)•define, float, exp, char, atan, ceil, acos,          floor.  

    There are several strings which have the same hash-key, it’s float and floor (hash-key:5), char and ceil (hash-key: 2). It’s called a collision. How can we handle this? there are 2 way:

1. Linear Probing 

   Search the next empty slot and put the string there.  

   Linear probing has a bad search complexity if there are many collisions. 

   example:          

h[ ]	Value	Step
0	atan	1
1	acos	2
2	char	1
3	define	1
4	exp	1
5	float	1
6	ceil	5
7	floor	3
…

 2. Chaining 

            In chaining, we store each  string in a chain (linked list).

    So if there is collision, we only  need to iterate on that chain.

    example: 

    

h[ ]	Value
0	atan à acos
1	NULL
2	char à ceil
3	define
4	exp
5	float à floor
6	NULL
7	NULL
…

   

Blockchain

A blockchain is also a distributed data structure but its purpose is completely different.

Think of it as a history, or a ledger. The purpose is to store a continuously-growing list of record without the possibility of tampering and revision.

It is mainly used in the bitcoin currency system for keeping track of transactions. Its property of being tamper-proof let everybody know the exact balance of an account by knowing its history of transaction.

In a blockchain, each node of the network stores the full data. So it is absolutely not the same idea as the DHT in which data are divided among nodes. Every new entry in the blockchain must be validated by a process called mining whose details are out of the scope of this answer but this process insure consensus of the data.

The two structures are both distributed data structure but serve different purposes. DHT aims to provide an efficient (in term of lookup time and storage footprint) structure to divide data on a network and blockchain aims to provide a tamper-proof data structure.