Intro to Hash Table with Chaining

Hash table is a data structure that combines an array with a linked list. It takes the random access ability of an array and combines it with dynamism of linked list.

If implemented well we are basically taking all the advantages of both the data structure to get insertion,deletion and search in constant time.

Hash table is a combination of two things:

1.  Hash function: it returns a positive integer that is called hash code.
2. An Array: it is capable of storing data of the type we want to store

The basic idea of hash table is we take our data and run that data through the hash function, so the data is processed and return a number (called hash code) and with that number we just store the data we want to store in the data structure.

But how can we define our hash function? There is no one particular way to define a hash function. There are lot of good and bad hash function. And as we're trying to get the operation close to constant time we'll have to implement good hash function.

A good hash function should have:

• Use only the data being hashed -> we don't want to incorporate anything else other than the data
• Use all the data being hashed -> we want to use all of the data
• Be deterministic -> every time we pass the same data we should get the same hash code
• Uniformly distribute data -> data should be spread out through out the able
• Generate very different hash code for very similar data

Example of a hash table is:

In this we are taking a string ans adding ASCII value of each of the character and returning the sum mod the size of hashTable(i.e HASH_MAX) and that is our hash code and we are saving the string to that position of hash table.

But if there is two input first- "aaop" and second- "paoa" both of them will return the hash code 7 if we use the above hash function. So, which ever data will save in the hash table that will be overwritten by the later one. We call this problem collision.

Collision occurs when two pieces of data run through the same hash function and returns the same hash code.

But we want to save both the data into the hash table. So, how do we do it?  one way can be linear probing.

In linear probing, if we have a collision, we try to place data in the next consecutive element in the array until we find a vacancy.So, if we can not put any of the two strings in hash code 7 then we'll try to put it in 8 and if that is also not vacant we'll increase hash code until we find it. That means  we are stretching away from constant time and leaning toward order of n with this process, and this problem is called clustering.

So, linear probing is subject to a problem called clustering. That means once there is a miss, two adjacent cells will contain data, making more likely that in the future cluster will grow.

The other problem is in our code we are still have room for specific amount of string(i.e HASH_MAX) that means we are still limited. We can only store as much data as we have location in the array.

So, how can we solve these problems? This is where chaining comes in play. And this is where we bring the linked list back to the picture. What if each element of array holding one piece of data, it held multiple pieces of data?

But that doesn't make sense, we know each element of array can only one piece of data of a data type. But what if that data type is a linked list?So, what if every element of an array is a pointer to the head of a linked list? Then we can build these linked list and grow them arbitrarily.

So, we start to grow these chains out of the array locations. Now we can store an arbitrary amount of data into the hash table without ever running into collision.

And we know that when we insert something in the front of the linked list, that is a O(1) operation.

But we know search or find function in linked list takes O(n) time. But instead of having one linked list, we now have HASH_MAX(i.e size of array)  number  of linked list where HASH_MAX can be 10 or 1000  whatever the size of array is, then time complexity is O(n/10) or O(n/1000). 

We know theoretically we disregard  constants when we measure complexity, but in real world these things matter. We will notice this happens to run 10 times or 1000 times faster, because we're distributing one long chain (linked list) across the 1000 smaller chains.So, each time we search through one of those chains we can ignore the other 999 chains we don't care about.

 As we are focusing on only one linked list which on average going to be thousand times shorter. So, we still are tending toward the average case of being constant time.

 Chaining works like this:

We take the hash code and make it point to the node which contains the string. And in collision i.e if we try to put "paoa" in the hash table:

We make a new node with that data and put it in end of the list that was pointed by 7.

 I will show the implementation in my next post.

Linked List Functions Implementation

In my last post about linked list I talked about how we can insert elements in linked list and how to print those elements. But there are a lot of other functions that we can perform on linked list, I am listing some them below and their functionalities:
                   
      pushFront() -> adds element to the front of the list
      topFront() -> returns the data of the first element
      popFront() -> removes first element of the list
      pushBack() -> adds element at the end of the list
      popBack() -> removes the last element from the list
      find(data) -> returns true or false depending on weather the value exists in the list or not
      erase(data) -> removes element  from the list
      empty() -> returns boolean value depending on weather the list is empty or not
      addsBefore(node,data) -> adds element before a node

Now I'll implement some of these functions.

pushFront(): 

To push an element in the front we'll just have to create a new node insert the data and initialize it's next pointer with head that means new node will point to previous first elements   and then initialize head with currentNode because now this is the first element. As all of these operations takes constant time, time complexity of pushFront() is order of 1 i.e. O(1).

topFront():

To get the data of the list we'll just have to return data of head. It takes constant time.

popFront():

To delete the first element we'll just have to delete the first element and update the head pointer with the next elements reference. It takes constant time.

 pushBack():

To push elements at the end of the list is similar to pushFront only difference is this time we'll update tmp because that is what we're using to keep track of the tail of the list.

find(data):

To find any data we'll have to traverse the list until we find it or if it is not on the list then till the end of list. In worst case this takes order of n  i.e. O(n) time.
Full Source Code in C++
Full Source Code in Python3

Intro to Linked List

Linked list is linear data structure where each element consists of two things: data and information for next node.

To implement Linked list in C++ first we'll make a class called Node that will have two fields.

*next pointer will contain the reference for next node and data will have the value. After this will create three Node type global pointers.

Now to insert nodes at the end of linked list we'll create a function called insert_elements(). This function will take the input value as the parameter.

 We have created a new node by writing: "new Node" and initialized it to newNode. That  means now the pointer newNode is pointing to the new node.

At first we have to check if head is equal to NULL or not. If there is no element in linked list, head will be NULL. So, we'll initialize it with newNode and we'll also initialize tmp with newNode. Now all three pointers is pointing to the same node and as we're not initializing the *next pointer it points to NULL.

If the linked list is not empty that means the head is not NULL, then we'll just insert the value in the variable data and initialize the  previous nodes *next pointer to the current node and initialze *tmp to now point at current node.

If we want to print the values inserted in the linked list we can create a function print_elements().

we'll make a node type pointer that points to the head that means the first node of the linked list and we'll iterate loop until currentNode is NULL and print the data of each node. currentNode will be NULL when we reach the last node.
Full Source code 

Segment Tree

Segment tree is basically taking the recursion pattern of merge sort and turning it into data structure. So, before we start with segment tree we have to know how merge sort works. If we see the diagram below;

So, what we are doing here is- we are recursing down the array by diving it in half and then we are recursing back up and merging the sorted array. On each level while recursing down it take linear amount of time because we are loop over the array and diving in half which takes linear amount of time, then while recursing up while combing the sorted list in liniear amount of time. So we can use this information to analyze mergesort runtime. If we see the width of the array we get at the end of splitting the array , we get the width as n so, that’a O(n) and the height of the array is log n because we are splitting the array in half each time and log of something basically means how many time we can diving that in half. Now if we combine both width and height we get the area a nlog n that means the complexity cof merge sort is  O(nlog n).

Now that we know how merge sort works the question is -how can we turn this into data structure? What we’ll do is we’ll consider each array of the merge sort as different nodes and use the nodes to form a tree. So, I am taking the sequence of the recursion and turning it into data structure. The tree will look like below:

So, as we can see our array has 6 element so the root node consists of all the elements from 0-5 then we are splitting the array in half so the left node consists of elements 0-2 and right node consists of elements 3-5 then keep diving those till the end so the tree looks like below

:

If you notice, I have drawn the same tree as before but here instead of putting the segments of array I’ve just put the range of those segments . So, segment tree is useful when we are solving range query type of problem. For example, If you are given an array and you have to find out minimum element of a particular range, let’s say the array is :

If we try to solve this using linear search the if we have n element and 1 query time complexity will be O(n*1) that means O(n).So, if we have q queries the complexity will be O(nQ) . Now if n<=10^5 and q<=10^5 and the time limit is 1second, with linear search we’ll get a TLE. But if we use segment tree, that we’ll help us reducing the time complexity. For this problem we’ll draw a similar tree like before.

But in each node we’ll save the minimum element of the entire range that node. So, the root node will contain minimum element of the range [0-5] and likewise other nodes will contain minimum element of it’s range. And we’ll start storing  the minimum value from the leaf nodes because the range size of the leaf is 1 from each node, so the element of that index itself. First we’ll store the number 8 node where range is 0-0 so we have to just put the element of 0^th index which is 1, then in range 1-1 we’ll store element of index 1 which is 3, likewise we’ll fill all the leaf nodes with there values. Now we’ll move on to the parent nodes of the leafs. First we’ll store the minim of range [0-1] which is the minimum of range [0,0] and [1,1] that is 1, then minimum of range [3-4] is minimum of range[3.3] and [3.4] which is -2. Then we’ll store the minimum of range [3-5] which is -2 , minimum of range [0-2] is 1 and minimum of range [0-5] is -2. Now that we’ve build our tree .At first we’ve filled the leaf nodes and then in a bottom up way we’ve filled the rest of the nodes.

Now we’ll see how to build this tree using code. We will use an array to build this tree. If you have noticed I have numbered the nodes in the tree and where 10 and 11 is missing because node 5 can’t be divided further. The numbering of the nodes is done so that we can make a relationship between parent and child nodes. So, node 1’s children are 2 and 3, node 2’s children are 4 and 5, node 3’s children are 6 and 7. Can you see a pattern here? When we are getting node i it’s children are 2*I and 2*i+1 and if we have children and want to find out it’s parent then if the child node is i, the parent node will be i/2 because for children 2,3 we get parent 1 likewise children 4,5 we get parent 2 . By using these notation we can store the children node in the array. So, the array for our tree we’ll look like this:

The nodes are not in the tree I have kept those indexes empty. So for n elements we’ll need total   2n-1  nodes in the tree but when my allocating array that is larger than 2n-1 because we re also taking some extra indexes which are empty, so the exact size of the array will be 2*(2^ceil(log n))+1 ≈  4*n+1, this is the maximum size needed to build a tree of size n.

Function for  building the tree is:

Now that we have made the segment tree, we have to do the query in the tree. In this case we are finding the minimum element in a range. So, when the query comes, there will be three cases .

To know the first case let’s see an example- If user does a query for range [0,5] then in the tree the root node is the range [0,5] and it contains -2 that means we’ve got the output -2. Case is:

1)This is complete overlap because the  node range [0,5] is completely inside the query range[0,5], so in complete overlap we just have to return tree[index], that’s how we get -2 as output

To know the second case and third case let’s see an example- If user does a query for range [0,2] then in the tree the root node is the range [0,5] that means we’ve partial overlap Case is:

2)Partial  overlap because the  query  range [0,2] is partially inside the root node  range[0,5], So, in partial overlap we’ll go to both sides left and right. First we’ll go to left in left we get the node range[0,2]and our query range is also [0,2] this is complete overlap so we’ll return the value which this node contains which is 1.

 Now we’ll go to the right node the range of which is [3-5] and query range is [0,2] so we’ve got the third case that is no overlap.

                                        

3) When the query range is outside the node range we get no overlap, in this case we’ll return infinity

So, the minimum of 1 and infinity we’ll be 1. And if you see our input array, the minimum element between [0,2] is also 1 that means we’re getting the right output.

So, the three cases for segment tree is:

          1) Complete overlap where output is element of that node

          2) Partial overlap where we have to find output by going both sides

          3) No overlap, in this case we’ll return infinity

Now let’s see the code for the query: