# Python sets and dictionaries can have quadratic-time performance

DevFeed: [Python sets and dictionaries can have quadratic-time performance](<https://devfeed.tech/articles/python-sets-and-dictionaries-can-have-quadratic-time-performance-29426.md>)

Original publisher: [Read original article](<https://lemire.me/blog/2026/09/03/python-sets-and-dictionaries-can-have-quadratic-time-performance/>)

Author: Daniel Lemire

Published: 2026-09-03T14:01:45Z

Content type: article

Language: en

Sources: [Daniel Lemire](<https://devfeed.tech/sources/daniel-lemire.md>)

Topics: [Python](<https://devfeed.tech/topics/python.md>), [Data structures](<https://devfeed.tech/topics/data-structures.md>), [hash](<https://devfeed.tech/topics/hash.md>), [CPU Cache](<https://devfeed.tech/topics/cpu-cache.md>)

Tags: [array](<https://devfeed.tech/tags/array.md>), [cpu-cache](<https://devfeed.tech/tags/cpu-cache.md>), [data-structure](<https://devfeed.tech/tags/data-structure.md>), [hash](<https://devfeed.tech/tags/hash.md>), [performance](<https://devfeed.tech/tags/performance.md>), [python](<https://devfeed.tech/tags/python.md>)

## AI overview

The article explains why Python sets and dictionaries are not formally constant-time in all cases. Hash collisions can make insertions and membership checks take quadratic time, while growing data structures can also incur reallocation and slower memory access as they exceed CPU cache capacity.

## Source excerpt

In Python, the dict data structure is the conventional key-value structure. E.g., you might store a list of names as keys and have their phone numbers as values. Valentin Ignatev wrote this amusing post on X: It is indeed widely believed that, in the strict sense, the dict data structure and its companion, the set ... Continue reading Python sets and dictionaries can have quadratic-time performance