Re: Hash

Douglas Dude said:


Richard Heathfield wrote:
Douglas Dude said:

How much time does it take to look for a value or key in a hash_map
keyvalue pair ?

About 10 minutes. 30 microseconds. A few months. It kind of depends,
really.

Please help me confirm the O-notation. I always think it is O(1), is
this correct?

Ah! Time *complexity*. Well, that depends on the implementation of the
algorithm, of course, but it's possible, given a key, to locate its
associated value in O(1) if you have a perfect hash. And if you don't, the
complexity depends on your mechanism for resolving collisions.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.
.

Relevant Pages

  • Re: Hash
    ... 30 microseconds. ... Richard Heathfield ... rjh at the above domain, ...
    (comp.programming)
  • Re: [OT] Re: Help with a C program
    ... >> Skarmander said: ... but then you started comparing program complexity to the ... Only the bits the doctor pokes and prods. ... Richard Heathfield ...
    (comp.lang.c)
  • Re: Hash
    ... Richard Heathfield wrote: ... 30 microseconds. ... rjh at the above domain, ...
    (comp.programming)
  • Re: As programmers...have we come a long way since 1993?
    ... Richard Heathfield wrote: ... Rapid growth of complexity often has the effect. ... I suspect ...
    (comp.programming)
  • Re: reading systemtime in microseconds
    ... Richard Heathfield wrote: ... > r norman wrote: ... >>You will not get time in microseconds that way. ... Your operating system ...
    (alt.comp.lang.learn.c-cpp)