Hashing & Prefix Sums

10 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

1. ◆what it is

   A hash table turns a key into a bucket index (hash & (capacity − 1)), so get / put / contains cost O(1) on average.

   #1
2. ◆what it is

   A prefix sum stores running totals once: sum(l..r) = p[r + 1] − p[l] — one subtraction per query.

   #2
3. ↯use it when

   Seen before? → HashSet. Value → index or count → HashMap. Many range sums → prefix array. Sum = k with negatives → prefix + map.

   #3
4. O( )cost

   HashMap: O(1) average, O(log n) worst (Java 8+ trees), O(n) memory. Prefix sums: O(n) build, O(1) query, O(n) per update.

   #4
5. { }template

   seen.put(0, 1); then per x: sum += x; count += seen.getOrDefault(sum - k, 0); seen.merge(sum, 1, Integer::sum);

   #5
6. !trap

   Override equals without hashCode (or change a key after put) and the entry is lost: lookups go to the wrong bucket.

   #6
7. !trap

   Integer objects compared with == or != work only for −128..127. Use .equals, Objects.equals, or unbox to int.

   #7
8. !trap

   Java's % can be negative: -7 % 3 == -1. Use Math.floorMod(x, k) when the remainder is a map key.

   #8
9. ✦pro tip

   Keys small and dense (letters, 1..n, remainders)? An int[] is a perfect hash table — no hashing, no boxing.

   #9
10. ✦pro tip

    One-to-one mapping (isomorphic, word pattern)? Two maps, one per direction — a single map can't see two keys sharing a value.

    #10

Shaky on a card? Open the chapter or flip its recall cards.