Hashing Table and Binnary Tree. The Implementation in Blokchain
Introduction
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.
Collision Handling: Since a hash function gets us a small number for a big key, there is possibility that two keys result in same value. The situation where a newly inserted key maps to an already occupied slot in hash table is called collision and must be handled using some collision handling technique. Following are the ways to handle collisions:
- Chaining:The idea is to make each cell of hash table point to a linked list of records that have same hash function value. Chaining is simple, but requires additional memory outside the table.
- Open Addressing: In open addressing, all elements are stored in the hash table itself. Each table entry contains either a record or NIL. When searching for an element, we one by one examine table slots until the desired element is found or it is clear that the element is not in the table.
Implementation In C
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <stdbool.h> #define SIZE 20 struct DataItem { int data; int key; }; struct DataItem* hashArray[SIZE]; struct DataItem* dummyItem; struct DataItem* item; int hashCode(int key) { return key % SIZE; } struct DataItem *search(int key) { //get the hash int hashIndex = hashCode(key); //move in array until an empty while(hashArray[hashIndex] != NULL) { if(hashArray[hashIndex]->key == key) return hashArray[hashIndex]; //go to next cell ++hashIndex; //wrap around the table hashIndex %= SIZE; } return NULL; } void insert(int key,int data) { struct DataItem *item = (struct DataItem*) malloc(sizeof(struct DataItem)); item->data = data; item->key = key; //get the hash int hashIndex = hashCode(key); //move in array until an empty or deleted cell while(hashArray[hashIndex] != NULL && hashArray[hashIndex]->key != -1) { //go to next cell ++hashIndex; //wrap around the table hashIndex %= SIZE; } hashArray[hashIndex] = item; } struct DataItem* delete(struct DataItem* item) { int key = item->key; //get the hash int hashIndex = hashCode(key); //move in array until an empty while(hashArray[hashIndex] != NULL) { if(hashArray[hashIndex]->key == key) { struct DataItem* temp = hashArray[hashIndex]; //assign a dummy item at deleted position hashArray[hashIndex] = dummyItem; return temp; } //go to next cell ++hashIndex; //wrap around the table hashIndex %= SIZE; } return NULL; } void display() { int i = 0; for(i = 0; i<SIZE; i++) { if(hashArray[i] != NULL) printf(" (%d,%d)",hashArray[i]->key,hashArray[i]->data); else printf(" ~~ "); } printf("\n"); } int main() { dummyItem = (struct DataItem*) malloc(sizeof(struct DataItem)); dummyItem->data = -1; dummyItem->key = -1; insert(1, 20); insert(2, 70); insert(42, 80); insert(4, 25); insert(12, 44); insert(14, 32); insert(17, 11); insert(13, 78); insert(37, 97); display(); item = search(37); if(item != NULL) { printf("Element found: %d\n", item->data); } else { printf("Element not found\n"); } delete(item); item = search(37); if(item != NULL) { printf("Element found: %d\n", item->data); } else { printf("Element not found\n"); } }
Output:
~~ (1,20) (2,70) (42,80) (4,25) ~~ ~~ ~~ ~~ ~~ ~~ ~~ (12,44) (13,78) (14,32) ~~ ~~ (17,11) (37,97) ~~ Element found: 97 Element not found
Binary Tree:Binary tree is the data structure to maintain data into memory of program. There exists many data structures, but they are chosen for usage on the basis of time consumed in insert/search/delete operations performed on data structures. Binary tree is one of the data structures that are efficient in insertion and searching operations. Binary tree works on O (logN) for insert/search/delete operations.Binary tree is basically tree in which each node can have two child nodes and each child node can itself be a small binary tree.
Example source code:
#include<stdlib.h>
#include<stdio.h>
struct bin_tree {
int data;
struct bin_tree * right, * left;
};
typedef struct bin_tree node;
void insert(node ** tree, int val)
{
node *temp = NULL;
if(!(*tree))
{
temp = (node *)malloc(sizeof(node));
temp->left = temp->right = NULL;
temp->data = val;
*tree = temp;
return;
}
if(val < (*tree)->data)
{
insert(&(*tree)->left, val);
}
else if(val > (*tree)->data)
{
insert(&(*tree)->right, val);
}
}
void print_preorder(node * tree)
{
if (tree)
{
printf("%d\n",tree->data);
print_preorder(tree->left);
print_preorder(tree->right);
}
}
void print_inorder(node * tree)
{
if (tree)
{
print_inorder(tree->left);
printf("%d\n",tree->data);
print_inorder(tree->right);
}
}
void print_postorder(node * tree)
{
if (tree)
{
print_postorder(tree->left);
print_postorder(tree->right);
printf("%d\n",tree->data);
}
}
void deltree(node * tree)
{
if (tree)
{
deltree(tree->left);
deltree(tree->right);
free(tree);
}
}
node* search(node ** tree, int val)
{
if(!(*tree))
{
return NULL;
}
if(val < (*tree)->data)
{
search(&((*tree)->left), val);
}
else if(val > (*tree)->data)
{
search(&((*tree)->right), val);
}
else if(val == (*tree)->data)
{
return *tree;
}
}
void main()
{
node *root;
node *tmp;
//int i;
root = NULL;
/* Inserting nodes into tree */
insert(&root, 9);
insert(&root, 4);
insert(&root, 15);
insert(&root, 6);
insert(&root, 12);
insert(&root, 17);
insert(&root, 2);
/* Printing nodes of tree */
printf("Pre Order Display\n");
print_preorder(root);
printf("In Order Display\n");
print_inorder(root);
printf("Post Order Display\n");
print_postorder(root);
/* Search node into tree */
tmp = search(&root, 4);
if (tmp)
{
printf("Searched node=%d\n", tmp->data);
}
else
{
printf("Data Not found in tree.\n");
}
/* Deleting all nodes of tree */
deltree(root);
}
Output :
$./a.out Pre Order Display 9 4 2 6 15 12 17 In Order Display 2 4 6 9 12 15 17 Post Order Display 2 6 4 12 17 15 9
Searched node=4
Hashing Table Implementation in Blockchain
Hashing Table Implementation in Blockchain:
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 good example is Bitcoin’s Secure Hashing Algorithm 256 (commonly shortened to SHA-256). Hashing using SHA-256 always gives an output result of a fixed length, which has a 256-bits length (the output is 32 bytes). This is always the case whether the transaction is just a single word or a complex transaction with huge amounts of data. What this means is that keeping track of a transaction becomes easier when you can recall/trace the hash. The size of the hash will depend on the hash function utilized, but the out using a particular hashing algorithm will be of a specific size.
Example:
When you take a YouTube video of say 50 megabytes and hash it using SHA-256, the output will be a hash of 256-bits in length. Similarly, if you take a text message of 5 kilobytes, the output hash will still be 256-bits. The only difference between the two will be the hash pattern. Let’s summarize the above information as follows: Hashing is the umbrella term for Cryptographic hash functions
Cryptographic hash functions
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 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 (we will get to that in a moment).
Characteristics of cryptographic hash functions
For a cryptographic hash function to be considered secure, it has to portray certain characteristics or properties. It is these properties that make the hash function suitable for cryptocurrencies like Bitcoin or Ethereum that utilize blockchain technology. Let me explain each one in simple terms for us all.
Deterministic
A hash function needs to have a fixed or specific output. What this means is that it doesn’t matter what number of times you process a given input using a hash function; the result is always of the same length. The hashes will be random and of different patterns, but the same size/length. Why is this important? Imagine getting different results for every transaction you record. It simply means it will be impossible for you to keep track of every input data using the hash
Quick Computation
In blockchain technology, a good hash function would be one that performs quick computations for every data input. It may be difficult to find the input data for a hash, but computing or calculating the hash should be ideally very fast. For instance, you can have the hash result of a simple “hi” within a fraction of a second. Similarly, the hash of a very large file will be received within a fraction of a second.
Pre-image resistance
One of the important properties of secure cryptographic hash functions is they are one-way. Let’s take it this way: given a hash of a particular transaction, it should be virtually impossible or practically infeasible to determine the original input data using this output. This property lends a level of security to the blockchain. When given a particular hash, the only possible way of finding what the original input data is if you hashed all the possible combinations of inputs until you eventually hash the correct or corresponding input. However, because the input data is randomized, hashing it is practically impossible.
Different hashes for every input (Randomized)
Hash functions produce different outputs for every input, even if the input data differs by only a digit or letter. For instance, the hash of the word “Alpha” should be completely different from the hash of the word “Alpha1”. If the patterns were to be similar and differ only at the end, then deciphering them would be easy.
Collision resistant
Cryptographic hash functions are also supposed to have collision resistant properties. Collisions can occur in cases where a hash function gives similar outputs for different inputs. For example, if “pic1” is photo and “pic2” is a video, but a hash function produces the same output, then we call that a collision. Normally, this should not happen. However, it could be a result of a “Birthday Box”.
Cryptographic hash functions
- 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
Blockchains and Hashing - where is it used?
Hashing is applied in blockchain as seen in some of the examples used above. Here are more examples.
- Addresses on the blockchain are derived from hashing e.g. Bitcoin addresses use SHA2-256 and RIPEMD 160.
- Hashing helps in defining cryptographic signatures that help determine valid transactions.
- The hash of a transaction makes it easy to keep track of transactions on the blockchain. Instead of looking for a transaction that was the “1030th in block 14573”, it is easier just to copy the hash into a blockchain explorer from where you can view the transaction details.
- Hashing functions are crucial in crypto mining where a valid nonce is discovered by computing several hashes. This helps to form a consensus on the blockchain.
- The use of “hash of the data” helps to store large amounts of data on the blockchain. This data is time-stamped and can be hashed for future reference. It makes the permanent data storage less bulky or simply more economical.
- Hashrate- determining how fast and smoothly-running the mining process is. It is vital in determining difficulty levels during mining.
Conclusion
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.
Referention:
Komentar
Posting Komentar