Hash vs list

Michael Torrie torriem at chem.byu.edu
Fri Apr 21 20:59:50 MDT 2006


On Fri, 2006-04-21 at 20:56 -0600, Michael Torrie wrote:
> A hash's lookup efficiency varies according to how good the hashing
> buckets algorithm is.  The more collisions there are, the worse it gets.
> However worse-case scenario, a lookup in a hash is O(n), the same as the
> plain array.  Best case, though, is O(log n).  Of course under the worst
> circumstances, if the hash requires looking in every bucket, it will
> probably be slower than a plain array, as there is overhead to be taken
> into account.  But usually if you're trying to find just one key by
> name, a hash is always fastest.

Umm, yeah.  so it's been a while. Levi is correct that the hash
algorithm's best runtime is O(1).  As Levi says, the although the hash
scales better, if the overhead is high (greater m constant) then the
actual realized runtime may be slower for hash.  But as you scale up the
dataset size, a hash becomes a much better algorithm than linear
searching.

Michael
  

> 
> Michael
> 
> 
> > 
> > Thoughts?
> > 
> > Thanks,
> > Jeff
> > 
> > [1] No, I'm not a spammer. :)  It's just an example.
> > /*
> > PLUG: http://plug.org, #utah on irc.freenode.net
> > Unsubscribe: http://plug.org/mailman/options/plug
> > Don't fear the penguin.
> > */
> 
> /*
> PLUG: http://plug.org, #utah on irc.freenode.net
> Unsubscribe: http://plug.org/mailman/options/plug
> Don't fear the penguin.
> */
> 



More information about the PLUG mailing list