Week 5 - Hash Tables Flashcards

1
Q

Are python dictionaries considered to be hash tables?

A

Yes, they are!

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

If you had to find a specific price for a fruit in a grocery store, what would the worst case time complexity be?

A

The worst case time complexity would be O(n), because you could possibly have to check every single price before you find the one for your desired fruit.

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

What is the time complexity of binary search?

A

The time complexity of binary search is O(log n), but it only works with sorted arrays!

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

What is instantaneous access?

A

Instantaneous access refers to the ability to retrieve or access data immediately without noticeable delay, allowing users to quickly obtain the information or resources they need. This is constant time O(1).

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

What are hash functions?

A

A hash function is an algorithm that converts strings (or other input types) into fixed-size numerical values, enabling instantaneous access or O(1) search times in data structures like hash tables.

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

What is a hash table?

A

A hash table is the combination of an array and a hash function.

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

What are the two core components of a hash table?

A

A hash table contains keys and values. Each key is mapped to a value, for example the key ‘Apple’ could be mapped to the value ‘42’ in a hash table.

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

What are some possible practical uses of hash tables?

A

Hash tables can map names to phone numbers or websites to IP addresses in mobile apps, prevent duplication in a voting app, and cache commonly visited websites for faster access.

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

What is Caching?

A

Caching is the process of storing frequently accessed data in a temporary storage location to speed up future retrievals.

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

What are the two main advantages of caching?

A
  1. Speed: It significantly reduces the time to receive data

2.Efficiency: It reduces the load on servers by avoiding repetitive tasks

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

What is a collision and when does it occur?

A

A collision occurs in a hash table when two keys map to the same location in the underlying array.

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

What is a perfect hash function?

A

A perfect hash function is a type of hash function that assigns unique hash values to distinct keys, ensuring no collisions. While ideal for fixed, known sets of keys, it’s rarely achievable in dynamic, real-world scenarios where keys can change.

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

What is one of the simplest ways to handle collisions?

A

One of the simplest ways to handle collisions is by using a linked list, where multiple keys mapping to the same slot are stored in a list at that slot.

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

What is the downside of using linked lists as the number of collisions increase?

A

As collisions increase, the efficiency of O(1) lookups diminishes because you must traverse longer linked lists to find a specific value. If many collisions occur, the hash table can degrade into a collection of long linked lists, significantly slowing down lookup operations.

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

What is the performance of hash tables with good hash functions?

A

Average Case Worst Case
Search O(1) O(n)
Insert O(1) O(n)
Delete O(1) O(n)

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

What is constant time?

A

Constant time is not instantaneous exactly, rather constant time means that the time taken by an operation remains the same regardless of the input size.

16
Q

How do hash tables compare in terms of speed to arrays and linked lists?

A

Hash tables are as fast as arrays at searching. Hash tables are as fast as linked lists at insert/delete.

17
Q

What is a load factor?

A

The load factor in a hash table is the ratio of the number of stored elements to the total number of available slots, indicating how full the table is. It is considered high if it exceeds 0.7!

18
Q

How can the load factor be improved?

A

Resizing a hash table improves the load factor and maintains O(1) average time complexity for operations due to amortized analysis. Although resizing is costly (O(n)) and infrequent, its expense is spread across many operations, ensuring that the average cost per operation remains constant over time.