Hash maps

Question 1

What functions are implemented in a hash map?

Answer 1

Insert(k,v)
Search(k) => value
Delete(k)

Question 2

What is the best and worst time complexity of a hash map?

Answer 2

Worst = O(n) - linear time
Best = O(1) - constant time

Question 3

What are entries in the hash table called?

Answer 3

Buckets

Question 4

What’s the term for when a hash function creates the same hash for two different keys?

Answer 4

Collisions

Question 5

What type of hash functions are there?

Answer 5

U.M.D.

• Universal hashing - worse case probability of collision 1/m (m = number of slots)
• Multiplication method
• Division method

Question 6

When does Python’s dictionary (hash table) resize and by how much?

Answer 6

When m > 2/3 full (m = number of slots)

• Total slots < 50k = size x 4
• Total slots ≥ 50k = size x 2

Question 7

What is the algorithm with the tortoise and the hare called and what questions can you solve with it?

Answer 7

Rabin-Karp (remember: Rabbit Carp = hare corp)

Used to solve cycling questions

Question 8

What is open addressing?

Answer 8

Method of collision resolution that uses “probing” to find an empty slot.
The hash function accepts a trial count
e.g. h = (key, trial) => x

Question 9

What is the simplest solution to collisions?

Answer 9

Hashing with chaining (linked lists)

Question 10

What is the expected probability of collision in universal hashing?

Answer 10

1/m

Question 11

What are 3 properties of universal hashing?

Answer 11

• Guarantees very few conflicts (1/m)
• Needs randomness
• Hash function is chosen from a hash family