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.