Kit Library / Computer Science / Data Structures
⚡ Topic Learning KitShared by a Veda learner · Generated with Veda AI
Veda Bites are swipeable micro-lessons — each one teaches exactly one idea. The bites below come from this kit — swipe through them in the app.
💡 Key Idea
Instant data retrieval, no searching!
Hashing is a technique that maps data of any size to a fixed-size value (called a hash code or hash value) using a hash function. This hash value is used as an index to store and retrieve data in an array-like structure called a hash table. The goal is to achieve O(1) average time complexity for…
↳ Hashing enables near-instant data access by mapping keys directly to storage locations.
📖 Definition
The magic that turns keys into indices.
A hash function $h(k)$ takes a key $k$ and returns an integer index within the range of the hash table (e.g., $0$ to $m-1$). A good hash function should be fast to compute, minimize collisions, and distribute keys uniformly across the table. Common examples include the division method (…
↳ A good hash function is fast, uniform, and minimizes collisions.
⭐ Important Fact
Constant time – the holy grail.
In a well-designed hash table, the average time complexity for search, insert, and delete operations is O(1), independent of the number of elements. This is because the hash function directly computes the location, avoiding any sequential search. However, in the worst case (e.g., all keys collide), the time…
↳ Hashing offers constant-time operations on average, but worst-case can be linear.
⚠️ Common Mistake
Different keys, same slot – a problem!
A collision occurs when two different keys $k_1$ and $k_2$ produce the same hash index ($h(k_1) = h(k_2)$). Collisions are inevitable if the number of possible keys exceeds the table size. Without handling, they cause data loss. Common mistake: ignoring collision resolution, leading to overwritten data or incorrect…
↳ Collisions are unavoidable; proper resolution is essential.
⚙️ Process
Store multiple items in the same slot.
Chaining is a collision resolution method where each slot of the hash table contains a linked list (or another container). When a collision occurs, the new element is simply appended to the list at that index. To search, compute the hash index and then traverse the list to find the key.
↳ Chaining uses linked lists to store multiple items per slot, making collisions manageable.
⚙️ Process
Find another slot when collision occurs.
Open addressing resolves collisions by probing (searching) for the next available slot in the hash table. Common probing techniques include linear probing (check next slot), quadratic probing (check slots at increasing offsets), and double hashing (use a second hash function). This avoids extra memory b…
↳ Open addressing finds alternative slots within the table, avoiding extra memory but risking clustering.
⚖️ Comparison
Which collision strategy is better?
↳ Chaining is simpler for deletion and handles high load factors, while open addressing saves memory.
✏️ Example
Simple hash function in action.
Suppose we have a hash table of size $m = 10$ and keys: 25, 34, 78. Using the division method $h(k) = k \bmod 10$:
↳ The division method is straightforward: the remainder of the key divided by the table size.
🛠️ Application
Hashing is everywhere in computing.
↳ Hashing powers databases, caches, security, and compilers.
See hashing in code.
↳ A basic hash table can be implemented with a list of lists for chaining.
🎯 Exam Tip
Prime numbers reduce collisions.
When using the division method, choose a table size $m$ that is a prime number and not close to a power of 2. This reduces the chance of collisions because it avoids patterns in the keys. For example, $m = 11$ is better than $m = 10$ for many key sets.
↳ Prime table sizes improve hash distribution and reduce collisions.
🧠 Memory Trick
Think of a library catalog.
Imagine a library where each book has a unique shelf number based on its title. Instead of searching the whole library, you go directly to the shelf. That's hashing: the hash function is the catalog that tells you the shelf number. Hash → Index → Direct access.
↳ Hashing is like a library catalog: direct mapping to the storage location.
❓ Did You Know
Hashing secures your passwords.
Cryptographic hash functions (like SHA-256) are designed to be one-way and collision-resistant. They are used in digital signatures, blockchain, and password storage. Unlike data structure hash functions, they don't need to be fast; they need to be secure.
↳ Cryptographic hashing prioritizes security over speed.
⚠️ Common Mistake
Overfilling the table kills performance.
The load factor $\alpha = n/m$ (number of elements / table size) indicates how full the table is. As $\alpha$ approaches 1 (or exceeds 1 in chaining), collisions increase, and performance degrades. A common mistake is not resizing the table when the load factor gets too high. Best practice: resize (rehash) when…
↳ Monitor load factor and resize to maintain O(1) performance.
Uniform distribution is key.
↳ A good hash function is uniform, fast, and avoids clustering.
Your ticket number is the hash.
At a coat check, you give your coat and receive a ticket with a number. When you return, you hand the ticket and get your coat instantly. The ticket number is like the hash index – it directly tells the attendant where to find your coat. No searching through all coats needed.
↳ Hashing provides direct access, just like a coat check ticket.
🚫 Warning
You can't get the key from the hash.
A hash function is one-way: given a key, you can compute the hash, but given a hash, you cannot uniquely determine the original key. This is because multiple keys can map to the same hash (collision). Therefore, hashing is not encryption; it's for lookup, not security (unless it's cryptographic).
↳ Hashing is one-way; don't confuse it with encryption.
🎯 Exam Tip
Know your complexities for exams.
↳ Remember: O(1) average, O(n) worst-case.
⚙️ Process
When the table gets full, rebuild.
Rehashing is the process of increasing the size of the hash table when the load factor exceeds a threshold. Steps: create a new table with a larger size (usually double), then re-insert all existing elements using the new hash function (since the table size changed, indices change). This is an O(n) operation but en…
↳ Rehashing maintains efficiency by resizing the table when needed.
Hashing is a data structure technique that maps keys to array indices using a hash function, enabling average O(1) time for search, insert, and delete operations. Collisions are handled via chaining or open addressing, a…
Full explanation, worked examples & memory tricks in the app
All 32 questions, laddered from warm-up to topper-level, each with its answer and the reasoning behind it.
Q1. What is the primary purpose of a hash function in a hash table?
BeginnerB · To map keys to indices in an array
A hash function computes an index from a key, enabling O(1) average-time access in a hash table.
Q2. Which of the following is a common hash function for integer keys?
BeginnerA · key % table_size
The modulo operation (key % table_size) is a simple and widely used hash function to map keys into the range of table indices.
Q3. What is a collision in hashing?
BeginnerD · Two different keys map to the same hash index
A collision occurs when a hash function produces the same index for two or more distinct keys.
Q4. Which collision resolution technique uses a linked list at each table slot?
BeginnerB · Separate chaining
Separate chaining stores all elements that hash to the same index in a linked list (or similar structure) at that slot.
Q5. Which of the following is a common application of hashing?
BeginnerB · Database indexing
Hashing is widely used in database indexing, symbol tables, caches, and many other applications requiring fast lookups.
Q6. A hash function can map two different keys to the same index.
BeginnerA · True
Yes, this is called a collision, which is inevitable when the number of possible keys exceeds the table size.
Q7. In a hash table, the order of elements is preserved as they are inserted.
BeginnerB · False
Hash tables do not preserve insertion order; elements are placed based on their hash values, not their insertion sequence.
Q8. What is the primary purpose of a hash function in a hash table?
BeginnerA · To map keys to array indices
A hash function's main role is to convert a key into an array index, enabling direct access to the table slot.
Q9. Which of the following is a common hash function for integer keys?
BeginnerD · Key modulo table size ($k \mod m$)
The modulo operation ($k \mod m$) is a standard and simple hash function for integer keys, producing an index in the range $[0, m-1]$.
Q10. What is a collision in hashing?
BeginnerC · When two different keys map to the same index
A collision occurs when a hash function maps two distinct keys to the same array index, requiring a resolution strategy.
Q11. Which collision resolution technique uses a linked list at each table slot?
BeginnerB · Separate chaining
Separate chaining stores all elements that hash to the same index in a linked list at that slot.
Q12. In open addressing, when a collision occurs, what does the algorithm do?
BeginnerB · It probes alternative slots until an empty one is found
Open addressing resolves collisions by searching for the next available slot using a probe sequence, unlike chaining which uses extra memory outside the table.
Q13. What is the load factor (α) of a hash table?
BeginnerD · The ratio of the number of stored elements to the table size
The load factor $\alpha = n/m$ (where $n$ is the number of keys and $m$ is the table size) indicates how full the table is, affecting performance.
Q14. Which of the following is a characteristic of a good hash function?
BeginnerC · It distributes keys uniformly across the table
A good hash function minimizes collisions by spreading keys evenly over the table, leading to near O(1) average operations.
Q15. What is the average time complexity for search in a well-designed hash table?
BeginnerD · O(1)
With a good hash function and low load factor, the average search time is constant, O(1), independent of the number of elements.
Q16. In linear probing, if slot h(k) is occupied, where is the next slot tried?
BeginnerA · h(k) + 1 (mod table size)
Linear probing checks consecutive slots: $(h(k) + i) \mod m$ for $i = 1, 2, \ldots$, so the next slot is $h(k)+1$ modulo the table size.
Q17. What is the main disadvantage of separate chaining?
BeginnerB · It requires extra memory for pointers or linked lists
Separate chaining uses additional memory to store linked list nodes, which can be a drawback compared to open addressing that uses the table itself.
Q18. What is the primary operation that a hash function performs in a hash table?
BeginnerB · It maps keys to array indices.
A hash function takes a key and computes an array index where the corresponding value is stored. This mapping enables average O(1) access.
Q19. Which of the following is a common collision resolution technique in hashing?
BeginnerB · Separate chaining
Separate chaining is a collision resolution method where each table slot holds a linked list of keys that hash to the same index. Other options are unrelated to collision resolution.
Q20. What is the average time complexity for insert, delete, and search operations in a well-designed hash table?
BeginnerA · O(1)
A well-designed hash table with a good hash function and appropriate load factor achieves average constant time O(1) for insert, delete, and search operations.
Q21. In the context of hashing, what does the term 'load factor' (α) represent?
BeginnerB · The ratio of the number of stored elements to the table size
The load factor α is defined as the number of elements stored divided by the table size. It is a key indicator of how full the table is and affects performance.
Q22. Which of the following is a common application of hashing?
BeginnerD · Implementing a symbol table in a compiler
Hashing is widely used in symbol tables (e.g., in compilers), databases, and caches to provide fast key-based lookup. Sorting, tree traversal, and graph algorithms are not primary applications of hashing.
Q23. In open addressing, when a collision occurs, what does the algorithm do?
IntermediateA · It probes for the next available slot
Open addressing resolves collisions by probing (e.g., linear, quadratic, or double hashing) to find another empty slot within the same array.
Q24. What is the load factor (α) of a hash table?
IntermediateD · Number of keys divided by number of slots
Load factor α = n/m, where n is the number of keys stored and m is the number of slots. It indicates how full the table is.
Q25. Which of the following is a characteristic of a good hash function?
IntermediateD · It distributes keys uniformly across the table
A good hash function minimizes collisions by spreading keys uniformly over the available indices.
Q26. What is the average time complexity for search in a well-designed hash table?
IntermediateD · O(1)
With a good hash function and low load factor, hash table operations achieve constant average time complexity, O(1).
Q27. In linear probing, if slot h(k) is occupied, where is the next slot tried?
IntermediateB · h(k) + 1
Linear probing checks consecutive slots: (h(k) + i) mod m for i = 0, 1, 2, ... until an empty slot is found.
Q28. What is the main disadvantage of separate chaining?
IntermediateD · It requires extra memory for pointers
Separate chaining uses linked lists, which require additional memory for node pointers, unlike open addressing which stores all elements in the array itself.
Q29. Which of the following is NOT a method of open addressing?
IntermediateA · Separate chaining
Separate chaining is a different collision resolution technique that uses linked lists, not open addressing.
Q30. What is the primary reason for choosing a prime number as the table size in modulo-based hashing?
AdvancedD · It reduces the number of collisions
A prime table size helps distribute keys more uniformly, especially when keys have patterns, reducing clustering and collisions.
Q31. In double hashing, the probe sequence is determined by:
AdvancedD · Two different hash functions
Double hashing uses a second hash function to compute the step size, making the probe sequence more flexible and reducing clustering.
Q32. What is the worst-case time complexity for search in a hash table with separate chaining?
AdvancedA · O(n)
In the worst case, all keys collide into one chain, making the search linear in the number of keys, O(n).
17 flashcards in this kit — the app reviews them with spaced repetition so the right card returns on the right day.
Every game is built from this kit's own content — scores feed your mastery, so playing counts as studying.
True False
Built from this kit's own content
Memory Match
Built from this kit's own content
Flashcard Battle
Built from this kit's own content
Speed Quiz
Built from this kit's own content
Sequence Builder
Built from this kit's own content
Revision Battle
Built from this kit's own content
Playable in the app
The full Veda Bites deck, complete notes, spaced-repetition flashcards, leveled MCQs, tests and games for this kit — plus Daily Facts and the Arena, every day.