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

[Antoine Pitrou]

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
http://bugs.python.org/issue5186.

Regards

Antoine.