Which one of the following hash functions on integers will distribute keys most uniformly over 10 buckets numbered 0 to 9 for i ranging from 0 to 2020?a)h(i) =i2mod 10b)h(i) =i3mod 10c)h(i) = (11 ∗ i2) mod 10d)h(i) = (12 ∗ i) mod 10Correct answer is option 'B'. Can you explain this answer?

Question

Which one of the following hash functions on integers will distribute keys most uniformly over 10 buckets numbered 0 to 9 for i ranging from 0 to 2020?a)h(i) =i2mod 10b)h(i) =i3mod 10c)h(i) = (11 &#8727; i2) mod 10d)h(i) = (12 &#8727; i) mod 10Correct answer is option 'B'. Can you explain this answer?

Answer

Since mod 10 is used, the last digit matters. If you do cube all numbers from 0 to 9, you get following

Therefore all numbers from 0 to 2020 are equally divided in 10 buckets. If we make a table for square, we don't get equal distribution. In the following table. 1, 4, 6 and 9 are repeated, so these buckets would have more entries and buckets 2, 3, 7 and 8 would be empty.

Answer

Which of the following hash function on integers will distribute key most uniformly over 10 bucket numbered 0 to 9 for i ranging form 0 to 2022

h ( i) = i power 2 mod 10 and

Answer

Since mod 10 is used, the last digit matters. If you do cube all numbers from 0 to 9, you get following

Therefore all numbers from 0 to 2020 are equally divided in 10 buckets. If we make a table for square, we don't get equal distribution. In the following table. 1, 4, 6 and 9 are repeated, so these buckets would have more entries and buckets 2, 3, 7 and 8 would be empty.

Answer

Explanation:

To determine which hash function will distribute keys most uniformly over 10 buckets, we need to analyze each of the given options.

Option A: h(i) = i^2 mod 10
This hash function computes the square of the input i, and then takes the modulo 10 of the result. Let's calculate the hash values for i ranging from 0 to 2020:

h(0) = 0^2 mod 10 = 0
h(1) = 1^2 mod 10 = 1
h(2) = 2^2 mod 10 = 4
h(3) = 3^2 mod 10 = 9
h(4) = 4^2 mod 10 = 6
...
h(2020) = 2020^2 mod 10 = 4

We can observe that the values are not uniformly distributed over the buckets. For example, both h(2) and h(2020) result in the same hash value of 4, causing a collision.

Option B: h(i) = i^3 mod 10
This hash function computes the cube of the input i, and then takes the modulo 10 of the result. Let's calculate the hash values for i ranging from 0 to 2020:

h(0) = 0^3 mod 10 = 0
h(1) = 1^3 mod 10 = 1
h(2) = 2^3 mod 10 = 8
h(3) = 3^3 mod 10 = 7
h(4) = 4^3 mod 10 = 4
...
h(2020) = 2020^3 mod 10 = 0

We can observe that the values are more uniformly distributed over the buckets compared to option A. There are no collisions among the computed hash values, and each bucket receives a fair number of keys.

Option C: h(i) = (11 - i^2) mod 10
This hash function subtracts the square of the input i from 11, and then takes the modulo 10 of the result. Let's calculate the hash values for i ranging from 0 to 2020:

h(0) = (11 - 0^2) mod 10 = 1
h(1) = (11 - 1^2) mod 10 = 0
h(2) = (11 - 2^2) mod 10 = 7
h(3) = (11 - 3^2) mod 10 = 4
h(4) = (11 - 4^2) mod 10 = 7
...
h(2020) = (11 - 2020^2) mod 10 = 1

We can observe that the values are not uniformly distributed over the buckets. For example, both h(1) and h(2020) result in the same hash value of 1, causing a collision.

Option D: h(i) = (12 - i) mod 10
This hash function subtracts the input i from 12, and then takes the modulo 10 of the result. Let's calculate the

Answer

C

Top Courses for Computer Science Engineering (CSE)View all

GATE Computer Science Engineering(CSE) 2026 Mock Test Series

Crash Course for GATE CSE

Computer Networks

Crash Course: Computer Science Engineering (CSE)

Question Bank for GATE Computer Science Engineering

Top Courses for Computer Science Engineering (CSE)

Top Courses for Computer Science Engineering (CSE)

Related Content

Mock Test Series

Subject-wise Courses

Subject-wise Courses

Other Engg Branches

Company