What is a hash table?
A hash table is a data structure that stores key–value pairs using an array, a hash function, and a collision-resolution strategy.
Study 7 Hash Tables with 12 free online flashcards. Review key terms, definitions, and concepts with this interactive flashcard deck.
What is a hash table?
A hash table is a data structure that stores key–value pairs using an array, a hash function, and a collision-resolution strategy.
How does hash-table lookup work?
It computes the key’s hash value, maps it to a bucket or slot, examines entries there, and uses key equality to confirm the match.
What must a hash function guarantee about equal keys?
Equal keys must produce equal hash values, but unequal keys may produce the same hash value or bucket index.
What is a hash-table collision?
A collision occurs when two different keys are assigned to the same bucket or slot.
How does separate chaining resolve collisions?
Separate chaining stores all entries mapping to one bucket in a collection, such as a linked list or dynamically managed sequence.
How does open addressing resolve collisions?
Open addressing stores every entry directly in the table array and searches a probe sequence of alternative slots after a collision.
What is linear probing?
Linear probing checks consecutive positions using indexi=(h(k)+i)modm.
Why are tombstones used in open addressing?
A tombstone marks a deleted entry while telling searches to continue probing, preventing a search from stopping too early.
Why must entries be rehashed after resizing?
It allocates a larger array and rehashes every entry because changing the bucket count changes the result of hash(key)modm.
How does geometric growth affect insertion complexity?
A resize costs O(n) when it occurs, but geometric growth spreads these costs across insertions, giving amortized O(1) insertion.
What are hash-table operation bounds?
With good distribution and controlled load factor, search, insertion, and deletion are expected O(1), but each can be O(n) in the worst case.
When is a hash table a strong data-structure choice?
A hash table is preferable for fast average-case membership tests, key–value associations, and frequent unsorted insertion or deletion.
A progressive guide to how computers encode numbers, text, images, and sound as binary data, including the trade-offs and limits of digital representation.
A focused set of flashcards covering Python variables, data types, expressions, control flow, functions, input, output, and common programming practices.
Learn how Boolean expressions, logical operators, and conditional structures let programs make reliable decisions, including how to handle boundaries, branch order, and testing.
A structured guide to the main data structures, their operations, efficiency trade-offs, representations, and practical selection criteria.
A progressive guide to tree structure, binary-tree traversals, binary search tree operations, deletion, balancing, and the way tree height determines time and space costs.
A progression through how data is organized, searched, exposed through software interfaces, and managed through abstraction layers in modern computer systems.
A medium-difficulty quiz on integrating problem definition, representation, algorithms, complexity analysis, testing, correctness, ethical evaluation, and documentation in a computer science capstone.
A practical guide to integrating problem definition, data representation, modular programming, algorithms, complexity analysis, testing, correctness, and ethical evaluation into a responsible computer science capstone.
This quiz covers process management, context switching and scheduling, multitasking, traps and interrupts, and RISC-V privilege transitions.