Hash Maps

Question 1

What is the ‘Set’ ADT and its operations?

Answer 1

A collection of data items that does not allow duplicates.

Operations: insert(x), remove(x), contains(x), isEmpty(), size(), addAll(x)/union(x), retainAll(x)/intersection(x), removeAll()

Question 2

What is the ‘Ordered Set’ ADT, its additional operations, and its important operation runtimes?

Answer 2

A set with a ‘total order’ defined on the items. (All items pairs in a <, >, relation)

Operations: findMin(), findMax(x)

Runtime for balanced search trees Oln(n): insert(x), remove(x), contains().

Question 3

What is the ‘Map ADT’ and describe its operations?

Answer 3

The map ADT is a collection of (key, value) pairs.

Keys are unique (sets), but values are not.

Operations: get(key), set(key, value)

Question 4

What is a common way to store a map whose keys are integers?

Answer 4

In an array, so that the runtime for get(k), and put(k, v) are Theta(1).

Question 5

What is a ‘Hash Table’ and what is its lookup runtime?

Answer 5

A data structure that implements an associative array or dictionary. It is an abstract data type that maps keys to values.

Look/ Get: Theta(1);

Question 6

What are hashing ‘collisions’?

Answer 6

When more than one value is hashed by a particular hash function hashes to the same slot in the table.

Question 7

What are the two goals of a good hash function?

Answer 7

1. Uniform Distribution i.e. to spread the keys out as much as possible
2. Ensure that all table cells can be used.

Question 8

What are the four practices to be cognizant of when designing a hash table?

Answer 8

1. Keep tableSize a prime number
2. When combining hash values, make the factors prime numbers.
3. Only use immutable objects as keys
4. When two objects are equal, their hash code methods must return the same values.

Question 9

Define the two methods to resolve collisions in hash tables.

Answer 9

1. Separate Chaining: Keeps all items whose key hashes to the same value in a linkedList.
2. Linear Probing: Placing the new key in another empty cell bases on a secondary function.

Question 10

What is the equation to calculate the ‘Load Factor’?

Answer 10

Load Factor (lambda) = The average length of a list = N/tableSize.