Python sets and dictionaries can have quadratic-time performance
Summary
The article analyzes Python's dict and set as hash tables and demonstrates that their performance is not strictly constant-time. Through a micro-benchmark, it shows how time grows roughly quadratically as the data set grows, driven by memory access and cache effects. It also discusses the fastconstmap library as a cache-friendly alternative and emphasizes that modeling assumptions (like O(1) for dict) are just simplifications.