apfelmus apfelmus at
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

     * 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.


More information about the Libraries mailing list