Week 4

Question 1

HashCode
A = 8
B=3
C=4
D=6
What is min. number of buckets required for no collission

Answer 1

6
Use Modulus to assign Buckets
8%6 = 2
3%3=3
4%3=1
6%3=0

Question 2

When does Collision occur

Answer 2

When two elements get mapped to the same index of the underlying array that makes up the HashSet.
Two DiFFERENT element are being hashed identical.
Trying to add a duplicate element to a HashSet does not qualify as collision.

Question 3

Hashing - Open Addressing

Answer 3

Placing new element with a duplicate hashcode into the first available (i.e. empty) array index after its own

Question 4

Hashing - Separate Chaining

Answer 4

Using an array of LinkedLists, so that at each index of the array, elements with the same hashcode get placed into a LinkedList together.

Question 5

Given a hash set of n buckets that utilizes separate chaining to handle collisions, if there are k elements in a bucket b, and you are searching for an element with hash code b, what is the time complexity of that specific operation? Select the best answer.

Answer 5

O(k)
Since we know that the element, if it exists, would be located in the bucket b, in order to determine if it does exist, we have to compare it with each of the k elements in the bucket in the worst case. Accessing the list in the bucket b is an O(1) operation due to being a simple index access.