Data.HashTable

[apfelmus]

Johannes Waldmann wrote:
> I learned at school, and I teach my students,
>   * balanced binary tree: costs are log(size)
>   * hashtable: costs are essentially constant

Correction:
     * hashtable: costs are  key size in bits
                    which is always >= log(size)
                    (because: pigeonhole principle)

(The  size  being the number of elements stored, not a preallocated 
table size. But those two should be proportional anyway.) So, hash 
tables have no asymptotic benefits, it's all in the constant factors.

Regards,
apfelmus