Built-in collections: list, tuple, dict and set — what to use when

Base: four collections and three questions

A junior-level answer to "what to use when": a list for an ordered collection that changes; a tuple for an immutable record of a few fields; a dictionary when a value is looked up by key; a set when you need unique elements and a fast "is it there" check. That is correct, and it is usually followed by three follow-up questions: how much faster the check on a set is, why a list cannot be put into a set, and what about order. That is what the mechanisms below are about.

How a list differs from a tuple in memory and speed is a separate lesson, "List versus tuple". Here the choice is among all four.

Mechanism 1: repeats and uniqueness

Output of bench/collections/basics.py, section 1 (labels translated):

1) duplicates
   list(data)          -> [3, 1, 3, 2, 1]
   set(data)           -> {1, 2, 3}
   dict.fromkeys(data) -> {3: None, 1: None, 2: None}
   {'a': 1, 'a': 2}    -> {'a': 2}
   len(set(data)) == len(data) -> False

A list keeps everything put into it. A set keeps only distinct elements, and the order of the source list is lost. A dictionary keeps unique keys, and when a key is repeated the last value wins.

This output gives two working techniques:

• "Are there duplicates" — len(set(data)) != len(data).
• "Remove duplicates, keeping the order" — list(dict.fromkeys(data)). A set cannot do this: a set has no order (Mechanism 3), while a dictionary does.

Mechanism 2: hashability — who can be a key

Set elements and dictionary keys must be hashable; dictionary values need not be. A set and a dictionary find an element or a key by its hash, so it must have a hash, and the hash must not change; a dictionary value sits next to its key, nothing is looked up by it, and there is no reason to hash it:

A short complete example shows it. The full file bench/collections/hashable.py:

import sys
 
print("PY", sys.version.split()[0])
 
d = {"items": []}
d["items"].append(1)
print('{"items": []} after append:', d)
print('{(1, 2): "ok"}:', {(1, 2): "ok"})
 
for text, make in [('{[]: "x"}', lambda: {[]: "x"}), ("{[1, 2]}", lambda: {[1, 2]})]:
    try:
        make()
    except TypeError as e:
        print(text, "-> TypeError:", e)

Run it with python3.13 bench/collections/hashable.py; the output on CPython 3.13.7 (the same on 3.11 and 3.12), exactly as printed:

PY 3.13.7
{"items": []} after append: {'items': [1]}
{(1, 2): "ok"}: {(1, 2): 'ok'}
{[]: "x"} -> TypeError: unhashable type: 'list'
{[1, 2]} -> TypeError: unhashable type: 'list'

The dictionary with a list as its value was created and even changed in place; the tuple became a key. A list fits neither as a key nor as a set element. More on what is hashable — the output of bench/collections/basics.py, section 2 (labels translated):

2) hashability: what can go into a set and into dict keys
   {[1, 2]}            -> TypeError: unhashable type: 'list'
   {[1, 2]: 'x'}       -> TypeError: unhashable type: 'list'
   {(1, 2)}            -> no exception
   {(1, [2])}          -> TypeError: unhashable type: 'list'
   {frozenset({1, 2})} -> no exception
   {{1, 2}}            -> TypeError: unhashable type: 'set'

The line worth remembering is {(1, [2])}. A tuple is hashable only if everything in it is hashable: the hash of a tuple is computed from the hashes of its elements, and a list has none. That is why a key "of several fields" is a tuple of immutable values, and a set of sets is built from frozenset.

Why mutable objects that are compared by value — lists, dictionaries, sets — have no hash: a dictionary places a key by its hash and later looks it up by the same hash. If such a key changed after it was inserted, its hash would change, and the dictionary would look in the wrong place. A value has no such problem: it is not looked up by hash, so d["items"].append(1) above breaks nothing. Instances of ordinary classes are mutable but hashable: they are compared by identity, not by value — see the lesson "Classes and OOP". How this works inside is covered in the article on dictionaries.

Mechanism 3: order — a dictionary has it, a set does not

A set has no such guarantee. The order in which it prints depends on the hashes of its elements, and the hash of a string differs from run to run:

That random "seed" can be fixed with the PYTHONHASHSEED environment variable. The script ran itself three times with different values — the output of bench/collections/basics.py, section 3. The script uses Russian fruit names as its strings; below they and the labels are translated, so this exact text will not appear in the run, and the orders shown are those of the original strings:

3) order
   dict in insertion order: ['melon', 'apple', 'pear']
   removed and inserted again — the key is at the end: ['melon', 'pear', 'apple']
   a set of strings under different PYTHONHASHSEED values:
   PYTHONHASHSEED=1: ['melon', 'pear', 'plum', 'apple', 'cherry']
   PYTHONHASHSEED=2: ['cherry', 'apple', 'melon', 'plum', 'pear']
   PYTHONHASHSEED=3: ['melon', 'plum', 'apple', 'pear', 'cherry']
   distinct orders out of three runs: 3
   a set of integers {5, 1, 3}: {1, 3, 5} — the order comes from the hash, not from insertion
   hash(1), hash(3), hash(5): 1 3 5 — the hash of a small integer equals the integer itself
   a set of integers {8, 1}: {8, 1} — and not always in ascending order

The last lines are a trap in reverse. A set of small integers often prints "in ascending order", because the hash of a small integer equals the integer itself. But that is a coincidence of the implementation, not sorting: {8, 1} printed as {8, 1}, and code that relies on the order will break on strings. If you need order, use a list, a dictionary or sorted(...).

Mechanism 4: the cost of a lookup — where the difference is huge and where there is none

The documentation names "fast membership testing" as the first use of sets. How fast is a matter of measurement. The element sought is the last one, which is the worst case for a list:

A list checks the elements one by one, so its time grows with the size. A set and a dictionary compute the hash and go to the right place in the table; when the hashes are well spread, as with these integers, only a few slots need checking — so their time grows by a few times, not by thousands of times like the list's. A tuple behaves like a list: it is a sequence too.

But O(1) for a set and a dictionary is an average estimate, not a promise of one check. If many keys share one hash, a lookup compares them one by one, and the worst case is O(n): in the lesson "Complexity of operations" a lookup in a set of a hundred objects with the same hash called __eq__ 105 times, not once. And a single check is not free either: it costs computing the hash and a call to __eq__, and for a long string both go over its characters.

The numbers also include the for loop the check ran in: an empty loop costs 18.7 ns per step — the "empty loop" row in the run record. At large sizes that is negligible, but at ten elements it is half of the set's time, so 3.4 times is a lower bound: the checks themselves differ more.

But the rule "always a set" does not work for small collections. On ten elements the difference is only 3.4 times, and if the element sought is the first one, the list finds it in 33.7 ns — as fast as the set. And building a set for a single check does not pay: building hashes every element and places it in the table. The measurement above does not see this — there the collections are ready before the clock starts — so building was measured separately. The output of bench/collections/build.py (CPython 3.13.7; labels translated):

building a set for the checks: ns per scenario, medians of 9 rounds
      size    checks     by list     set(lst) + checks
        10         1        98.8                 211.1
        10       100      8499.6                1962.7
      1000         1      4638.7                7926.6
      1000       100    596511.4               10674.0

For a single check, building the set lost to the scan both at ten and at a thousand elements; for a hundred checks it won. A set pays off when there are many checks; if it already exists, it is faster even at ten elements. Where the break-even point lies on your data is a matter of measurement, not of a rule.

Mechanism 5: a queue is not a list

Output of bench/collections/cost.py, section 2 (labels translated):

2) removal from the front: 50,000 removals from a collection of 100,000, ns per removal
   (building the collection is not part of the measurement)
   form                             min    median       max
   list.pop(0)                  11920.9   12662.3   13358.6
   deque.popleft()                 41.6      42.4      47.3
   list.pop() from the end         42.5      43.7      46.3
   list.pop(0) / deque.popleft() by medians: 299

A list stores its elements contiguously, and removing the first one shifts all the others by one position — the longer the list, the more it costs. Removing from the end shifts nothing, so list.pop() is cheap. For a queue — "append to the end, take from the front" — the standard library has collections.deque, which its docstring describes as "a list-like sequence optimized for data accesses near its endpoints". In the measurement popleft() was 299 times cheaper than list.pop(0).

Deeper: what memory costs

Output of bench/collections/basics.py, section 4 (labels translated):

4) memory: the container itself for 1000 integers, bytes (sys.getsizeof)
   list     8056
   tuple    8040
   set     32984
   dict    36952
   set / list: 4.1

sys.getsizeof counts the container itself, without its elements: the numbers are shared and do not count. A list and a tuple store one pointer per element — 8 bytes on a 64-bit build — plus a header. A set and a dictionary hold a hash table with a reserve of empty slots — without that reserve, lookup by hash would stop being fast — plus bookkeeping data. Hence 4.1 times more memory for the set: that is the price of a fast in. But 4.1 is the ratio for a thousand integers on this version, not a constant: it depends on the number and kind of elements and on the implementation.

In CPython a set and a dictionary are built differently. In a set each table slot is a pointer to the element plus its cached hash (setentry, Include/cpython/setobject.h:20–23 in CPython 3.13.7). A dictionary is an index table (dk_indices) plus a separate array of entries (dk_entries). A general entry stores the hash, the key and the value (PyDictKeyEntry, Include/internal/pycore_dict.h:76–81), while an entry of a dictionary whose keys are all strings stores only the key and the value (PyDictUnicodeEntry, lines 83–86): a string keeps its hash in itself (the hash field, Include/cpython/unicodeobject.h:101). It shows in memory — the output of bench/collections/basics.py, section 6, identical on 3.11–3.14 (labels translated):

6) memory and the kind of keys: 1000 keys, bytes (sys.getsizeof)
   dict, int keys      36952
   dict, str keys      26032
   set, int            32984
   set, str            32984

A dictionary with the same thousand keys, but strings, is 10,920 bytes smaller; a set's size does not depend on the kind of elements. The details are in the articles on how lists and dictionaries are built.

How to answer in an interview

Short answer: a list is an ordered mutable collection with repeats, a tuple is immutable, a dictionary maps key → value with unique keys, a set holds unique elements without order. Membership checks and lookups by value are done on a set or a dictionary: there it is a hash lookup — O(1) on average and O(n) in the worst case, when hashes coincide — in a list it is a scan. Only a hashable object can be a set element or a dictionary key; dictionary values can be anything. A dictionary keeps insertion order, a set does not.

That is enough for a correct answer. What follows is what you add if the interviewer digs.

If the interviewer digs deeper

On "how much faster is a set". "It depends on the size and on the data. In my run on CPython 3.13.7 x in on a list of a thousand elements was 216 times slower, on ten — 3.4 times, and the list finds its first element just as fast. Building a set for a single check is not worth it: in the measurement it took longer than one scan and paid off at a hundred checks. A set's O(1) is the average: with coinciding hashes a lookup degenerates into a scan. The exact ratios on another machine have to be measured."

On "why can't a list go into a set". "A set searches by hash, and the hash of a mutable object could change after insertion. That is why a list has no hash. A tuple is hashable only if everything in it is: {(1, [2])} fails. But a list can be a dictionary value — values are not looked up: {"items": []} works."

On "is a dictionary ordered". "Since 3.7 insertion order is a language guarantee. A key that is removed and inserted again goes to the end. A set has no order: a set of strings printed differently under different PYTHONHASHSEED values."

On "how to make a queue". "collections.deque. list.pop(0) shifts all the elements — in my run it cost 299 times more than popleft() on a hundred thousand."

Next they ask

Common misconceptions

Version history

Practice

Two problems. Answer first, then check against the real output: in both, the correct answer is taken from a run of the script rather than assigned.

words = ["b", "a", "b", "c", "a"]
print(list(dict.fromkeys(words)))
print(sorted(set(words)))
print(len(set(words)), len(words))

['b', 'a', 'c']
['a', 'b', 'c']
3 5

['a', 'b', 'c']
['a', 'b', 'c']
3 5

['b', 'a', 'b', 'c', 'a']
['a', 'b', 'c']
5 5

['b', 'a', 'c']
['b', 'a', 'c']
3 3

Check yourself

How it was measured

The numbers of this lesson come from these scripts. Each one opens right from here — together with the record of its run: what it ran on, what came out and with what spread.

Observations without time — CPython 3.11.15, 3.12.3, 3.13.7 and 3.14.7; time measurements — 3.13.7 and 3.14.7 on one machine with two cores. The scripts bench/collections/hashable.py, bench/collections/build.py and section 6 of bench/collections/basics.py were added and run on 14.10.2026 on linux/x86_64. Contracts and quotes were checked on 14.10.2026. The lesson did not run Python 3.15 (released on 9 October 2026) — there is only a line about it in the version history.

• bench/collections/basics.py
• bench/collections/cost.py
• bench/collections/build.py
• bench/collections/hashable.py
• bench/collections/practice.py