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. > */ > /* PLUG: http://plug.org, #utah on irc.freenode.net Unsubscribe: http://plug.org/mailman/options/plug Don't fear the penguin. */
