Data.HashTable

apfelmus apfelmus at quantentunnel.de
Thu Mar 6 17:48:59 EST 2008


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



More information about the Libraries mailing list