What is a hash table?
A hash table is a data structure that stores key–value pairs and supports efficient insertion, lookup, and deletion.
Study 06 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 and supports efficient insertion, lookup, and deletion.
What properties should a useful hash function have?
A useful hash function is deterministic, fast, well distributed, and consistent with equality.
What is a collision in a hash table?
A collision occurs when two different keys map to the same table index.
How does separate chaining resolve collisions?
Separate chaining stores all entries with the same index in a collection associated with that slot, often a linked list.
How does open addressing resolve collisions?
Open addressing stores every entry directly in the table array and searches alternative slots using a probe sequence.
Why does open addressing use tombstones?
A tombstone marks a deleted slot so probing continues through it instead of incorrectly ending a search.
Why must entries be rehashed after resizing?
Resizing requires recomputing indexes because changing the capacity changes the modulus used to place entries.
What must a hash function guarantee about equal keys?
Equal keys must produce the same hash value. Otherwise, a lookup may search a different location from the one used during insertion.
How does data-structure hashing differ from cryptographic hashing?
Data-structure hashing prioritizes speed and good distribution. Cryptographic hashing additionally aims to resist intentional attacks and make inputs difficult to recover or manipulate.
What is primary clustering in linear probing?
Primary clustering is the formation of long runs of consecutive occupied slots. In linear probing, these runs increase the probe lengths of later operations.
How does double hashing determine probe positions?
Double hashing uses a second hash function to determine the probe step: pi(k)=(h1(k)+ih2(k))modm.
When are hash-table operations expected to take O(1) time?
Expected O(1) operations require assumptions such as good distribution, controlled load factor, and an effective collision strategy. Worst-case search, insertion, or deletion can still take O(n).
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 14-question quiz on trees, binary trees, traversals, recursive algorithms, and binary search trees. The questions progress from foundational concepts to applied reasoning about structure, complexity, and BST operations.
A structured guide to comparison-based sorting algorithms, their complexity, stability, memory use, and practical selection criteria.
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.