Time complexity of dictionary insertions

[tim_one at email.msn.com]

In article <371F2125.BEC5F892 at fzi.de>,
  Oliver Ciupke <ciupke at fzi.de> wrote:
> As I understood from the Python documentation, dictionaries are
> implemented as extensible hash tables.

Yes.

> What I didn't find either in the references or in the FAQ is: what is
> the actual time complexity for an insertion into a dictionary?

Min O(1), Max O(N), Ave O(1).  If the hash function is doing a terrible job
(e.g. maps every key to the same hash value), make those all O(N).

> Do the old contents (probably references)

Yes.

> have to be copied when extending (doubling?)

Approximately doubling, yes.

> the dictionary?

Right.

> I guess updates and deletions have constand complexity, right?

No; see above for insertion.  Deletion is O(1) always, because Python doesn't
try to shrink the table by magic (if you stick in a million keys and then
delete them, the table will still contain a million "this entry isn't being
used" markers).

> If the complexity of insertion is something like n*log(n), does anyone
> know measurements "how linear" the real measured times are?

In practice, with a non-pathological hash function + key distribution combo,
insertion & deletion act like O(1) on average.

for-more-details-see-the-source-code<wink>ly y'rs  - tim

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own