Hash vs list
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
> > Thoughts?
> > Thanks,
> > Jeff
> >  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