[plt-scheme] likely -> incompatibility: hashtables

From: Matthew Flatt (mflatt at cs.utah.edu)
Date: Tue Apr 8 15:03:52 EDT 2008

At Tue, 08 Apr 2008 20:40:07 +0200, "Majorinc, Kazimir" wrote:
> Matthew Flatt wrote:
> > Immutable hash-table update will be constant time. (Well, O(lg n), but
> > the constant will be so small that it's effectively O(n).) Mutable
> > hash-table update would be O(n).
> >
> > That's different from lists, where operating on the two kinds have the
> > same complexity, and I think it's a sever enough difference to
> > discourage the operation on mutable hash tables.
> >   
> Why O(n) if you already have O(log n) immutable hash table? Isn't it 
> very easy to define at least equally efficient hash table then? Is it 
> political or technical decision?

While `hash-set!' could be implemeted with `hash-set' and a mutable
cell, the constant facter on the current `hash-set!' is lower than the
constant on `hash-set'.

In my tests, the difference is a factor of 2 to 5, depending on the
complexity of the key and including GC time.


Posted on the users mailing list.