[Python-ideas] set.add() return value
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