Hash maps Flashcards

1
Q

What functions are implemented in a hash map?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

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

A
Worst = O(n) - linear time
Best = O(1) - constant time
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What are entries in the hash table called?

A

Buckets

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

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

A

Collisions

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What type of hash functions are there?

A

U.M.D.

  • Universal hashing - worse case probability of collision 1/m (m = number of slots)
  • Multiplication method
  • Division method
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

A

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

  • Total slots < 50k = size x 4
  • Total slots ≥ 50k = size x 2
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

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

A

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

Used to solve cycling questions

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is open addressing?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is the simplest solution to collisions?

A

Hashing with chaining (linked lists)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is the expected probability of collision in universal hashing?

A

1/m

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What are 3 properties of universal hashing?

A
  • Guarantees very few conflicts (1/m)
  • Needs randomness
  • Hash function is chosen from a hash family
How well did you know this?
1
Not at all
2
3
4
5
Perfectly