Python sets en dictionaries kunnen een kwadratische tijdcomplexiteit hebben

Het is inderdaad algemeen aangenomen dat de dict-datastructuur en diens begeleider, de set-datastructuur, in strikte zin $O(1)$ zijn. Dit betekent dat naarmate je de omvang van de datastructuur vergroot, de tijd om een sleutel in te voegen of op te vragen constant blijft.

Laten we deze bewering onderzoeken.

Hoe hash-tabellen werken

Een hash-functie is een functie die objecten (zoals strings, integers, etc.) omzet in integer-waarden. We verwachten doorgaans dat hash-functies zich random-achtig gedragen, hoewel ze binnen de huidige programma-uitvoering altijd hetzelfde object naar dezelfde integer moeten mappen. Op basis van hash-functies construeren we hash-tabellen:

1. Maak een array van buckets.
2. Pas bij een gegeven object de hash-functie toe om het naar een bucket te mappen.
3. Sla het object op in de bucket. Wanneer de bucket al bezet is, wordt er een andere truc gebruikt (zoals het gebruik van een nabijgelegen bucket).

Als alles goed gaat, nemen toegang en invoeging in een hash-tabel bijna constante tijd in beslag, wat betekent dat de tijd die ze kosten onafhankelijk is van de omvang van de hash-tabel.

Dit is in veel gevallen bijna waar, maar formeel gezien is het onjuist. Er zijn veel redenen waarom dit niet klopt. Zo kan het nodig zijn om opnieuw toe te wijzen (reallocate) wanneer de datastructuur groeit, wat doorgaans tijd kost die proportioneel is aan de omvang van de datastructuur. Daarnaast hebben we te maken met collisies. Een collisie treedt op wanneer twee objecten dezelfde hash-waarde hebben. Bij het gebruik van hash-tabellen gaan we ervan uit dat collisies zeldzaam zijn, maar het is niet moeilijk om er veel te creëren door zorgvuldig objecten te kiezen.

Bewijs van kwadratische tijdcomplexiteit

In Python zijn set en dict hash-tabellen. Ik kan mijn versie van Python 'gemakkelijk' laten instorten:

M = (1 << 61) - 1
values = [i * M for i in range(1, n + 1)]
s = set(values)                       # invoegingen
count = sum(v in s for v in values)   # controles

Als de invoegingen en de controles constant-tijd operaties zijn, dan zouden de gehele constructie en de volledige controle lineaire tijd in beslag moeten nemen. Ik heb dit uitgevoerd op een Apple M4 Max met Python 3.14, waarbij de mediaan van drie runs is gerapporteerd.

De tijd verviervoudigt ongeveer elke keer dat $n$ verdubbelt. Dat is kwadratische tijd, niet lineaire tijd. De lidmaatschapscontroles (membership checks) gedragen zich op dezelfde manier: 1066 ms bij $n = 16000$. Bij honderdduizend elementen duurt het bouwen van de set 45 seconden.

Modellen versus de realiteit

Zouden we een hash-tabel kunnen maken die echt constante tijd hanteert? Nee. Naarmate de omvang van je datastructuur groeit, is er progressief trager geheugen nodig. Als je een kleine hash-tabel hebt, kan deze in de CPU-cache verblijven en snel zijn. Zodra deze een omvang van megabytes bereikt, bevindt de datastructuur zich doorgaans in het RAM-geheugen, wat veel trager is. Uiteindelijk moet je het op een schijf opslaan, wat nog trager is, enzovoort.

Anders gezegd: beweren dat een hash-tabel $O(1)$ of constante tijd is, is een model. Het kan waar zijn, misschien zelfs vaak, maar het is niet de realiteit. Modellen zijn geweldige hulpmiddelen voor onderwijs: ze presenteren een vereenvoudigd model dat je snel kunt leren. Maar modellen kunnen ook vooroordelen (biases) introduceren in hoe we denken.

Bijvoorbeeld, zelfs nadat je de paragraaf hebt gelezen waarin staat dat de dict-datastructuur trager wordt, geloof je het misschien niet. Je kunt er ook nog steeds van overtuigd zijn dat het doorgaans de snelste aanpak is die je kunt gebruiken.

Praktijkvoorbeeld: Cache-effecten

Laten we een ander praktisch geval bekijken. Stel dat je een grote map hebt van strings naar integers, die je één keer bouwt en daarna alleen bevraagt. Dit is een veelvoorkomende situatie: een woordenboek van woorden naar identifiers, een opzoektabel van landcodes, of een tabel van functienamen.

De fastconstmap-bibliotheek bouwt een onveranderlijke (immutable) map vanuit een dict[str, int]. Dit is geschikt wanneer je sleutels vooraf bekend zijn.

Ik bouw een map van een miljoen willekeurige strings van zestien tekens naar integers, en zoek vervolgens elke sleutel op in een willekeurige volgorde. Met een dict schrijf ik de voor de hand liggende loop:

total = 0
for k in probes:
    total += d[k]

Met fastconstmap vraag ik alle sleutels tegelijk op en schrijf ik de waarden in een buffer die ik zelf beheers, zodat er per sleutel geen Python-object wordt gealloceerd:

out = array("Q", bytes(8 * n))
cm.get_many_into(probes, out)

Ik ben genereus tegenover de dict. Ik hergebruik dezelfde string-objecten voor de opzoeken, en een Python-string cached zijn hash-waarde de eerste keer dat deze wordt berekend. De dict betaalt dus helemaal niet voor het hashen, terwijl fastconstmap elke sleutel elke keer hasht. Hier zijn de resultaten, in nanoseconden per sleutel.

De dict is niet constante tijd. De tijd per sleutel loopt op van 22 ns naar 202 ns naarmate de map groeit, een factor negen. Dit komt niet doordat het algoritme is veranderd of door collisies. Het komt doordat een miljoen sleutels, hun string-objecten en hun integer-objecten ongeveer 116 bytes per sleutel innemen, waardoor de opzoeken de cache missen. De fastconstmap-versie heeft 9 bytes per sleutel nodig en blijft dus veel langer in de cache. Let op hoe de cijfers schalen: de dict wordt 10 keer trager naarmate de omvang toeneemt.

De les is altijd dezelfde. Sommige modellen zijn nuttig, maar geen van hen is de realiteit. Wees je bewust van cognitieve vooroordelen.

***

Bronverwijzing: Daniel Lemire, "Python sets and dictionaries can have quadratic-time performance," in Daniel Lemire's blog, 3 september 2026, https://lemire.me/blog/2026/09/03/python-sets-and-dictionaries-can-have-quadratic-time-performance/.