Hashing Table & Binary Tree

Before knowing about Hashing Table we first must understand what hashing is. Hashing is a technique used for storing and retrieving keys in a fast manner. In hashing, a string of characters are transformed into shorter length values or key that represents the original string of characters.

Example: "H"ello. H will be defined as the key to the string of characters and placed in to the Hash Table.

Hashing Table

Hashing Table is an array where we store the original string. The index of the table is the hashed key, the value is the original string.

Example: I[ ]       Value
                  0         alphabet
                  ...        ...
                  8         hello

There are many ways to define the key of a string, some of the important one are:
-Mid Square
-Division
-Folding
-Digit Extraction
-Rotating Hash

Mid Square
The string of characters are converted into numbers and squared. After being squared, the middle part of the value is extracted. Example: Key -> @(64) -> 64^2 -> 4"09"6 -> "09" is extracted.
Extracting the middle part can be easily done with mask and shift operations.

Division
The string is divided using the modulus operator. We take each character of the string and total it, then we use the modulus operator(we will be dividing it by 64). It is by far the simplest method to hash an integer x.
Example: "HELLO" -> 72(H) + 69(E) + 76(L) + 76(L) + 79(O) =  372 % 64 = 52.

Folding
Partition the string into each parts, then sum each parts to obtain the hash key.
Example: "HELLO" = 372 -> 37 + 2 = 39.

Digit Extraction
Extraction through a given digit. Example: 1976542 we take the xth digit, in this case we'll be using 2nd,3rd and 5th. That will give use 975 for our hash key.

Rotating Hash
Using any hash method, we then rotate the digits. Example: 12345 -> 54321.

What would we do if a collision happened. Example : The hash table I[1] already has "b"ounty, while we want to insert another string that is "b"elieve. There are two ways to deal with this situation, that is : Linear Probing and Chaining.

Linear Probing
Going back to the Example of having I[1] already filled with "b"ounty. We will insert "b"elieve into the next available Index that is I[2].

Chaining
In this method we will not be inserting the string "b"elieve into I[2]. Instead we will be inserting the string into a linked list node in I[1].

According to my research there are no difference in using Hash Table nor Blockchain. Both are reliable.

Binary Tree

Simply, binary tree is s rooted tree that has atmost two branches. Those two branches are distinguished as left and right. A branch that is cut off will be named a leaf.

Example: This binary tree's main root is the node 18, while the leaves are (9,12,23).

Linked List II

According to the material that has been passed on to me about Linked List. Here's what i can conclude from the materials:

Struct for previous and next

Code:

struct tnode node{
      int nim;
      tnode *next,*prev;
}*head,*tail,*curr;

Before learning the other type of Linked List we must understand how to Insert,Delete,Push,Pop the Data in the List.

Linked List: Insertion

Code:

struct tnode *node =

(struct tnode*) malloc (sizeof(struct tnode));

node->value = x;

node->next = head;

head = node;

Linked List: Delete

Code:

struct tnode *curr = head;

if ( head->value == x ) {

head = head->next;

free(curr);

}

Linked List: Push

Code:

void Push();

struct tnode *node = (struct *node) malloc(sizeof(struct node));

if(head==NULL){

      head = nim;

}else{

head->next=nim;

}

void PopHead();

//set global variable *temp;

struct tnode *node = (struct *node) malloc(sizeof(struct node));

      temp = head;

      head=temp->next;

      free(temp);

After learning how to Insert,Delete,Push,and Pop, we can now proceed to the other type of Linked List.

Double Linked List

In Double Linked List, every node has a pointer to it's previous and next node.

References: BinusMaya