6 Mar
2008
6 Mar
'08
4:48 p.m.
Hi
I learned at school, and I teach my students, * balanced binary tree: costs are log(size) * hashtable: cost are essentially constant
All true, but log(1000) = 10 [nitpick, its nearly always log base 2, not base 10]. 10 ~= constant.
... but indeed some experiments with Data.Map and Data.Hashtable support the point you made. That's either good for Data.Map or bad for Data.Hashtable.
I think both of those are true. Hashtable isn't a natural functional data structure, so is ignored, so is not improved. I suspect a Trie would be a much better data structure for most of the uses of Hashtable, but alas there is not one in the standard libraries. Thanks Neil