Hash Tables and Binary Tree

Hashing and Hash Tables

Hashing

Hashing is the transformation of a string of characters into a shorter length value or key that represents the original string. Hashing is used to index and retrieve items in a database because it is faster to find item using the shorter hashed key than to find it using the original value. such function is called hash function which come with different forms and each will gives different result.

for example you have a input of integers such as "11", "12", "13", "14" and we place them in an array.

List = [11, 12, 13, 14]

If we want to find the number "14" it will take time complexity of O(n). What if we have a huge amount of data stored, it will be to long to find a specific number. but with hashing and hash table with will only took time complexity of O(1). 

Let the hash function H(x) maps the value X at the index in x%10 in an array. It will be shown:

The same happen if the inputted data is a string then it will return the index of the string by minus it with ascii of  'a' and 'A' for uppercase.

Hash Function

There are many different ways to hash and there are 5 most common and important method for constructing hash functions.

1. Mid-square

in this technique, a seed value is taken and it is squared. Then, some digits from the middle are extracted. These extracted digits form a number which is taken as the new seed.

2. Division

the key will be modulo(%) and using the remainder for the table size.

3. Folding

Divide the key 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 part. 

Ex.

Given a hash table 100 location 

key = 83781

parts 83, 78, 1

folding = 83 + 78 + 1 = 162

hash key = 162%100 (the max size array that we set, 100) = 62

4. Digit Extraction

We extract the 1st, 3rd and 5th digit of the key.

Ex. 

key = 12492, 1st = 1, 3rd = 4,  5th = 2

hash key = 142

5. Rotation Hash

Basically reverse the hash hey after using the 4 other method. Using the example in "digit extraction" having a hash key of 142, with this function the hash key = 241.

Collisions

Collisions happens when we have 2 key with the same hash key. if we hash using the first character example we have an string of {"", "bird", "chair", "dance"} and we want to add a string of "ball" it will be place in the first index. But first index has already "bird" occupy it.

There are 2 ways to handle this situation.

1. Linear Probing

search the next empty slot and put the string there

2. Chaining

put the string in a slot as a chained list (linked list).

index             value

   0                 null

   1                 bird->ball->null

   2                 chair->null

   3                 dance->null

Here is an example of hash and chaining integers
Example when we run the code:

For characters it is the same but different hash function and include 2 more header file

Example of Blockchain Hashing

A basic example of hashing is used to digitally sign a piece of software so that it is available for download. To do this you need a hash of the script of the program you want to download. You also need a digital signature, which gets hashed as well.

Once the input data has been hashed the software is encrypted and it can be downloaded. So, when someone downloads software, the browser needs to decrypt the file and check the two unique hash values. The browser then runs the same hash function, using the same algorithm and hashes both the file and the signature again. If the browser successfully produces the same hash value, it can confirm that both the signature and the file are authentic and that have not been altered.

source: hedgetrade/what is blockchain hashing.

The Hash Algorithms 

Hash algorithms are computational functions. The process condenses input data into a fixed size, the resulting is an output that is a hash or a hash value. Hashes identify, compare or run calculations against files and strings of data. When attempting to add to an extent blockchain, the program must solve for the target-hash in order for it to reach acceptance as a new block.

• Hashes are deterministic and pre-image resistant:

• Deterministic: the outcome of a particular set of data input will always have the same result. This makes it possible to keep track of transactions and nearly impossible to recreate the input from the output data (or pre-image resistant).  

• SHA-256:

• This produces a 256-bit hash. Given that data is so large, that there are too many possible outcomes to compare hashes to and attempt to solve backward. So if one wanted to try to solve for a target hash, this they would need to begin with a random hash a sequence -then test it against the target hash – this would take a nearly incalculable amount of times.

• Collision Resistance: SHA-256 is collision resistant because of the large amount of data, so arriving the same target-hash at the same time is nearly impossible. This is also a result of using a target with high min-entropy.

source: hedgetrade/what is blockchain hashing.

Advantage of using hash in Blockchain

Advantage of implement hash in blockchain is that they are more secure, fast and there are no collision. It also help to determine valid transaction preventing hacker. There are millions of nodes and each requires verification. Making a change will disturb the output making it out of sync and will alert and reject the output. This is why Hashing blockchain is secure guarantee.

Binary Tree

Binary tree is a rooted tree data structure in which each node has at most 2 children.

There are 4 types of binary tree

1. Perfected Binary Tree

Binary tree which every level are at the same depth.

2. Complete Binary Tree

Binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. A perfected binary tree is a complete binary tree.

3. Skewed Binary Tree

Binary tree i which each node has at most one child.

4. Balance Binary Tree

Binary tree in which no leaf is much father away from the root than any other leaf.