Hashing: 17 flashcards
All 17 flashcards from this kit, free and with no sign-up.
1. What is hashing in data structures?
Show the answer
A technique that maps data of arbitrary size to fixed-size values (hash codes) using a hash function, enabling efficient storage and retrieval.
2. What is a hash function?
Show the answer
A function that takes a key as input and returns an integer (hash value) used as an index in a hash table.
3. What is a hash table?
Show the answer
A data structure that stores key-value pairs, using a hash function to compute an index for each key to determine where to store the value.
4. What is a collision in hashing?
Show the answer
When two different keys produce the same hash value (index) in a hash table.
5. What is chaining (closed addressing) for collision resolution?
Show the answer
Each bucket in the hash table holds a linked list (or another container) of all entries that hash to the same index.
6. What is open addressing for collision resolution?
Show the answer
When a collision occurs, the algorithm probes for the next available slot in the hash table (e.g., linear probing, quadratic probing, double hashing).
7. What is linear probing?
Show the answer
A collision resolution method where, if a slot is occupied, you check the next slot (index+1, then +2, etc.) until an empty slot is found.
8. What is the load factor (α) of a hash table?
Show the answer
The ratio of the number of stored entries (n) to the number of slots (m): α = n/m. It indicates how full the table is.
9. What is the average time complexity of search, insert, and delete in a hash table with good hashing and low load factor?
Show the answer
O(1) on average.
10. What is the worst-case time complexity of search in a hash table, and when does it occur?
Show the answer
O(n), when all keys collide into the same bucket (e.g., with chaining) or when the table is nearly full and probing is long.
11. What is a good hash function property?
Show the answer
It should distribute keys uniformly across the hash table to minimize collisions, and be fast to compute.
12. What is the division method for a hash function?
Show the answer
h(k) = k mod m, where k is the key and m is the table size. It's simple but m should be a prime number to reduce collisions.
13. What is the multiplication method for a hash function?
Show the answer
h(k) = floor(m * (k * A mod 1)), where A is a constant between 0 and 1 (often 0.618). It avoids the need for m to be prime.
14. What is double hashing?
Show the answer
An open addressing method where the probe sequence is determined by a second hash function: index = (h1(k) + i * h2(k)) mod m.
15. What is the primary advantage of hashing over binary search trees?
Show the answer
Average O(1) time for search, insert, and delete, compared to O(log n) for balanced BSTs.
16. What is a common application of hashing?
Show the answer
Implementing symbol tables in compilers, database indexing, caches, and password storage (hash of password).
17. What is the difference between a hash set and a hash map?
Show the answer
A hash set stores only keys (no values), while a hash map stores key-value pairs.
Your notes can be a kit like these
Every kit here was made from real study material. Point Veda at a chapter, a PDF, a photo or a link and get notes, flashcards, practice MCQs, games and a scored test — free, in 42 languages.
- Chapter notes
- Flashcards
- Practice MCQs
- Scored tests
- Exam prep
Get Veda free See what students get
Free to start · No ads · Works in 42 languages