.png)
Mobiprep has created last-minute notes for all topics of Hashing and Searching to help you with the revision of concepts for your university examinations. So let’s get started with the lecture notes on Hashing and Searching.
Data Structure
Linked List
Doubly Linked List
Circular Linked List
Queues
Stacks
Hashing and Searching
Sorting
Our team has curated a list of the most important questions asked in universities such as DU, DTU, VIT, SRM, IP, Pune University, Manipal University, and many more. The questions are created from the previous year's question papers of colleges and universities.
Question 1 - Explain Linear Search with example?
Answer - In linear search we simply search for the elements in array. We match the search key value to the each elements in the array. We start searching from the 0 index and continue until match is found. When we find a match we say search is successful and return the index. Lets understand with the example below.
Code:
Linear_Search (a , n , item , loc)
Begin
for i = 0 to (n - 1) by 1 do
if (a[i] = item) then
set loc = i
Exit
endif
endfor
set loc = -1
End
Example:
Source:pinterest
In above example we are looking for 50.first we match 50 with 10,but they do not match.so we compare 13,50.They do not match. We continue this process. At index 4 50,50 are matched. Here search is successful and we get index 4 in return which represents the position of element.
Question 2 - Explain Binary Search with example?
Answer - Binary search is the searching technique can be applied only for the sorted arrays.so if you want to use binary search algorithm for searching first sort the given array. For searching element in array first we find the mid of array. Then we match the element at the mid with the element to be searched .If match is successful search is complete otherwise we have idea that the element to be searched is smaller or greater than the mid. If greater we search in the right part else we search in left part. When we search in left part we update last to mid-1 and if in right part we update first to mid+1.then again we find mid and continue the search.
Code:
Procedure binary_search
A ← sorted array
n ← size of array
x ← value to be searched
Set lowerBound = 1
Set upperBound = n
while x not found
if upperBound < lowerBound
EXIT: x does not exists.
set midPoint = lowerBound + ( upperBound - lowerBound ) / 2
if A[midPoint] < x
set lowerBound = midPoint + 1
if A[midPoint] > x
set upperBound = midPoint - 1
if A[midPoint] = x
EXIT: x found at location midPoint
end while
end procedure
Example:
Source:study.com
In this example we are looking for 46.
Step 1:first mid value is 5,at 5 46 is not present.
Step 2:But 46>31 so,we update L=5+1=6.
Step 3:Now we find new mid=6+10/2=8.
Step 4:At 8 46 is not present so again 46>42,mid=9.
Step 5:Now at 9 we find 46.
Hence search is successful and index 9 is returned.
Question 3 - What is hashing and define different hash functions.
Answer - Hashing is a technique used for searching elements by using key values. In hashing by using key comparisons searching is done in less time. Average case time complexity for hashing is O(1) and worst case time complexity is O(n).
The following mentioned are some of the hash functions:
Division: In this function we need the size of table. We modulo divide each data by the size of table and whatever reminder we get we put the data in there. suppose data is 54,65,22,18. And table size is 10.so we got reminders as 4,5,2,8.So 54 goes in 4,65 in 5,22 in 2 and 18 in 8.
In this method firstly key is squared and then mid part of the result is taken as the index.
Digit folding: In digit folding we divide data into some group of digits and simply add them to get the index. Ex.data is 45698,we divide them as 45,69,8.Now 45+69+8=122.Now 122 is our index.
Question 4 - What is hashing collision and how to handle it?
Answer - When we get the same hash key for different data by hash function then it is called as hashing collision. In simple words two different data can not be placed in same place when such condition occurs it is called as hashing collision. There are different strategies to handle collision.
Chaining: In chaining when collision occurs we have linked list in which we store the data which is collided. Suppose we have data as 44,65,22,84.now by using hash function we get indexes as 4,5,2,4.So collision is for index 4 due to 44 and 64.So we keep this collided data in linked list.
Linear probing: In linear probing when collision occurs we search for the next empty place and place the data there. suppose we have data as 44,65,22,84.now by using hash function we get indexes as 4,5,2,4.So collision is for index 4 due to 44 and 64.So 44 is at 4,65 is at 5 ,22 is at 2.and if 6 is empty 84 will go to 6 due to collision.
Quadratic probing: Solving of clustering problem is done in Quadratic probing. In this method the hash function is defined by the H(key)=(H(key)+x*x)%table size.
Double hashing: Two hash function are used when there is an occurrence of collision and this is nothing but the double hashing method. In this method 1 hash function is simple as same as division method. But for the second hash function there are rules. It must never evaluate to zero. Must sure about the buckets, that they are probed. The hash functions for this technique are: H1(key)=key % table size ,H2(key)=P-(key mod P)Where, p is a prime number which should be taken smaller than the size of a hash table.
Using these techniques we can handle most of the collisions.
Question 5 - Explain linear probing with example?
Answer - In linear probing when collision occurs we search for the next empty place and place the data there. suppose we have data as 44,65,22,84.now by using hash function we get indexes as 4,5,2,4.So collision is for index 4 due to 44 and 64.So 44 is at 4,65 is at 5 ,22 is at 2.and Due to collision at 4 84 should go in 5 but 5 is already occupied by 65 so we check if 6 is empty .84 will go to 6 due to collision.
Index | Data |
0 | Null |
1 | Null |
2 | 22 |
3 | Null |
4 | 45 |
5 | 65 |
6 | 84 |
7 | Null |
8 | Null |
9 | Null |
Question 6 - Explain Quadratic probing with example?
Answer - This is a method in which solving of clustering problem is done. In this method the hash function is defined by the H(key)=(H(key)+x*x)%table size. Let us consider we have to insert following elements that are:-67, 90,55,17,49.In this we can see if we insert 67, 90, and 55 it can be inserted easily but at case of 17 hash function is used in such a manner that :-(17+0*0)%10=17 (when x=0 it provide the index value 7 only) by making the increment in value of x. let x =1 so (17+1*1)%10=8.in this case bucket 8 is empty hence we will place 17 at index 8.
Index | Data |
0 | 90 |
1 | Null |
2 | Null |
3 | Null |
4 | Null |
5 | 55 |
6 | Null |
7 | 67 |
8 | 17 |
9 | 49 |
Question 7 - Explain Double hashing with example?
Answer - Two hash function are used when there is an occurrence of collision in double hashing . In this method 1 hash function is simple as same as division method. But for the second hash function there are rules. It must never evaluate to zero. Must sure about the buckets, that they are probed. The hash functions for this technique are: H1(key)=key % table size ,H2(key)=P-(key mod P)Where, p is a prime number which should be taken smaller than the size of a hash table. Let us consider we have to insert 67, 90,55,17,49. In this we can see 67, 90 and 55 can be inserted in a hash table by using first hash function but in case of 17 again the bucket is full and in this case we have to use the second hash function which is H2(key)=P-(key mode P) here p is a prime number which should be taken smaller than the hash table so value of p will be the 7.i.e. H2(17)=7-(17%7)=7-3=4 that means we have to take 4 jumps for placing the 17. Therefore 17 will be placed at index 1.
Index | Data |
0 | 90 |
1 | 70 |
2 | Null |
3 | Null |
4 | Null |
5 | 55 |
6 | Null |
7 | 67 |
8 | Null |
9 | 49 |
Question 8 - What are the time complexities of linear and binary search?
Answer - In the best case, The element being searched may be found at the first position. Thus in best case, linear search algorithm takes O(1).The element being searched may be present at the last position or not present in array in worst case. In worst case, linear search algorithm takes O(n). Time complexity of binary search is log2(n) because we keep dividing the arrays while searching.
Comments