Hashing & Binary tree GSLC 2 Data Structures

Hashing is a process that use the hash function. Before that, do you know what is a hash function? Hash function is a function that maps every data of arbitrary size to fixed size values. The values that returned by a hash function is called hash function or simply hashes. The values that used to index a fixed sized table or hash table are called hash values.

Hash functions & their hash tables are used for access datas and the data storage space is fractionally small. They access datas in nearly constant time per retrieval. Hashing is a computationally & efficient form of data storage which avoids the non-linear access of the ordered and unordered list. Hash functions related to (& often confused with) checksums, ciphers, error-correcting codes, randomization codes, fingerprints, check digits, & lossy compressions.

Hash Function usage:

• Calculating a fixed-size bit string value from a file.
• Allocate memory
• Access datas

Overview

A hash functions perform three functions:

1. Convert variable length into fixed length values
2. Scramble the bits of the key so that the resulting values are uniformly distributed over the key space
3. Map the key values into one less than or equal to the table size

Good hash function characteristics

A good hash function must minimizing collisions & computing the datas quickly. The poorly designed hash function will perform slowly & it causes the collision.

Implementation in a Blockchain

Hashing is implemented in a blockchain by chaining the hash tables that have a hash function in them. The hash tables consist of more than one keys and more hashing processes. The hash table hashing will be used in the current technology.

Source:

• Wikipedia
• etc.

Hash Table GSLC Data Structures

In computing, a hash table (hash map) is a data structure that implements an associative array abstract data type, a structure that can map keys to values. A hash table uses a hash function to compute an index, also called a hash code, into an array of buckets or slots, from which the desired value can be found.

A hash function will assign each key to a unique bucket, but most hash table designs employ an imperfect hash function that cause hash collision where same index is defined by the hash function for more than one key.

One-step syntax:
index = f(key, array_size)

Two-step syntax:
hash = hashfunc(key)
index = hash % array_size

In the two syntax, the hash is independent of the size of the array and it's reduced to an index (a number between 0 & array size-1) using a modulo (%) operator. The array size is a power of 2 (c^2), the remainder operator is reduced to masking, which improves speed, but can increase the problems with a poor hash function.

We must understand the blockchain concept before we implement the hash table.

Blockchain concept

A blockchain is defined as a data structure that stores a state and its evolution over time. The state is a key-value store where keys are called state elements. The state element's concept is an abstraction that contents a corresponding balance in every address or a variable of a contact account with its value. A transaction is an atomic change of involved state elements' number. A block is a sequence of transactions. In a blockchain, every block is hash-chained with the previous block. Every block is generated at intervals of length T (block time) and it is identified with its index (an increasing number). A block in index i is symbolized with b_i . The depth of a block is the number of mined blocks that is added by one, or equals 1 (for the last mined block). A block should conform to a consensus rule for being a valid block, which may deal with specific semantic constraints. Even if consensus rules are fundamental in practice, the rest of the paper is largely independent from the specific rules that encoded by a blockchain. The consensus algorithm is the way nodes reach an agreement about the next block the will be added to the blockchain. The rest of the paper is independent from the blockchain-adopted algorithm. Forks temporarily produced by certain algorithms, then one of the forks will be chosen by all nodes discarding the other chains' blocks.


Hash Table implementation in a blockchain

Hash Table implemented in a blockchain by chaining the tables that have a hash function in them. The hash tables consist of more than one keys and more hashing processes. The hash table will be used in the current technology.

References

Anonymous, Hash Table - Wikipedia. Accessed in: 11^th of March 2020. https://en.wikipedia.org/wiki/Hash_table
Bernardini, Matteo & friends. Blockchains Meet Distributed Hash Tables: Decoupling Validation from State Storage (Extended Abstract). Accessed in: 11^th of March 2020. http://ceur-ws.org/Vol-2334/DLTpaper4.pdf