Data Structures & Algorithms Hashing & Sorting Syllabus

Hashing & Sorting syllabus — full chapter and topic list

Expand any chapter to see its topics and sub-topics. This is the whole examinable outline for Hashing & Sorting in Data Structures & Algorithms, not a summary of it.

1. 1

   Hash Tables

   4 topics

   • Hash Functions
   • Collision Resolution
   • Hash Sets and Hash Maps
   • Applications and Frequency Counting
2. 2

   Elementary Sorting

   4 topics

   • Bubble Sort
   • Selection Sort
   • Insertion Sort
   • Stability in Sorting
3. 3

   Efficient Sorting

   4 topics

   • Merge Sort
   • Quick Sort
   • Heap Sort
   • Lower Bound for Comparison Sorts
4. 4

   Non-Comparison Sorting

   3 topics

   • Counting Sort
   • Radix Sort
   • Bucket Sort
5. 5

   Searching Techniques

   3 topics

   • Linear Search
   • Binary Search
   • Ternary Search

Hashing & Sorting flashcards for Data Structures & Algorithms

24 of 51 cards from the Hashing & Sorting deck — real questions with worked answers.

1. What is a hash function in the context of hash tables?

   A function that maps a key of arbitrary size to a fixed-range integer index (bucket), ideally distributing keys uniformly so that $h(\text{key})$ can be computed in $O(1)$ time.

2. What three properties characterize a good hash function?

   1) Deterministic (same key always gives same value), 2) Uniform distribution of keys across buckets to minimize clustering, and 3) Fast to compute, ideally $O(1)$.

3. State the division method for hashing an integer key $k$ into $m$ buckets.

   $h(k) = k \bmod m$. Choosing $m$ to be a prime not close to a power of $2$ helps spread keys evenly.

4. State the multiplication method for hashing a key $k$.

   $h(k) = \lfloor m \,(k A \bmod 1) \rfloor$, where $0 < A < 1$ is a constant (Knuth suggests $A \approx \frac{\sqrt{5}-1}{2} \approx 0.618$) and $kA \bmod 1$ is the fractional part.

5. What is a collision in a hash table?

   A collision occurs when two distinct keys $k_1 \neq k_2$ hash to the same bucket, i.e. $h(k_1) = h(k_2)$. Collisions are unavoidable in general and must be resolved.

6. Name the two main families of collision resolution strategies.

   1) Separate chaining (each bucket stores a list/structure of entries), and 2) Open addressing (all entries stored in the table itself, probing for another slot).

7. How does separate chaining resolve collisions?

   Each bucket holds a secondary container (typically a linked list). Colliding keys are appended to that bucket's list, so lookups scan only the entries within one bucket.

8. Define the load factor $\alpha$ of a hash table.

   $\alpha = \frac{n}{m}$, the ratio of the number of stored entries $n$ to the number of buckets $m$. It measures how full the table is.

9. In separate chaining, what is the expected cost of a search under simple uniform hashing?

   $O(1 + \alpha)$, where $\alpha = \frac{n}{m}$ is the load factor. With $\alpha = O(1)$, operations are expected $O(1)$.

10. Contrast linear probing, quadratic probing, and double hashing in open addressing.

    Linear: probe $h(k)+i$. Quadratic: probe $h(k)+c_1 i + c_2 i^{2}$. Double hashing: probe $h_1(k) + i\,h_2(k)$. Steps $i = 0,1,2,\dots$ all taken $\bmod m$.

11. What is primary clustering and which probing scheme suffers from it?

    Primary clustering is the buildup of long runs of occupied slots that lengthen future probes. It afflicts linear probing, because colliding keys probe the same contiguous sequence.

12. Why is table resizing (rehashing) used, and what is its amortized cost?

    When $\alpha$ exceeds a threshold, the table is resized (often doubled) and all entries are rehashed to keep operations $O(1)$. Doubling gives $O(1)$ amortized insertion cost.

13. What is the difference between a hash set and a hash map?

    A hash set stores only unique keys (membership testing). A hash map (dictionary) stores key–value pairs, mapping each unique key to an associated value. Both use hashing for $O(1)$ average operations.

14. What are the average and worst-case time complexities of insert/search/delete in a hash map?

    Average case $O(1)$; worst case $O(n)$ when many keys collide into one bucket (degenerating to a linear scan).

15. How can a hash map be used for frequency counting?

    Iterate over the elements, using each element as a key and incrementing its stored count: $\text{map}[x] \mathrel{+}= 1$. This yields all frequencies in $O(n)$ average time.

16. Give two classic algorithmic applications of hash maps/sets beyond frequency counting.

    Detecting duplicates / membership queries in $O(1)$, and the two-sum problem (checking whether $\text{target}-x$ has been seen). Also grouping/anagram bucketing and caching/memoization.

17. Describe the Bubble Sort process.

    Repeatedly pass through the list, comparing adjacent pairs and swapping them if out of order, so the largest remaining element 'bubbles' to the end each pass. Repeat until a pass makes no swaps.

18. State the best, average, and worst-case time complexity of Bubble Sort.

    Best $O(n)$ (already sorted, with early-exit flag), average and worst $O(n^{2})$. Space $O(1)$; it is stable and in-place.

19. Describe the Selection Sort process.

    For each position from left to right, find the minimum element in the unsorted remainder and swap it into place. After the $i$-th pass the first $i$ elements are sorted.

20. State the time complexity and number of swaps of Selection Sort.

    $O(n^{2})$ comparisons in all cases (best, average, worst), but only $O(n)$ swaps. Space $O(1)$; it is in-place and generally not stable.

21. Describe the Insertion Sort process.

    Build the sorted portion one element at a time: take the next element and shift larger sorted elements right until the correct insertion point is found, then place it there.

22. State the best, average, and worst-case complexity of Insertion Sort.

    Best $O(n)$ (nearly sorted input), average and worst $O(n^{2})$. Space $O(1)$; it is stable, in-place, and efficient for small or nearly sorted arrays.

23. What does it mean for a sorting algorithm to be stable?

    A sort is stable if it preserves the relative order of elements that compare equal (equal keys keep their original input order).

24. Classify these sorts as stable or unstable: Bubble, Insertion, Merge, Selection, Quick, Heap.

    Stable: Bubble, Insertion, Merge (standard). Unstable (standard implementations): Selection, Quick, Heap.

See more Hashing & Sorting flashcards →

Planning Hashing & Sorting for Data Structures & Algorithms

Hashing & Sorting (Data Structures & Algorithms) FAQ