[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.
http://ad.doubleclick.net/clk;164216239;13503038;w?http://sf.net/marketplace
_______________________________________________
Bacula-devel mailing list
Bacula-devel@xxxxxxxxxxxxxxxxxxxxx
https://lists.sourceforge.net/lists/listinfo/bacula-devel


This mailing list archive is a service of Copilotco.