Re: cdb Fast Lookup

Russ Allbery wrote:
> 
> Gustavo Vieira Gonçalves Coelho Rios <[email protected]> writes:
> 
> > DJB says about cdb:
> 
> > Fast Lookup: A successful lookup in a large database normally takes just
> > two disk accesses. An unsuccessful lookup takes only one.
> 
> > How may one make such a claim?
> > How may DJB have used a perfect hash function? How may one garantee such
> > a feat ?
> 
> It's not particularly difficult to generate a perfect hash function when
> you know the entire key space in advance, which cdb_make does.
> 
> --
> Russ Allbery ([email protected])             <http://www.eyrie.org/~eagle/>

What?

Let's suppose you have 10 bytes long strings to fit in a 4 byte hash
table. A perfect hash function will assure you exactly 2 ^ 80 / 2 ^ 32
registers per slot. This gives you 2 ^48 register per slot. But now
suppose a very bad case: You have about 2^24 key that maps all the same
hash value. This is very bad, isn't it? since cdb uses linear probing,
performance will drop down! Just confirm me that!