Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site watdaisy.UUCP
Path: utzoo!watmath!watdaisy!gvcormack
From: gvcormack@watdaisy.UUCP (Gordon V. Cormack)
Newsgroups: net.lang,net.lang.pascal
Subject: Re: Pointers and hashing
Message-ID: <6913@watdaisy.UUCP>
Date: Mon, 4-Feb-85 11:45:30 EST
Article-I.D.: watdaisy.6913
Posted: Mon Feb  4 11:45:30 1985
Date-Received: Tue, 5-Feb-85 04:36:09 EST
References: <400@decwrl.UUCP>
Organization: U of Waterloo, Ontario
Lines: 25
Xref: watmath net.lang:1367 net.lang.pascal:223

> 
>     Hashing IS NOT an O(1) operation!
> 
>     Hashing is an O(N)/buckets operation, where many times you can use enough
> buckets to make it very fast.
> 
> -- 
> - Joel McCormack {ihnp4 decvax ucbvax allegra sequent utcsrgv}!decwrl!joel
> 		 joel@decwrl.arpa

Thus, if we use O(N) buckets, we have O(1) (average case) retrieval
time.  If O(1) worst-case retrieval time is required, a perfect hash
scheme is necessary.  I have written about one such scheme in
Computer Journal 28:1 (Feb. 85).

Complexity considerations aside, there are almost no circumstances 
where binary search is superior to hashing for unique-key unordered
retrievals.

It seems there should be a better newsgroup in which to continue 
discussions such as this, but I can't think of one.
-- 
 
Gordon V. Cormack      CS Department, University of Waterloo
   gvcormack@watdaisy.uucp     gvcormack%watdaisy@waterloo.csnet