Dicts, defaultdict and Counter

1. When to reach for a dict

You need to look something up by key, and you don’t care about order.

That’s most of part 1 in an interview. “Record a value for a user, return it later” is a dict, and there’s nothing more to it.

What a dict cannot answer, because it discarded order to buy O(1) lookup:

• what’s the largest or smallest → heap
• what’s the oldest → deque
• where would this go if inserted → sorted list + binary search
• which keys start with this prefix → trie

So the recognition question is always what the problem wants beyond membership. Nothing more, use a dict.

2. Storing only the latest value

The simplest case, and worth naming because the instinct is to over-build.

If you only ever return the most recent value for a key, you don’t need a container per key. You need one value:

class SessionStore:
    def __init__(self):
        self.last = {}

    def login(self, user_id, timestamp):
        self.last[user_id] = timestamp

    def last_login(self, user_id):
        return self.last.get(user_id)

.get(key) returns None for a missing key instead of raising, and .get(key, default) lets you pick what it returns. That’s the whole not-found handling.

Reach for a list per key only when the question needs the history, which is what versioned lookups are about.

3. defaultdict

defaultdict(factory) calls the factory to create a value the first time a key is touched, so you skip the “if key not in dict” line.

from collections import defaultdict

events = defaultdict(list)
events[user].append(x)       # no initialisation needed

windows = defaultdict(deque)
windows[user].append(t)

The argument is a factory, a callable that produces the default. list, deque, int, set. Not a value.

defaultdict(None) is the trap: None isn’t callable, so there’s no factory and it behaves as a plain dict, raising KeyError on a missing key. If you want None as a default, use a plain dict and .get().

Reading creates entries. d[key] on a defaultdict inserts an empty container even if you were only checking. That’s a slow leak when the keys come from user input, and it’s why a read-only path should use .get(key, default) instead.

3.1 When not to use one

The rule that keeps this from biting:

defaultdict when the values are containers you always append to. Plain dict + .get() when the values are scalars, or when absence carries meaning.

The second half is the one that costs you. If “this key is not in the dict” is how you represent removed, unknown or inactive, a structure that silently makes keys reappear on read has destroyed the thing you were relying on:

scores = defaultdict(int)
scores["a"] = 70
del scores["a"]              # removed

scores["a"]                  # 0 — and "a" is back in the dict
"a" in scores                # True. The removal is gone.

With a plain dict the same read raises KeyError, which is loud, or .get("a") returns None, which is correct.

Saving two lines of initialisation is not worth it when presence is what you are testing.

4. Counter

A dict subclass whose values are counts. Everything a dict does, plus three conveniences.

from collections import Counter

c = Counter()                    # empty
c = Counter(["a", "b", "a"])     # counts an iterable → {'a': 2, 'b': 1}

c["a"]                           # 2
c["zebra"]                       # 0, and does NOT insert the key
c.most_common(2)                 # [('a', 2), ('b', 1)] — list of (key, count) tuples

Missing keys return 0 without inserting, which is the difference from defaultdict(int). A defaultdict creates the entry when you read it; a Counter doesn’t.

most_common(k) sorts by count, highest first, and returns (key, count) tuples. Which is why extracting just the keys needs an unpack:

[word for word, _ in c.most_common(k)]

By hand that’s sorted(d.items(), key=lambda kv: kv[1], reverse=True)[:k].

4.1 update adds, it doesn’t overwrite

The one real trap. dict.update replaces values; Counter.update adds them.

c = Counter({"a": 5})
c.update(["a"])          # a is now 6, not 1

Two argument forms, and they mean different things:

c.update(["a", "a", "b"])     # iterable → counts occurrences, so a += 2
c.update({"a": 10})           # mapping  → adds the given amounts, so a += 10

The constructor takes the same two forms.

4.2 Count on write, not on read

Both of these work, and the second is better if top is called more than once:

# counts on every read — O(total words) per call
def add(self, text):  self.words.extend(text.split())
def top(self, k):     return [w for w, _ in Counter(self.words).most_common(k)]

# counts on write
def __init__(self):   self.counts = Counter()
def add(self, text):  self.counts.update(text.split())
def top(self, k):     return [w for w, _ in self.counts.most_common(k)]

Same principle as maintaining a running answer rather than recomputing it: do the work when data arrives, not when someone asks.

text.split() with no argument splits on any whitespace and collapses runs of it, which is more robust than split(' ').

5. Which one

6. Mistakes

• defaultdict(None) — not a factory, so it’s just a dict that raises.
• Reading a defaultdict inserts. Use .get() on read-only paths.
• Building a per-key list when only the latest value is needed.
• Rebuilding a Counter on every read instead of maintaining it on write.