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