Hashing

Question 1

What is the size of the array needed to store integer keys with up to digits using direct addressing?

a) 12
b) 10^12
c) 2^12

Answer 1

This is the number of all integers with up to 12 digits.

Question 2

What is the maximum possible chain length for a hash function h(x) = x mod 1000 used with a hash table of size 1000 for a universe of all integers with at most 12 digits

a) 10^9
b) 10^12
c) 1

Answer 2

When the values of the last 3 digits are fixed, there are 10^9 numbers with at most 12 digits.

Question 3

You want to hash integers from 0 up to 1M. What can be a good choice of p for the universal family?

a) 999997
b) 1000002
c) 1000003

Answer 3

1000003 This is a prime number bigger than 1000000

Question 4

How can one build a universal family of hash functions for integers between -1M (minus one million) and 1M?

a) Take the universal family for integers with p=100003
b) First, add 1M to each integer and get the range of integer between 0 and 2M. Then use the universal family for integers with p=200003.
c) First, add 1M to each integer. Then use the universal family for integers with p=100003
b)

Answer 4

b)