Data Structures, unit: Hash Tables. Core concepts, terminology, and worked-example cues a college student meets for this unit, building on prior units without repeating them. Front: a term, concept, or short problem cue. Back: the definition, explanation, or answer.
38 cards · basic cards · AI-written, checked twice. Edit anything.
- What is a hash table?
Show answer
A data structure that maps keys to values using a hash function for fast lookup- What is a hash function?
Show answer
A function that converts a key into an index (or bucket) in the underlying array- What is the average time complexity of insertion, deletion, and lookup in a well-implemented hash table?
Show answer
O(1)- What is a hash collision?
Show answer
When two different keys hash to the same index- What is chaining, as a collision resolution technique?
Show answer
Storing multiple key-value pairs at the same index using a linked list or similar structure- What is open addressing, as a collision resolution technique?
Show answer
Finding another open slot in the array when a collision occurs, rather than chaining- What is linear probing?
Show answer
An open addressing technique that checks the next slot sequentially until an empty one is found- What is quadratic probing?
Show answer
An open addressing technique that checks slots at increasing quadratic intervals to reduce clustering- What is double hashing?
Show answer
An open addressing technique using a second hash function to determine the probe sequence- What is the load factor of a hash table?
Show answer
The ratio of the number of stored elements to the table's total capacity- What happens when a hash table's load factor gets too high?
Show answer
Performance degrades due to more frequent collisions, often triggering a resize (rehashing)- What is rehashing?
Show answer
Creating a new, larger hash table and reinserting all existing elements when the load factor grows too high- What makes a good hash function?
Show answer
It distributes keys uniformly across the table and is fast to compute- What is a hash set?
Show answer
A hash table variant that stores only keys (no associated values), used for fast membership testing- What is the worst-case time complexity of a hash table operation, if many collisions occur?
Show answer
O(n)
FlashKeepers