Hashing & Hash Table

Hashing & Hash Table

Hashing is a technique used to access value in database or array faster.

The way hashing works is the original string of characters are transformed in to short length value or key called Hash Key, that represent the original string or as index to access original value stored in array called Hash Table or database.

The way to hash a string is called Hash Function. There is some important methods to construct hash function :

·       Mid-square

square the string / identifier and extract the middle r bits of the result.

·       Division ( most common )

Divide the string /identifier using modulus operator by value M (can be any value but usually prime number, table size or the size of memory used.

·       Folding

Divide each value into number of part with the same number of digits. Sum all of the part. If there is last carry in hash value, the last carry will be ignored.

·       Digit Extraction

Predefined digit of the give number is considered as the hash address. Ex: if x =14568, we exteact 1^st, 3^rd, and 5^th digit, and the has code of 158

·       Rotating Hash

Use hash method, after get the hash address/key, rotate the address by shifting the digit to get new hash address/key.

Collision

is when the different string have the exact same hash address. If this thing happens there is  2 general way to handle this:

-          Linear Probing : search the next empt slot and put the string there

-          Chainin             : put the string in a slot as a chained link ( linked list).

Implementation of Hash Table in Block Chain

The data in Hash Table is divided and stored in the different node, while in the block chain the data is saved like the hash Table but the data is not divided in blockchain, in blockchain all node have the copy of all the data. As far as i can find, hash table is not used in Block Chain.