[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Bacula-devel] Accurate file project hash tables

On Tuesday 25 March 2008 23:56:16 Martin Simmons wrote:
> >>>>> On Tue, 25 Mar 2008 17:55:50 +0100, Kern Sibbald said:
> >
> > As currently implemented this table is a hash table using the hash class
> > that I wrote 3 or 4 years ago for this particular project. It is fast and
> > efficient.
> BTW, the hash function is currently a little broken I think, e.g. these
> strings will all have the same hash index:
> "abcdefghijklm"
> "zzcdefghijklm"
> "zzzzzzzzzzzzzzcdefghijklm"
> The problem is that nothing collects the bits that are lost by the <<
> operator, so you only hash on the last 32/3 chars.  I think you need to
> rotate the bits instead of just shifting.

Yes, I noticed the hashing is not uniform, but I haven't had the time to look 
into why, so thanks for digging into it.  You are surely right.  If I am not 
mistaken there is no rotate bits function in C because as I remember when I 
wrote the original code (a long time ago) I had to use assembly language to 
get the rotate (one instruction).

Check out the new SourceForge.net Marketplace.
It's the best place to buy or sell services for
just about anything Open Source.
Bacula-devel mailing list

This mailing list archive is a service of Copilotco.