18. Applications of Hash Tables

Choose the key before writing the loop#

A hash table becomes useful when we identify a question that repeatedly asks, “Have I seen this thing?” or “What information belongs to this thing?” The key identifies the thing; the value stores the answer. The hard part is often choosing this relationship rather than implementing hashing again.

Recall 17. Hash Tables: expected constant-time operations assume a suitable hash and bounded load. In this chapter, $n$ is an input array length and $d$ is its number of distinct values. A table containing one entry per distinct value needs $O(d)$ entries, not necessarily $O(n)$, although $d\leq n$.

The lecture develops sets, counters, two sum, odd-occurring elements and anagrams. These are different algorithms built from the same map operations. Each example below identifies the information the table holds after processing a prefix of the input. That statement is the loop invariant: a fact preserved by every iteration and used to justify the result.

Sets: membership without associated data#

A set contains unique elements and supports insertion, membership testing and deletion. Repeatedly inserting 8 leaves one copy of 8. Implement it with a map whose key is the set element and whose value is an ignored marker, such as 1:

• SetInsert(s, x) becomes mapPut(s, x, 1).
• SetContains(s, x) becomes mapGet(s, x, NULL).
• SetDelete(s, x) becomes mapRemove(s, x).
• Size is the map's distinct-key count.

The NULL output pointer means we only need to know whether the key exists, not retrieve the dummy value. These calls use the complete integer map in the previous chapter.

Read the hash row as expected bounds under the assumptions above. The unordered-array insertion row includes checking uniqueness, so it is linear even if physically appending would be constant-time. An AVL tree is attractive if you also want sorted traversal or worst-case guarantees.

Worked example. To remove duplicates while preserving the first occurrence order in [4, 3, 4, 8, 8, 4], start with an empty set and output sequence.

The set is unordered, but the output order is controlled by the input scan. Enumerating the set afterwards would not in general preserve the same order.

Practice. Why can't a set tell whether 4 appeared once or three times?

Counters: values that record multiplicity#

A counter maps an item to its occurrence count. For each input x, retrieve its old count, treating absence as zero, then replace it with old count plus one. The invariant is that after the first $i$ inputs, each stored count equals its frequency within that prefix.

For [4, 3, 4, 8, 8, 4]:

• First 4: absent means 0, then store 4 → 1.
• 3: store 3 → 1.
• Second 4: retrieve 1 and replace with 2.
• First and second 8: store 1, then replace with 2.
• Third 4: replace 2 with 3.

The final map is 4 → 3, 3 → 1, 8 → 2. The map contains three pairs despite six inputs.

/* Requires the struct map and functions from Hash Tables.
   Counts must fit in int. Returns false on allocation failure. */
bool counterAdd(struct map *counter, int x) {
    int count = 0;
    (void)mapGet(counter, x, &count);
    return mapPut(counter, x, count + 1);
}

The initialisation count = 0 handles absence because mapGet leaves the output unchanged on failure. In a general unbounded counter, check for INT_MAX before incrementing, or use a count type suitable for the maximum input.

For $n$ items, one lookup and one update per item gives expected $O(n)$ table work with suitable resizing, plus hashing/key-comparison costs. The fixed-capacity example remains expected linear when its capacity is chosen proportional to $n$; using a tiny fixed table for an indefinitely growing input does not maintain bounded load.

Practice. Process [2, 2, 7, 2]. State the invariant after the third item and the final counter.

Two sum: look for the complement#

Problem. Given an integer array and target $S$, determine whether two different positions contain values whose sum is $S$. Equal values are allowed if they occur at separate positions.

Checking every pair examines up to $n(n-1)/2$ pairs, so costs $O(n^2)$. A hash set remembers earlier values. If the current value is $x$, its required partner is the complement $S-x$.

For lecture input [12, 6, 3, 3, 7, 8] and target 13:

Check before inserting the current value. With target 6, the first 3 must not match itself. The second 3 can match the first. For target 16, no complement is present during this scan, so the result is false.

C implementation and correctness#

This function uses the complete integer map from 17. Hash Tables. Its caller receives a success/failure status separately from the mathematical answer. The scratch set is allocated inside the function and freed on every exit.

#include <limits.h>
#include <stdint.h>

/* Precondition: a has n elements when n > 0; result is not NULL. */
bool twoSum(const int *a, size_t n, int target, bool *result) {
    if (n > (SIZE_MAX - 1) / 2) return false;
    struct map *seen = mapNew(2 * n + 1);
    if (seen == NULL) return false;
    *result = false;
    for (size_t i = 0; i < n; i++) {
        int x = a[i];
        /* Test whether target - x fits in int before subtracting. */
        bool fits = !((x > 0 && target < INT_MIN + x) ||
                      (x < 0 && target > INT_MAX + x));
        if (fits && mapGet(seen, target - x, NULL)) {
            *result = true;
            mapFree(seen);
            return true;
        }
        if (!mapPut(seen, x, 1)) {
            mapFree(seen);
            return false;
        }
    }
    mapFree(seen);
    return true;
}

The range check matters because signed overflow in C is undefined. If the complement is outside the int range, no int array element can equal it, so skipping that lookup is correct.

Before iteration $i$, seen contains exactly the values in positions $0,\ldots,i-1$. If we find the complement, it belongs to an earlier position, proving a valid pair. If a valid pair exists at indices $j<i$, then when iteration $i$ arrives, a[j] is already in seen; hence it will be found. These establish both directions: every reported pair is valid, and every valid pair can be detected.

There are at most $n$ lookups and $n$ insertions. With good distribution and capacity proportional to $n$, time is expected $O(n)$ and auxiliary space $O(n)$ including the bucket array. Worst case is $O(n^2)$ if chains grow linearly. The hash table does not make the overall algorithm constant-time.

Practice. What happens for [3] with target 6, and for [3, 3] with target 6?

Odd-occurring elements: store only what matters#

Problem. Return the number of distinct integers occurring an odd number of times. The lecture example [4, 3, 4, 8, 8, 4] returns 2: 4 occurs three times, 3 once, and 8 twice.

A full counter works: count all items, then enumerate the distinct keys and count those with an odd value. But if the question only needs odd/even status, we can store less information.

Keep a set odd. On seeing x, delete it if present; otherwise insert it. Each occurrence toggles membership. After processing a prefix, x belongs to odd exactly when its prefix count is odd.

This follows from parity: adding one turns even into odd and odd into even. Returning set size therefore answers the question.

The player uses an array for the unchanged input and table rows for the odd set. Follow the concrete membership changes; it does not pretend to render a hash table's collision layout.

Practice. Is XOR-ing all input values enough to return the number of distinct odd-occurring values?

The player implements this toggling with the map from 17. Hash Tables. This copyable C routine reports allocation failure separately from the mathematical count. The map stores one dummy value per currently odd key. Checking presence before insertion is necessary: inserting unconditionally would fail to toggle even occurrences. mapRemove cannot fail here because the preceding lookup found the key; the function frees its scratch map on both success and allocation failure.

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

/* Uses mapNew/mapGet/mapPut/mapRemove/mapFree from Hash Tables. */
bool oddDistinctCount(const int a[], size_t n, size_t *out) {
    if (out == NULL || n > (SIZE_MAX - 1) / 2) return false;
    struct map *odd = mapNew(2 * n + 1);
    if (odd == NULL) return false;
    for (size_t i = 0; i < n; i++) {
        if (mapGet(odd, a[i], NULL)) {
            (void)mapRemove(odd, a[i]);
        } else if (!mapPut(odd, a[i], 1)) {
            mapFree(odd);
            return false;
        }
    }
    *out = odd->count;
    mapFree(odd);
    return true;
}

Anagrams: equality of frequency maps#

Two strings are anagrams if each character occurs equally often in both. Order can differ; multiplicity cannot. Thus "aaabb" and "ababa" match, but "aaabb" and "babab" do not: their counts of a and b differ.

Count characters in the first string and subtract occurrences from the second. Every final difference must be zero. A set would be insufficient: both "aaabb" and "babab" have the set {a,b}.

For a small known alphabet, direct indexing is simpler than hashing. For lowercase English letters, a 26-element count array is enough. The following complete routine compares C strings as sequences of bytes, case-sensitively, assuming eight-bit bytes. It treats spaces as ordinary bytes. Unicode characters or ignoring punctuation require an explicit different tokenisation policy.

#include <stdbool.h>
#include <stddef.h>
#include <limits.h>
_Static_assert(UCHAR_MAX == 255, "This example assumes 8-bit bytes");

bool anagram(const char *s, const char *t) {
    size_t counts[256] = {0};
    for (const unsigned char *p = (const unsigned char *)s; *p; p++)
        counts[*p]++;
    for (const unsigned char *p = (const unsigned char *)t; *p; p++) {
        if (counts[*p] == 0) return false;
        counts[*p]--;
    }
    for (size_t i = 0; i < 256; i++)
        if (counts[i] != 0) return false;
    return true;
}

Why can we fail immediately on a zero count? The second string has requested more of that byte than the first supplies. At the end, a remaining positive count means the second supplied too few. If neither happens, every byte count agrees.

For lengths $L_s,L_t$, time is $O(L_s+L_t+R)$, where $R$ is alphabet size; with fixed $R=256$, auxiliary space and final-array scan are constant. A hash counter instead uses space proportional to distinct symbols when the key universe is large.

Practice. Compare "abb" and "aba" using the subtraction method. At which character can failure be detected?

From a frequency table to an application#

The lecture finishes with a discussion of ordering votes dramatically at Tribal Council. A vote counter maps each candidate's identity to a number of votes, but the slide does not specify one formal ordering objective. To turn the prompt into an algorithm, first define what “dramatic” means.

For example, if the goal is to reveal a chosen available candidate's next vote, the counter can test whether that candidate has votes remaining and decrement the count. If the goal is to repeatedly choose the currently largest remaining count, a counter alone cannot identify that maximum in constant time: it would require scanning distinct candidates or maintaining a priority queue. The data structure must answer the actual repeated query.

More exam-style practice#

Work each prompt before opening its answer. State the invariant or cost assumption that makes your reasoning valid.

Question 1. Process 3,5,3,3,5,8 with a parity toggle table that stores keys occurring an odd number of times. Give the final set.

Question 2. A two-sum scan seeks target 10 in [6,4]. Why should it check the complement before inserting the current item?

Question 3. Are aab and abb anagrams? Explain the map test and its cost in terms of string length n.

For revision, practise choosing a key/value relationship before choosing the collision strategy. 21. COMP2521 Revision collects comparisons and implementation checks.