[Python-ideas] set.add() return value

Antoine Pitrou solipsis at pitrou.net
Fri Feb 13 15:39:27 CET 2009

Steven D'Aprano <steve at ...> writes:
> It's true that the results you found aren't consistent with O(1), but as 
> I understand it, Python dicts are O(1) amortized ("on average over the 
> long term").

They are not O(1) amortized, but O(1) best case. The worst case being O(N) (if
all keys fall in the same hash bucket). The whole game with hash tables is to
find a sufficiently smart hash function such as keys are equiprobably
distributed amongst buckets and lookup cost is O(1) rather than O(n).

Hash functions can be improved over time, a recent example can be found at



More information about the Python-ideas mailing list