Suppose we are given $n$ keys, $m$ hash table slots, and two simple uniform hash functions $h_1$ and $h_2$. Further suppose our hashing scheme uses $h_1$ for the odd keys and $h_2$ for the even keys. What is the expected number of keys in a slot?
Each key lands in any given slot with probability $1/m$ under simple uniform hashing, regardless of which function is used. The expected number per slot is therefore $n/m$.
More Searching, Sorting and Hashing questions
GATE 2021 CS (CS1) Q19– Consider the following array: [23, 32, 45, 69, 72, 73, 89, 97]. Which algorithm out of the…
GATE 2019 CS Q30– An array of 25 distinct elements is to be sorted using quicksort. Assume that the pivot…
GATE 2019 CS Q50– Consider the following statements: I. The smallest element in a max-heap is always at a…
GATE 2015 CS (CS1) Q14– Which one of the following is the recurrence equation for the worst case time complexity…
GATE 2016 CS (CS1) Q23– The worst case running times of Insertion sort, Merge sort and Quick sort, respectively,…
GATE 2017 CS (CS1) Q58– Let A be an array of 31 numbers consisting of a sequence of 0's followed by a sequence of…