# Hashing Technique - Simplified

Jun 10, 2021Hello, this video is about

## hashing

### technique

. The## hashing

### technique

is useful for search purposes now, before moving on to hashing, let's quickly look at some of the known search techniques. Here is a linear search, in this the elements must be arranged in a random array, not in any order. and the search time is of the order of n to search for any element we start searching the element from the left side of an array to the right side which means we will start from the initial index and the time is of the order of n seconds search.The method is binary search in this, the elements must be in ascending order, sorted, kept in a list maintained in an array and we always look for an element in the middle of a list and if the element is bigger, we go to the right side if It's like that. is smaller, we go to the left side, so the search time is the login order. The important thing is that the arrangement of elements in a linear search can be random but in a binary search it must be in the sorted order and the time complexity for linear search is of order N and binary search improves the search method and it makes it faster and it's of log n order, but a requirement here is that the elements must be sorted, so we have to spend some extra time sorting the elements, okay? we want a lookup method that takes constant time, so from n we have moved to login and from record n we want to move to order of 1, so this is the requirement that the hashing technique introduces, so let's see hash in hashing technique if there is a list.

The elements are given and the array space is provided, we have to enumerate, store the list of elements, then we store the element in its own index, we take the value of an element itself as an index and store it in the same index, so eight are stored. at eight and three it is created as index and stored in location 3, so now when you want to search for any key element, say 10, then we directly go to index 10 and see if the element is present or not, if we want search for key element 12, we go directly to index 2 and element c is present or not, so 12 is not found, so the search time is of the order of 1.

We have to go directly to that index and search for the element but the problem is that if I have one more element which is 50 then we have to store it at index 50 which means it may be very far away so to store this 50 we should have index 50 in the transmission, so a lot of space is wasted on this. If we want to reduce the time, we may have to waste a lot of memory for just a few elements. We need a very large size matrix where most of these pieces are empty to improve this technique or to improve this basic idea.

We adopt a mathematical model. We designed a mathematical model for hashing based on functions, so let's see below how it is modeled using mathematics mathematically, the list of elements we have we call key space and the place where we have to store them we call hash table. and we say that there is some function, say H of in the same way 3 is stored in 3: 13 H of 13 is 13, so 13 is stored in index 13, so we say that H of X equals X is a hash function that maps these key elements from space of keys to the hash table and we take this as an ideal hash function.

So this is the same case that we just saw and we just did it mathematically. If I have an index of 50, then I should have it. If I have a key element 50 then I should have index 15 in an array so I should have a very long hash table again the problem is the same a lot of space is wasted so if we see the properties of the functions , there are two types of functions, one to one and many to one, these are the two types of cardinality are followed by functions and H of X equal to X is a one to one function if we take any other function other than H of X equals Now we say that here this function is responsible for assigning the elements to their indexes, so we need to modify the function to efficiently use the space in the hash table, so we will try to modify the function, so here with here we take the hash function H of size as 10 here size can be we can take a hash table of any size so I am taking hash function: H of gives 8 so 8 is stored here 3 mod 10 is a 3 so it is stored here 13 mod 10 is also 3 so there is a collision and this is causing a collision now the problem is that when you change the hash function then there is a possibility that two or more elements are assigned at the same index and that is called collision now we have to solve this collision we have to solve this problem there are different methods to avoid collusion to avoid collision or to remove collusion we have different methods which are open hash under es i.e.

Nexis chaining and closed hashing, under which we have linear probing and quadratic probing, let's look at them one by one. The first method to resolve collusion is chaining in this method when we assign any key using the same hash function. The hash function is the same when we assign It will be assigned at 8, so it will not store the element in the hash table, but if we add this index, we will add a new string and in it we will insert the element. The chain is nothing more than a link. The rest 3 is assigned here so add a node to a string and insert 3. 13 is also assigned here so we will add a new node and there we will insert 13 so when there is a collision we will insert a key element in the same index in a string so all these elements are inserted at their indices inside a string now when I want to search for any key element say 13 then I should use H hash function of 13 is 13 the mod size is 313, mod 10 gives me 3, so go to index 3 and search for that element key element in a string at that particular index, so there may be more than one element, so we have to search it and chain the entire linked list, so that's it.

Now the time complexity of the hash will not be of the order of 1 it will be more than 1 but it will be better than logging and it will be faster than logging now let's see other methods let's see the next method linear probing in this hash function is H of x is equal to x size mod same hash function am take 8 is mapped to 8 3 is mapped to 313 is also mapped to the same location but there is a collusion so we store it in the next location 13 so in this method we simply we find the next free space and store the element in X free space, so what is this approach?

We must give the reasoning mathematically, so here the explanation that our actual hash function is the size of mod equal. a I where I take values 0 or 1 or 2 or so now when we use 13 and we have to insert 13 then we say H of 13 plus F of 0 mod 10 this gives us 3 but there is a collision so next we use the same hash function to a different value of I and find F from one more to 10 so we got dancer as 4 this is how the value is stored in the location for index 4 so we use this script X as a hash function and store the element if there is a collision then we take the next high value even if there is a collision again then we take the next value of I and so on now let's insert the rest of the elements 6 is a store in 6 and 4 there is a collision there is already some element there , so we store it in the following place and 10 is stored here now, when I have to search for any key element, let's say I am searching for 4, then I should use this hash function H of X equal to mod size X goes to that place but the element is not present there then I should look at the next location which is 4 yes it is found here so it is found at index 5 which means by using hash function I should go to index and start searching the element in the conservative locations if I have a key element if I have to search for the key element 24 then 24 plus 10 gives me index 4 when I go to index 4 24 is not present then I should move to the next location it is not present , the next location is not present, the next location is MD, so I have to stop and say that 24 is not found, so I can say that to search for any key element we have to use the hands function, go to that particular index. and start searching for the item until the item is found or the empty space is reached.

This is the method to search and again the time complexity will not be on the order of one, it will be more than one, but it will be better than logging in now. Linear probing causes grouping of elements. A group of items will be in one place in a consecutive location and will be allocated continuously, so this may cause a lot of time to search for any item, so to avoid grouping of items we introduce quadratic probing. so this is the same as linear probing where if I take the hash function then for this we also define a new function as dash of 1 2 and so on, so it is not f of is not equal to i F of I is equal to I squared, so the difference between linear probing is in linear probing a linear probing F of I is equal to I we take here but in quadratic probing f of I is equal to I squared we take that is the difference now when we try to map the key element eight is stored here three in the same place 13 4 is 0 there is a collision so for I as 1 will be stored in the next location next is 23 so let's find out for 23 H of 23 plus F of 0 mod 10 this gives 3 there is a collusion at location 3 there is a collision so H of 23 H of 23 plus F of 1 mod 10 so this is 3 plus 1 mod 10 is 4 in 4 there is also a collision so we find 23 H of 23 plus F of 2 mod 10 so this is 3 plus F of 2 is 4 mod 10 is a 7 so this 23 there is a collision here then it is stored at index 7, now you can see that the element is kept a few locations away, it is not very close to the elements that are colluding with 23, so there is a gap between the elements, so This will prevent grouping of elements and improve search time.

I hope you understood the hash. Thanks for watching this video.

If you have any copyright issue, please Contact