in Education by
Which of the following scenarios leads to linear running time for a random search hit in a linear-probing hash table? (a) All keys hash to same index (b) All keys hash to different indices (c) All keys hash to an even-numbered index (d) All keys hash to different even-numbered indices The question was posed to me in an internship interview. I'd like to ask this question from Hashing techniques topic in division Indexing and Hashing of Database Management

1 Answer

0 votes
by
The correct choice is (a) All keys hash to same index Easiest explanation - If all keys hash to the same location then the i-th inserted key would need i lookups to be found. The probability of looking up i-th key is 1/n (since it’s random). If you know some probability it’s trivial to show that such lookups have linear time.

Related questions

0 votes
    A hash table can store a maximum of 10 records, currently there are records in location 1, 3,4,7, ... Answers, Database Interview Questions and Answers for Freshers and Experience...
asked Oct 11, 2021 in Education by JackTerrance
0 votes
    Are there any specific scenarios to use Liferay search container over Dandelion data tables framework,when Data ... for Interview, JavaScript MCQ (Multiple Choice Questions)...
asked Jul 8, 2022 in Education by JackTerrance
0 votes
    Write C program that use both recursive and non recursive functions to perform Linear search for a Key value in a given list. Select the correct answer from above options...
asked Dec 17, 2021 in Education by JackTerrance
0 votes
    The complexity of a linear search algorithm is (a) O(n) (b) O(log n) (c) O(n2) (d) ... Questions and Answers, Database Interview Questions and Answers for Freshers and Experience...
asked Oct 11, 2021 in Education by JackTerrance
0 votes
    The Worst case occur in linear search algorithm when (a) Item is somewhere in the middle of the array ... , Database Interview Questions and Answers for Freshers and Experience...
asked Oct 11, 2021 in Education by JackTerrance
0 votes
    The Average case occur in linear search algorithm (a) When Item is somewhere in the middle of the ... from Sorting in portion Query Processing Techniques of Database Management...
asked Oct 10, 2021 in Education by JackTerrance
0 votes
    which of the scenarios can we overcome by using BPM? option a) Theft b)Time wastage c) None of these Select the correct answer from above options...
asked Dec 19, 2021 in Education by JackTerrance
0 votes
    which of the scenarios can we overcome by using BPM? option a) Theft b)Time wastage c) None of these Select the correct answer from above options...
asked Dec 18, 2021 in Education by JackTerrance
0 votes
    What is the best definition of a collision in a hash table? (a) Two entries are identical except ... Answers, Database Interview Questions and Answers for Freshers and Experience...
asked Oct 11, 2021 in Education by JackTerrance
0 votes
    If h is any hashing function and is used to hash n keys in to a table of size m, where n...
asked Oct 11, 2021 in Education by JackTerrance
0 votes
0 votes
    After reading the chapter, I know these points: I know that data gets highlighted after being selected. I know ... entry and editing. Select the correct answer from above options...
asked Nov 26, 2021 in Education by JackTerrance
...