How do you deduplicate a list in Python while preserving first-seen order?

## The two candidate tools Deduplicating a sequence means collapsing elements that are **equal**, and Python decides equality for hashed containers with the pair `__hash__` and `__eq__`. Both tools below therefore require hashable elements. What separates them is the order of what comes out. `set(items)` builds a hash set. Iterating a set walks its internal table, so the output order is a function of each element's hash value and of the table's resize history, not of the order you inserted. For small integers this is deceptive: `hash(n) == n` for small ints, so `set([3, 1, 2])` frequently iterates ascending and people conclude that sets sort. They do not. For strings, hash randomization is on by default (seeded per process, pinnable with the `PYTHONHASHSEED` environment variable), so the same program can print a different order on the next run. Any code whose output depends on set iteration order is a flaky test waiting to happen. `dict.fromkeys(items)` is a classmethod that builds a dict whose keys are the elements and whose values are all `None` (an optional second argument supplies a different fill value). Duplicate elements collapse into one key. Since Python 3.7 a dict's iteration order is a documented **language guarantee** of insertion order; CPython 3.6 already behaved that way, but only as an implementation detail nobody was allowed to rely on. So `list(dict.fromkeys(items))` is the canonical order-preserving dedupe, and it is one expression. ```python >>> list(dict.fromkeys(["b", "a", "b", "c"])) ['b', 'a', 'c'] ``` The `list(...)` wrapper matters: iterating a dict yields its keys, but a dict is not a list, so callers expecting a sequence want the conversion. ## Why the *first* occurrence wins A key's position in a dict is fixed the first time it is inserted. Re-assigning a key that already exists updates its value but does **not** move it to the end. `dict.fromkeys` re-assigns `None` over `None`, so every later duplicate is a no-op for both the value and the position. You keep the first element you saw, where you first saw it. That distinction only becomes visible when "equal" does not mean "identical". `1`, `True` and `1.0` are all equal and share a hash, so they collapse into a single key, and it is whichever one appeared first that is kept: ```python >>> dict.fromkeys([1.0, True]) {1.0: None} ``` The same applies to any class with a custom `__eq__` and `__hash__`: two objects that compare equal but carry different payloads will leave you holding the first one. If you need the last one instead, feed the reversed sequence and reverse the result, or key the survivors explicitly. ## Cost Both `set` and `dict.fromkeys` are a single pass with O(1) average hashing per element, so both are O(n) time and O(k) extra space for k unique elements. The idiom people reach for before they know either one is ```python out = [] for x in items: if x not in out: out.append(x) ``` which is O(n squared), because `in` on a list is a linear scan. It is fine for ten items and a genuine production hazard for a hundred thousand. `dict.fromkeys` does allocate a full dict rather than a set, so each unique element costs a table entry plus a value slot; that overhead is real but almost never the deciding factor next to correct ordering. ## Iterables and iterators Both accept any iterable, including a generator, and both consume it exactly once. `list(dict.fromkeys(line.strip() for line in stream))` is a complete deduplicating read of a stream. Because the whole result is materialized, memory scales with the number of **unique** elements, not with the input length, which is why this idiom survives inputs far larger than the output. ## Where the one-liner stops working Two cases break it. If elements are unhashable, such as `dict` or `list` instances, both tools raise `TypeError` and you need a hashable stand-in key. And if you want to deduplicate by a *derived* value, keeping the first record per user id rather than per whole record, `dict.fromkeys` cannot express it at all, because it keys on the entire element; that case needs an explicit `seen` set inside a loop. ## Interview framing Interviewers ask this to see whether you reach past the obvious `set()`. Saying "`set(items)`" is a correct answer to a question that was not asked. The strong answer states the ordering guarantee, names the version it became a guarantee, and mentions that the elements must be hashable either way.