Re: Hash

From: Hallvard B Furuseth <h.b.furuseth@xxxxxxxxxxx>
Date: Fri, 29 Dec 2006 11:42:27 +0100

Jon Harrop writes:

Douglas Dude wrote:

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

Assuming there are no clashes (different keys with the same hashed value),
that is correct.

But there usually are clashes (aka hash collisions).

Even discounting hash collisions, we could have a quarrel about whether
it should have been O(key length) where the key length is not considered
constant. A typical hash function must traverse the entire key even
when searching an empty table, so the key length affects the lookup time
differently than for e.g. binary search. (I have no idea what the
equivalent formula is for binary search.)

--
Hallvard
.

Follow-Ups:
- Re: Hash
  - From: Jon Harrop

References:
- Hash
  - From: Douglas Dude
- Re: Hash
  - From: Richard Heathfield
- Re: Hash
  - From: Douglas Dude
- Re: Hash
  - From: Jon Harrop

Prev by Date: .indd .cpt .psd .ps .eps .ai file formats help need
Next by Date: Re: platform independent bit shifting
Previous by thread: Re: Hash
Next by thread: Re: Hash
Index(es):
- Date
- Thread

Relevant Pages

Re: How do Lisp Hash Tables handle clashes?
... Clashes are a show-stopper for me - I presume the way to handle this ... are you worrying about values whose hash function clashes? ... cl-user> ... that equipment. ...
(comp.lang.lisp)
Re: [patch 1/3] kmsg: Kernel message catalog macros.
... On Sunday 17 August 2008 06:40:50 Tim Hockin wrote: ... The shorter the hash is, ... You need to catalogue them all anyway, so you can detect clashes at build ... Yes, you have to change the new string in that case, but that's easy. ...
(Linux-Kernel)
Re: How do Lisp Hash Tables handle clashes?
... Clashes are a show-stopper for me - I presume the way to handle this is ... from the original hash table and the list of exceptions every time. ... tables for fast lookup. ... Lisp provided hash tables. ...
(comp.lang.lisp)
Re: How do Lisp Hash Tables handle clashes?
... Lisp provided hash tables. ... How do Lisp Hash Tables handle clashes? ... and that include that no distinct keys should ever clash. ...
(comp.lang.lisp)
Re: OT: Binary Search - Should They Know It?
... Patterns of Enterprise Architecture ... A graduate from a university degree program absolutely should be familiar with basic data structures such as a hash table, or an algorithm like a binary search. ... In the end, what a company needs to do is figure out what they are hiring for, what skills that person needs, and figure out a way to measure those skills in a reliable way. ...
(microsoft.public.dotnet.languages.csharp)