Week 5 - Hash Tables Flashcards
Are python dictionaries considered to be hash tables?
Yes, they are!
If you had to find a specific price for a fruit in a grocery store, what would the worst case time complexity be?
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.
What is the time complexity of binary search?
The time complexity of binary search is O(log n), but it only works with sorted arrays!
What is instantaneous access?
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).
What are hash functions?
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.
What is a hash table?
A hash table is the combination of an array and a hash function.
What are the two core components of a hash table?
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.
What are some possible practical uses of hash tables?
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.
What is Caching?
Caching is the process of storing frequently accessed data in a temporary storage location to speed up future retrievals.
What are the two main advantages of caching?
- Speed: It significantly reduces the time to receive data
2.Efficiency: It reduces the load on servers by avoiding repetitive tasks
What is a collision and when does it occur?
A collision occurs in a hash table when two keys map to the same location in the underlying array.
What is a perfect hash function?
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.
What is one of the simplest ways to handle collisions?
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.
What is the downside of using linked lists as the number of collisions increase?
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.
What is the performance of hash tables with good hash functions?
Average Case Worst Case
Search O(1) O(n)
Insert O(1) O(n)
Delete O(1) O(n)
