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

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


>>>>> On Wed, 26 Mar 2008 10:11:32 +0100, Kern Sibbald said:
> 
> 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).

Yes, to get rotate in C you have to use two shifts and combine the results.
However, gcc on x86 can detect patterns like

(x << y) | (x >> (32-y))

for unsigned x and generate the rotate instruction :-)

__Martin

-------------------------------------------------------------------------
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.