A hash table as a counter in C#

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:

var log = LogOf(1000);
var names = new List<string>();
var counts = new List<int>();
long comparisons = 0;
foreach (var item in log)
{
    int i = 0;
    while (i < names.Count)
    {
        comparisons++;
        if (names[i] == item) break;
        i++;
    }
    if (i == names.Count)
    {
        names.Add(item);
        counts.Add(1);
    }
    else
    {
        counts[i]++;
    }
}
Console.WriteLine($"orders: {log.Count}");
Console.WriteLine($"products: {names.Count}");
Console.WriteLine($"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;
    var log = new List<string>();
    for (int i = 0; i < n; i++)
    {
        log.Add($"SKU-{(i * 7919) % catalog}");
    }
    return log;
}

The idea

The map counts

In the lesson “Dictionary 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 = [
    "mouse", "headset", "mouse", "monitor",
    "keyboard", "mouse", "headset", "monitor",
    "mouse", "headset"
];
var counts = new Dictionary<string, int>();
foreach (var item in log)
{
    counts[item] = counts.GetValueOrDefault(item) + 1;
}
var top = counts.OrderByDescending(e => e.Value).Take(3);
foreach (var (item, n) in top)
{
    Console.WriteLine($"{item} {n}");
}

mouse 4
headset 3
monitor 2

var counts = new Dictionary<string, int>();
foreach (var item in log)
{
    counts[item] = counts.GetValueOrDefault(item) + 1;
}
var top = counts.OrderByDescending(e => e.Value).Take(3);
foreach (var (item, n) in top)
{
    Console.WriteLine($"{item} {n}");
}

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.

GetValueOrDefault(item) returns 0 for a product that is not there yet, so the first order gives 1. 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[item] = counts.(item) + 1;

GetValueOrDefault returns the value, or 0 for a key that is not there.

See it

The tools of your language

In C# the counter is a Dictionary<string, int>. TryGetValue reads without an exception for a missing key. counts[item] = counts.GetValueOrDefault(item) + 1 looks the key up twice: once to read, once to write. CollectionsMarshal.GetValueRefOrAddDefault gives a reference (ref) to the value inside the table, and you increase it in place with one lookup. Since .NET 9 LINQ also has ready-made counting, CountBy, in the order of first appearance:

List<string> log = [
    "mouse", "headset", "mouse", "monitor",
    "keyboard", "mouse", "headset", "monitor",
    "mouse", "headset"
];
var counts = new Dictionary<string, int>();
foreach (var item in log)
{
    ref int slot = ref CollectionsMarshal.GetValueRefOrAddDefault(counts, item, out _);
    slot++;
}
Console.WriteLine($"{counts["mouse"]} {(counts.TryGetValue("tablet", out int t) ? t : 0)}");
foreach (var (item, n) in log.CountBy(x => x))
{
    Console.WriteLine($"{item} {n}");
}

4 0
mouse 4
headset 3
monitor 2
keyboard 1

See it

Measure: a list of pairs against a map

The same thousand orders with the map:

var log = LogOf(1000);
var counts = new Dictionary<string, int>();
long updates = 0;
foreach (var item in log)
{
    counts[item] = counts.GetValueOrDefault(item) + 1;
    updates++;
}
Console.WriteLine($"orders: {log.Count}");
Console.WriteLine($"products: {counts.Count}");
Console.WriteLine($"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.

var counts = new Dictionary<string, int>();
foreach (var item in log)
{
    counts[item] = counts.GetValueOrDefault(item) + 1;
}
var top = counts.OrderByDescending(e => e.Value).Take(3);
foreach (var (item, n) in top)
{
    Console.WriteLine($"{item} {n}");
}

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 C# it is a tuple (city, item) or a record: both have Equals and GetHashCode over their 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 bool Matches(List<string> kit, List<string> basket)
{
    var need = new Dictionary<string, int>();
    foreach (var item in kit) need[item] = need.GetValueOrDefault(item) + 1;
    foreach (var item in basket) need[item] = need.GetValueOrDefault(item) - 1;
    return need.Values.All(n => n == 0);
}

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 = [
    "monitor", "keyboard", "mouse", "cable",
    "cable"
];
List<string> basket1 = [
    "cable", "mouse", "monitor", "cable",
    "keyboard"
];
List<string> basket2 = [
    "monitor", "keyboard", "mouse", "mouse",
    "cable"
];
Console.WriteLine($"basket 1: {(Matches(kit, basket1) ? "complete kit" : "does not match")}");
Console.WriteLine($"basket 2: {(Matches(kit, basket2) ? "complete kit" : "does not match")}");

Answer

basket 1: complete kit
basket 2: complete kit

basket 1: does not match
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)
{
    var counts = new Dictionary<string, int>();
    foreach (var c in customers) counts[c] = counts.GetValueOrDefault(c) + 1;
    foreach (var c in customers)
    {
        if (counts[c] == 1) return c;
    }
    return null;
}

List<string> customers = [
    "C-17", "C-4", "C-17", "C-9",
    "C-4", "C-21", "C-9", "C-30"
];
Console.WriteLine($"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 Dictionary in today’s .NET walks in insertion order as long as nothing has been removed, but the documentation does not promise it. Do not rely on it.

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, int)? VoucherPair(int[] prices, int voucher)
{
    var seen = new Dictionary<int, int>();
    for (int i = 0; i < prices.Length; i++)
    {
        if (seen.TryGetValue(voucher - prices[i], out int j)) return (j, i);
        seen[prices[i]] = i;
    }
    return null;
}

int[] prices = { 27, 14, 33, 25, 8, 36, 19 };
var (a, b) = VoucherPair(prices, 50).Value;
Console.WriteLine($"products {a} and {b}: €{prices[a]} + €{prices[b]}");

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 };
var (a, b) = VoucherPair(prices, 50).Value;
Console.WriteLine($"products {a} and {b}: €{prices[a]} + €{prices[b]}");

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