Natterings about history files

Alex Kiernan alexk at
Mon Feb 12 08:58:12 UTC 2001

Fabien Tassin <fta at> writes:

> According to Russ Allbery:
> > 
> > Unfortunately, if I understand how this works correctly, we can't use a
> > perfect hash function even for old history files, since the point of a
> > perfect hash function is that you'll only ever look up keys that you fed
> > to your function generator when you made it.  Since one of the main
> > purposes (and the most common queries) for old history entries is whether
> > one has an article that one *doesn't* have, this doesn't work very well.
> > We'd be looking up a whole bunch of keys that we didn't give to the
> > perfect hash generator, and which therefore would likely collide left and
> > right in unuseful ways.
> Do you have an idea of the rate collision in the current model ?
> I assume it is quite high unfortunatly. In the past, Matt Dillon did
> the exercise for its Diablo history system but I can't put my hand on
> its report.

This one?

Alex Kiernan, Principal Engineer, Development, Thus PLC

More information about the inn-workers mailing list