Re: cdb Fast Lookup

Steve Dekorte <[email protected]> writes:
> On Friday, August 23, 2002, at 04:17  PM, Russ Allbery wrote:

>> It's not particularly difficult to generate a perfect hash function
>> when you know the entire key space in advance, which cdb_make does.

> A *perfect* one? Even when the number of keys is large compared to the
> hash space?

How many keys are in the typical cdb database?  Do you really think that
number is large compared to the numbers represented by a 32-bit integer,
for instance?

A Google search for perfect hash functions turns up lots of details.

I'm not saying that Dan is using perfect hash functions; I don't believe
that he is, from past discussion, but I don't remember the exact details.
A perfect hash function makes no guarantees about what happens when you
look for something that's not inside its space, like a key that isn't in
the database, and Dan still makes guarantees for those lookups, so I'm
guessing he's doing something else.

I'm just pointing out why the problem isn't nearly as hard as it sounds.
cdb has a huge advantage over other, more typical hashing problems and
database formats in that the function that generates the database knows
every key that will ever be stored in the database.

The real answer to the original question is "read the source code."

-- 
Russ Allbery ([email protected])             <http://www.eyrie.org/~eagle/>