Use app×
Join Bloom Tuition
One on One Online Tuition
JEE MAIN 2025 Foundation Course
NEET 2025 Foundation Course
CLASS 12 FOUNDATION COURSE
CLASS 10 FOUNDATION COURSE
CLASS 9 FOUNDATION COURSE
CLASS 8 FOUNDATION COURSE
0 votes
934 views
in Computer by (69.2k points)

Explain the functionality of linear and quadratic probing with respect to hashing technique. 

1 Answer

+1 vote
by (69.7k points)
selected by
 
Best answer

Linear Probing: The simplest way to resolve a collision is to start with the hash address and do a sequential search through the table for an empty location. The idea is to place the record in the next available position in the array. This method is called linear probing. An empty record is indicated by a special value called null. The array should be considered circular, so that when the last location is reached the search proceeds to the first record of the array. An unoccupied record location is always found using this method if atleast one is available; otherwise, the search halts unsuccessfully after scanning all locations. The major drawback of the linear probe method is that of clustering.

When the table is initially empty, it is equally likely that a new record will be inserted in any of the empty position but when the list becomes half full, records start to appear in long strings of adjacent positions with gaps between the strings. Therefore the search to find an empty position becomes longer.

Quadratic probing: In the above case when the first insertion is made the probability of new element being inserted in a particular position is 1/n where n is the size of the array. At the time of second insertion the probability becomes 2/n and so on for the kth insertion the probability is k/n, which is k times as compared to any other remaining unoccupied position. Thus to overcome the phenomenon of long sequence of occupied positions to become even longer we use quadratic rehash, in this method if there is a collision at hash address h, this method probes the array at locations h+1, h+4, h+9, ... That is (h(key) +i2 % hash size) for i=1,2,... gives the ith hash of h. 

Welcome to Sarthaks eConnect: A unique platform where students can interact with teachers/experts/students to get solutions to their queries. Students (upto class 10+2) preparing for All Government Exams, CBSE Board Exam, ICSE Board Exam, State Board Exam, JEE (Mains+Advance) and NEET can ask questions from any subject and get quick answers by subject teachers/ experts/mentors/students.

Categories

...