A hash table as a counter in Java

Problem

The best-selling products of the day

The shop dashboard shows the three best-selling products of the day. The log is a list of orders, one per line. The code keeps two lists, the names and the counts, and for every order it looks for the product from the start of the names:

List<String> log = logOf(1000);
List<String> names = new ArrayList<>();
List<Integer> counts = new ArrayList<>();
long comparisons = 0;
for (String item : log) {
    int i = 0;
    while (i < names.size()) {
        comparisons++;
        if (names.get(i).equals(item)) break;
        i++;
    }
    if (i == names.size()) {
        names.add(item);
        counts.add(1);
    } else {
        counts.set(i, counts.get(i) + 1);
    }
}
System.out.println("orders: " + log.size());
System.out.println("products: " + names.size());
System.out.println("comparisons: " + comparisons);

orders: 1000
products: 251
comparisons: 125255

A thousand orders and 251 different products: 125,255 comparisons. The catalog grows with the shop, and so does the list every order walks through. On a big day with 100,000 orders the dashboard takes minutes to load.

Where the log comes from

The log follows a formula, so that the programs in all four languages and the comparison in the browser below build exactly the same one. The catalog has n / 4 + 1 products:

static List<String> logOf(int n) {
    int catalog = n / 4 + 1;
    List<String> log = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        log.add("SKU-" + (i * 7919) % catalog);
    }
    return log;
}

The idea

The map counts

In the lesson “HashMap and HashSet” you counted orders with a map. Here it becomes a technique: a hash table as a counter (a frequency map). The key is what you count, the value is how many times you have seen it.

One pass over the data. For every element: find its counter (or 0) and add 1.
The lookup is in a hash table: O(1) on average, however many products there are. O(n) in total instead of O(n · m).
After that you answer the questions from the counts, not from the data: which one is most common, which one appears once, whether two things have the same counts.

The memory is O(m): one pair for every different product.

See it

The counter fills up

List<String> log = List.of(
    "mouse", "headset", "mouse", "monitor",
    "keyboard", "mouse", "headset", "monitor",
    "mouse", "headset");
Map<String, Integer> counts = new HashMap<>();
for (String item : log) {
    counts.merge(item, 1, Integer::sum);
}
List<Map.Entry<String, Integer>> top =
    new ArrayList<>(counts.entrySet());
top.sort((x, y) -> y.getValue() - x.getValue());
for (var e : top.subList(0, 3)) {
    System.out.println(e.getKey() + " " + e.getValue());
}

mouse 4
headset 3
monitor 2

Map<String, Integer> counts = new HashMap<>();
for (String item : log) {
    counts.merge(item, 1, Integer::sum);
}
List<Map.Entry<String, Integer>> top =
    new ArrayList<>(counts.entrySet());
top.sort((x, y) -> y.getValue() - x.getValue());
for (var e : top.subList(0, 3)) {
    System.out.println(e.getKey() + " " + e.getValue());
}

Step by step, in words

An empty map: product → how many times it was sold. The log has 10 orders.
Order 1: mouse. It is not in the map yet, so it gets a count of 1.
Order 2: headset. It is not in the map yet, so it gets a count of 1.
Order 3: mouse, 1 → 2. One lookup in the hash table, without walking the other products.
Order 4: monitor. It is not in the map yet, so it gets a count of 1.
Order 5: keyboard. It is not in the map yet, so it gets a count of 1.
Order 6: mouse, 2 → 3. One lookup in the hash table, without walking the other products.
Order 7: headset, 1 → 2. One lookup in the hash table, without walking the other products.
Order 8: monitor, 1 → 2. One lookup in the hash table, without walking the other products.
Order 9: mouse, 3 → 4. One lookup in the hash table, without walking the other products.
Order 10: headset, 2 → 3. One lookup in the hash table, without walking the other products.
10 orders, 10 counter updates. Only the 4 distinct products get sorted by count, not the orders.
The top three: mouse 4, headset 3, monitor 2.

merge(item, 1, Integer::sum) puts 1 if the key is not there, and otherwise adds 1 to the old count. The top three come from sorting the pairs by count: only the different products are sorted, not the orders.

Try it

Fill in

The line that counts:

counts.merge(item, 1, );

merge takes how to combine the old count with the new one: Integer::sum.

See it

The tools of your language

In Java the counter is a HashMap<String, Integer>. getOrDefault with put does the same as merge, but it looks the key up twice. merge looks it up once. When you need the keys sorted, Collectors.groupingBy with a TreeMap and Collectors.counting() counts in a stream:

List<String> log = List.of(
    "mouse", "headset", "mouse", "monitor",
    "keyboard", "mouse", "headset", "monitor",
    "mouse", "headset");
Map<String, Integer> counts = new HashMap<>();
for (String item : log) {
    counts.put(item, counts.getOrDefault(item, 0) + 1);
}
System.out.println(counts.get("mouse") + " " + counts.getOrDefault("tablet", 0));
Map<String, Long> sorted = log.stream()
    .collect(Collectors.groupingBy(item -> item, TreeMap::new, Collectors.counting()));
System.out.println(sorted);

4 0
{headset=3, keyboard=1, monitor=2, mouse=4}

See it

Measure: a list of pairs against a map

The same thousand orders with the map:

List<String> log = logOf(1000);
Map<String, Integer> counts = new HashMap<>();
long updates = 0;
for (String item : log) {
    counts.merge(item, 1, Integer::sum);
    updates++;
}
System.out.println("orders: " + log.size());
System.out.println("products: " + counts.size());
System.out.println("counter updates: " + updates);

orders: 1000
products: 251
counter updates: 1000

1,000 updates instead of 125,255 comparisons. Run both in the browser. n is the number of orders, and the catalog grows with it:

A list of product and count pairs O(n²)
A map as a counter O(n)

Algorithm	n = 10	n = 1,000	n = 100,000
A list of product and count pairs	16	125,255	≈ 1,252,550,000
A map as a counter	10	1,000	100,000

The code runs in your browser, in JavaScript. The number of operations is the same in every language, because the algorithm is the same. The time depends on the machine, so it is only for comparison. “≈” is an estimate from the curve: we do not run an n that big, so the page does not freeze.

Map<String, Integer> counts = new HashMap<>();
for (String item : log) {
    counts.merge(item, 1, Integer::sum);
}
List<Map.Entry<String, Integer>> top =
    new ArrayList<>(counts.entrySet());
top.sort((x, y) -> y.getValue() - x.getValue());
for (var e : top.subList(0, 3)) {
    System.out.println(e.getKey() + " " + e.getValue());
}

More precisely, if you are curious

The top k without sorting everything. Sorting m different products is O(m log m). If there are millions of products and you need the top 10, you keep a heap with at most k pairs: every pair goes in, and when there are k + 1, the smallest goes out. That is O(m log k).

A key with several parts. You count sales by city and product: the key is the pair. In Java it is a record CityItem(String city, String item): a record has equals and hashCode over its fields.

The idea

The basket and the kit

The “home office” kit is a monitor, a keyboard, a mouse and two cables. The warehouse checks that the basket to be shipped is exactly the kit: nothing extra, nothing missing. The order does not matter, the counts do.

One counter: +1 for every product of the kit, −1 for every product in the basket. The basket matches if all counts end up at 0.

static boolean matches(List<String> kit, List<String> basket) {
    Map<String, Integer> need = new HashMap<>();
    for (String item : kit) need.merge(item, 1, Integer::sum);
    for (String item : basket) need.merge(item, -1, Integer::sum);
    for (int n : need.values()) {
        if (n != 0) return false;
    }
    return true;
}

The same check finds anagrams: “listen” and “silent” have the same letters with the same counts. The counter is over letters instead of products.

Try it

Predict the check

List<String> kit = List.of(
    "monitor", "keyboard", "mouse", "cable",
    "cable");
List<String> basket1 = List.of(
    "cable", "mouse", "monitor", "cable",
    "keyboard");
List<String> basket2 = List.of(
    "monitor", "keyboard", "mouse", "mouse",
    "cable");
System.out.println("basket 1: " + (matches(kit, basket1) ? "complete kit" : "does not match"));
System.out.println("basket 2: " + (matches(kit, basket2) ? "complete kit" : "does not match"));

Answer

basket 1: does not match
basket 2: complete kit

basket 1: complete kit
basket 2: complete kit

basket 1: complete kit
basket 2: does not match

The idea

The first customer with a single order

Marketing sends a “come back” voucher to the customers who ordered only once. It wants the first one in time. The counter gives the counts, but not the order:

static String firstSingle(List<String> customers) {
    Map<String, Integer> counts = new HashMap<>();
    for (String c : customers) counts.merge(c, 1, Integer::sum);
    for (String c : customers) {
        if (counts.get(c) == 1) return c;
    }
    return null;
}

List<String> customers = List.of(
    "C-17", "C-4", "C-17", "C-9",
    "C-4", "C-21", "C-9", "C-30");
System.out.println("first customer with one order: " + firstSingle(customers));

first customer with one order: C-21

Two passes: the first one counts, the second walks the log, in the order of the orders, and stops at the first one with a count of 1. O(n), with no nested loop.

More precisely, if you are curious

Why does the second pass walk the log and not the map? A HashMap keeps no order at all: walking it goes bucket by bucket. A LinkedHashMap keeps insertion order, and then walking the map also works.

The idea

Two products for exactly €50

The customer has a voucher for exactly €50 and wants two products that use it up. The prices in the catalog are not sorted.

You walk through the prices and for each one you ask: have I already seen the price that tops this one up to 50? The map keeps the prices seen so far and their positions:

static int[] voucherPair(int[] prices, int voucher) {
    Map<Integer, Integer> seen = new HashMap<>();
    for (int i = 0; i < prices.length; i++) {
        Integer j = seen.get(voucher - prices[i]);
        if (j != null) return new int[] { j, i };
        seen.put(prices[i], i);
    }
    return null;
}

int[] prices = { 27, 14, 33, 25, 8, 36, 19 };
int[] p = voucherPair(prices, 50);
System.out.println("products " + p[0] + " and " + p[1] + ": €" + prices[p[0]] + " + €" + prices[p[1]]);

products 1 and 5: €14 + €36

One pass: O(n) time and O(n) memory. With two pointers it works without a map, with O(1) memory, but the prices must be sorted. If they are not, sorting costs O(n log n) and loses the position of every product in the catalog. So: sorted data, two pointers; unsorted data, a map.

Try it

Find the bug

Someone swapped two lines. Now for a €50 voucher the program offers one product twice:

int[] prices = { 27, 14, 33, 25, 8, 36, 19 };
int[] p = voucherPair(prices, 50);
System.out.println("products " + p[0] + " and " + p[1] + ": €" + prices[p[0]] + " + €" + prices[p[1]]);

products 3 and 3: €25 + €25

Pick the line with the bug.

Exercise

Who spends the most

Solve the task in your own editor.

Revenue per customer. The log has pairs of customer and amount: C-4 for €30, C-17 for €55, C-4 for €20, C-9 for €80, C-17 for €10 and C-4 for €45. Add up the amounts per customer with a map (the value is a sum, not a count) and print the two who spent the most:

C-4: €95
C-9: €80

More tasks

Anagrams. Write a check whether two words are anagrams (“listen” and “silent”) by counting the letters with a map. How many operations does it take for words of length n?
The first repeat. Find the first order whose customer has already ordered before. Do you need a counter, or is a set enough?
Periods with equal counts. From prefix sums you know how to count periods with a given sum. Count the periods of consecutive days in which the number of returned orders equals the number of delivered ones.

Test

Check yourself

1. The log has 100,000 orders and 25,000 different products. How many counter updates does the map make?25,000: one per product100,000 · 25,000100,000: one per order

2. How do you check with one map that the basket is exactly the kit?+1 for every product of the kit, −1 for every product in the basket, and every count must be 0Sort both lists and compare them, no map neededCheck that every product in the basket is in the kit

3. In voucherPair the price goes into the map after the lookup for its pair. Why not before?Because of speedIt does not matterOtherwise a €25 product finds itself for a €50 voucher

4. When are two pointers the better choice for a pair with a given sum?Always, because they are fasterWhen the prices are already sorted: no map and no extra memoryNever

5. You need the top 10 of 2,000,000 different products. What is cheapest?Look for the largest ten timesSort all 2,000,000 pairsA heap with at most 10 elements: O(m log k)

A hash table as a counter

Cookies