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.
24 cards · basic cards · AI-written, checked twice. Edit anything.
- What is a hash table?
- A data structure that maps keys to values using a hash function for fast lookup
- What is a hash function?
- 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?
- O(1)
- What is a hash collision?
- When two different keys hash to the same index
- What is chaining, as a collision resolution technique?
- 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?
- Finding another open slot in the array when a collision occurs, rather than chaining
- What is linear probing?
- An open addressing technique that checks the next slot sequentially until an empty one is found
- What is quadratic probing?
- An open addressing technique that checks slots at increasing quadratic intervals to reduce clustering
- What is double hashing?
- An open addressing technique using a second hash function to determine the probe sequence
- What is the load factor of a hash table?
- 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?
- Performance degrades due to more frequent collisions, often triggering a resize (rehashing)
- What is rehashing?
- Creating a new, larger hash table and reinserting all existing elements when the load factor grows too high
- What makes a good hash function?
- It distributes keys uniformly across the table and is fast to compute
- What is a hash set?
- 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?
- O(n)
FlashKeepers