Rangkuman UAS

Rangkuman Data Structure Session 9 (10 Maret 2020)

A. Outline:

1. Hashing
2. Hash Table
3. Hash Function
4. Tree/Binary Tree Introduction
5. Hashing Implementation in Block Chain

B. Summary

1. Hashing

Hashing is a technique used for storing and retrieving keys in a rapid manner. In hashing, a string of characters are transformed into a usually 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 shorter hashed key than to find it using the original value.

2. Hash Table

Hash table is a table (array) where we store the original string. Index of the table is the hashed key while the value is the original string.

example:

Supposed we want to store 5 string: define, float, exp, char, atan into a hash table with size 26. The hash function we will use is “transform the first character of each string into a number between 0..25” (a will be 0, b will be 1, c will be 2, …, z will be 25).

explanation:

atan is stored in h[0] because a is 0. char is stored in h[2] because c is 2. define is stored in h[3] because d is 3. and so on..

We only consider the first character of each string.

h[ ]	Value
0	atan
1
2	char
3	define
4	exp
5	float
6
…
25

3. Hash Function

a. Mid-Square

Square the string/identifier and then using an appropriate number of bits from the middle of the square to obtain the hash-key.  If the key is a string, it is converted to a number. 

Steps:

1.  Square the value of the key. (k2)
2.  Extract the middle r bits of the result obtained in Step 1

Function : h(k) = s

• k = key
• s = the hash key obtained by selecting r bits from k2

b. Division

Divide the string/identifier by using the modulus operator.

Function: h(z) = z mod M

• z  = key
• M = the value using to divide the key, usually using a prime number, the table size or the size of memory used.

c. Folding

Partition the string/identifier into several parts, then add the parts together to obtain the hash key

Steps:

1. Divide the key value into a number of parts
2. Add the individual part (usually the last carry is ignored)

d. Digit Extraction

A predefined digit of the given number is considered as the hash address. 

Example:

Consider x = 14,568. If we extract the 1st, 3rd, and 5th digit, we will get a hash code of : 158. 

e. Rotating Hash

Use any hash method (such as division or mid-square method). After getting the hash code/address from the hash method, do rotation. Rotation is performed by shifting the digits to get a new hash address.

Example:

Given hash address = 20021

Rotation result: 12002 (fold the digits)

4. Tree/Binary Tree Introduction

A tree is a non-linear data structure that represents the hierarchical relationships among the data objects. Binary tree is a rooted tree data structure in which each node has at most two children. Those two children usually distinguished as left child and right child. Node which doesn’t have any child is called leaf.

A Binary Tree node contains following parts:

1. Data
2. Pointer to left child
3. Pointer to right child

5. Hashing Implementation In Block Chain

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

another 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.

SOURCE:

• https://www.tutorialspoint.com/data_structures_algorithms/hash_data_structure.htm
• https://www.geeksforgeeks.org/binary-tree-data-structure/
• https://www.onlinehashcrack.com/how-to-hashing-in-blockchain-explained.php
• PPT Session 9 Data Structure