Hash Set Lookup

Foundations

In Arrays & Strings, one running value summarized everything a scan had passed. Some questions need more than a summary: they need to know whether one exact value appeared earlier. A hash table answers that. It is an array of slots, called buckets, indexed from 0, plus a hash function that turns a value into a bucket index, such as hash(x) % 8 for 8 buckets.

Storing x writes it into bucket hash(x) % 8; checking for x computes the same index and looks only there. That jump is the same O(1) move as reading nums[i]. Two values can land in the same bucket, a collision, so the table probes other slots and grows before it gets crowded. That keeps lookups O(1) on average, however many values it holds.

Hash set lookup puts that to work during a scan. Walk nums = [7, 1, 5, 3, 6] and, at each element, first ask whether it is already in a set called seen, then add it. Every answer costs one O(1) lookup, so the scan never loops back to compare earlier elements one by one. The set trades memory, up to n values, for that speed.

• Arrays & Strings

  Hashing is the tool for remembering facts while you walk an array. That lesson shows why one remembered fact can replace an inner loop.

  Open lesson

Case Scenario

Contains Duplicate asks that question of a whole array: does any value appear twice? In nums = [2, 7, 3, 1, 3], the 3 at index 4 repeats the 3 at index 2, so the answer is True. A repeat can sit anywhere, so a correct answer has to account for every pair of positions.

The direct approach compares every value with every value after it, using two nested loops over i and j. That is up to n(n - 1)/2 comparisons, 10 for these five values, and the loops stop early only when a repeat turns up. Step through the passes below to see how much of that reading repeats.