[plt-scheme] likely -> incompatibility: hashtables

From: Majorinc, Kazimir (kazimir at chem.pmf.hr)
Date: Tue Apr 8 14:40:07 EDT 2008

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?

Posted on the users mailing list.