Hashing & Binary Tree

What is Hashing?

- Hashing is the process of mapping large amount of data item to smaller table with the help of hashing function for faster access of elements. The efficiency of mapping depends of the efficiency of the hash function used.

Example above, if we want to find Ada, Ada is at the 8th index and we can say that myData = Array[8]; but that's only possible if we know the exact position of Ada in the array. Well, what if we don't?

Using ASCII we get:

- Mia – M (77) i(105) a(97), 77+105+97=279, 279%11=4

We added all the ASCII value we got and then found the remainder by dividing it with the total amount of data. We do that for all the data we have in our list and we put them into their respective indexes. It will look like this:

Index Number = The sum of the ASCII codes % Size of Array

Now if we find Ada we just sum up all the ASCII codes which is 262 and modulo it with 11 (262%11), and we get the index number 9. myData=Array[9].

What if a collision happens? For example we have 2 elements 40 and 70, and the size of our array is 10. They both has the same results which is 0. We can solve this using Linear Probing. What is Linear Probing?

In the array above, the index 0 is already taken by 70, so where will 40 go?

Using Linear Probing : Index Number = (Index Number + 1) % Size of Array, so we get (0+1)%10=1. As we can see that the index number 1 is taken by 31 in the array above so we apply the formula again and get (1+1)%10=2. So we place 40 in the index number 2

In the picture above, rather than passing them to a space which is empty we have linked them using linked list so it's way much easier and faster to access the data that we want to access.

Trees

Unlike Arrays, Linked Lists, Stack and Queues, which are linear data structures, Trees are hierarchical data structures.

-Node number 1 is called Root

-Node number 2 and 3 will be called the Children of node 1 and 1 is the Parent for 2 and 3

-Node 2 is the Parent for 4 and 5 and so on.

-Node 14 is called a Leaves, Leaves are elements with no Children

Binary Tree

Binary Tree is a tree with maximum number number of children is 2. Not more than 2. Since each element in a binary tree can have only 2 children, we typically name them the left and right child.

We usually declare a binary tree struct in C like this :

struct binaryTree {

int data;

struct binaryTree *left; //left side of the tree

struct binaryTree *right; //right side of the tree

};

Helpful links:

-https://youtu.be/KyUTuwz_b7Q

-https://www.geeksforgeeks.org/binary-tree-set-1-introduction/