From: "Brian Schröder" <ruby.brian@...>
Date: 2005-04-28T22:33:07+09:00
Subject: Re: Hash as Checklist

On 28/04/05, Dr Balwinder S Dheeman <bsd.SANSPAM@cto.homelinux.net> wrote:
> On 04/28/2005 07:48 AM, basi wrote:
> > Hello,
> > I need to check if a word is in a list. I'm using hash because the
> > lists can be long (i'm under the impression hash is faster than array).
> 
> A hash have to store "key" => value pairs, how will be more efficient
> than an array? and why?
> 

because Array lookups are O(n) and Hash lookups should be O(1). To
find something in an Array you have to traverse it completely and will
find the entry you are searching in expected n/2 steps. For hashes
there exist different implementations, but basically you compute the
possible position of an object from the object and just take a look if
it is there. (Oversimplified).

best regards,

Brian

> [snip]

-- 
http://ruby.brian-schroeder.de/

multilingual _non rails_ ruby based vocabulary trainer:
http://www.vocabulaire.org/ | http://www.gloser.org/ | http://www.vokabeln.net/