Velocity Reviews > Why in hash function use 5381?

# Why in hash function use 5381?

anguo
Guest
Posts: n/a

 01-03-2004
i find in many hash function use 5381,for exampla:
static constmap_hash hash(char *pchData, int iLen)
{
unsigned char cBuf;
constmap_hash ulHashId;
ulHashId = 5381;
while (iLen > 0)
{
cBuf = *pchData++ - 'A';
if (cBuf <= 'Z' - 'A')
{
cBuf += 'a' - 'A';
}
ulHashId = ((ulHashId << 5) + ulHashId) ^ cBuf;
--iLen;
}
return ulHashId;
}
Can anyone tell me why use 5381 ?
thanks!!

Ben Pfaff
Guest
Posts: n/a

 01-03-2004
http://www.velocityreviews.com/forums/(E-Mail Removed) (anguo) writes:

> i find in many hash function use 5381,for exampla:

[...]

> Can anyone tell me why use 5381 ?

This webpage implies that it is a random number selected by Dan
Bernstein: <http://www.cs.yorku.ca/~oz/hash.html>. Presumably
everyone else just used the same number.
--
int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuv wxyz.\
\n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
);while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p[i]\
);}return 0;}

Martin Ambuhl
Guest
Posts: n/a

 01-03-2004
Ben Pfaff wrote:
> (E-Mail Removed) (anguo) writes:
>>i find in many hash function use 5381,for exampla:

> [...]
>>Can anyone tell me why use 5381 ?

> This webpage implies that it is a random number selected by Dan
> Bernstein: <http://www.cs.yorku.ca/~oz/hash.html>. Presumably
> everyone else just used the same number.

Except that it is not so very random looking: 5381 = 012405. This looks
like something deeper is involved. The 001/010/100/000/101 raises the
question about the choice of the last octal digit, though.

--
Martin Ambuhl

Jean-Michel Collard
Guest
Posts: n/a

 01-03-2004
Ben Pfaff wrote:

>
> --
> int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuv wxyz.\
> \n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
> );while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p[i]\
> );}return 0;}

huh "Just another C hacker"

Ben.c: (in function main)
Ben.c:9:18: Variable i initialized to type arbitrary unsigned integral type,
expects int: sizeof(p) / 2

Ben.c:10:9: Function strchr shadows outer declaration
An outer declaration is shadowed by the local declaration.

Specification of strchr:
[function (char *, int) returns char *]

Ben.c:11:7: Function putchar shadows outer declaration
Specification of putchar:
[function (int) returns int]

Ben.c:12:10: Test expression for while not boolean, type char: *q
Test expression type is not boolean.

Ben.c:14:12: Variable strchr used before definition
An rvalue is used that may not be initialized to a value on some execution
path.
Ben.c:17:7: Variable putchar used before definition

Ben.c:17:7: Return value (type int) ignored: putchar(p[i])
Result returned by function call is not used.

Cheers

Ben Pfaff
Guest
Posts: n/a

 01-03-2004
Jean-Michel Collard <(E-Mail Removed)> writes:

> Ben Pfaff wrote:
>
> > --
> > int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuv wxyz.\
> > \n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
> > );while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p[i]\
> > );}return 0;}

>
> huh "Just another C hacker"
>
> [...many warnings snipped...]

It's perfectly well-defined, if obfuscated, C. It's not meant to
be lint-clean. Based on what I've seen from some versions of
lint, a lot of lint warnings are simply nonsensical, so that's
not even a good goal for real-world code.

Richard Bos
Guest
Posts: n/a

 01-05-2004
Jean-Michel Collard <(E-Mail Removed)> wrote:

> Ben Pfaff wrote:
>
> > int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuv wxyz.\
> > \n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
> > );while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p[i]\
> > );}return 0;}

>
> huh "Just another C hacker"
>
> Ben.c: (in function main)
> Ben.c:9:18: Variable i initialized to type arbitrary unsigned integral type,
> expects int: sizeof(p) / 2

Correct for this constant value, though.

> Ben.c:10:9: Function strchr shadows outer declaration
> An outer declaration is shadowed by the local declaration.

Where, pray, is this "outer declaration" to be found?

> Ben.c:11:7: Function putchar shadows outer declaration

And ditto?

> Ben.c:12:10: Test expression for while not boolean, type char: *q
> Test expression type is not boolean.

Yer_what_?

> Ben.c:14:12: Variable strchr used before definition
> An rvalue is used that may not be initialized to a value on some execution
> path.
> Ben.c:17:7: Variable putchar used before definition

Erm... boggle.

> Ben.c:17:7: Return value (type int) ignored: putchar(p[i])
> Result returned by function call is not used.

Gosh. Lint really _is_ prehistoric, isn't it?

Richard

August Derleth
Guest
Posts: n/a

 01-05-2004
Richard Bos wrote:
> Jean-Michel Collard <(E-Mail Removed)> wrote:
>
>
>>Ben Pfaff wrote:
>>
>>
>>>int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuv wxyz.\
>>> \n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
>>>);while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p[i]\
>>>);}return 0;}

>>
>>huh "Just another C hacker"
>>
>>Ben.c: (in function main)
>>Ben.c:9:18: Variable i initialized to type arbitrary unsigned integral type,
>> expects int: sizeof(p) / 2

>
>
> Correct for this constant value, though.

Eh, lint can't tell that.

>
>
>>Ben.c:10:9: Function strchr shadows outer declaration
>> An outer declaration is shadowed by the local declaration.

>
>
> Where, pray, is this "outer declaration" to be found?

The old-style implicit declaration of everything returning an int?

>>Ben.c:12:10: Test expression for while not boolean, type char: *q
>> Test expression type is not boolean.

>
>
> Yer_what_?

Here's where lint is a bit too pedantic (well, here's a single instance
out of possibly thousands ): C acts like it has a boolean type
sometimes, and it certainly has a boolean context. lint doesn't know,
and can't be made to know, that things other than boolean-returning
relational expressions (such as (a > 5) or (f <= 12)) can meaningfully
be used in a boolean context.

IMNSHO, lint here goes from pedantic to incorrect. Even the earliest
versions of C would gleefully, and conformantly, accept things that
aren't strictly booleans where it imposes a boolean context. For lint to

>
>
>>Ben.c:14:12: Variable strchr used before definition
>> An rvalue is used that may not be initialized to a value on some execution
>> path.
>>Ben.c:17:7: Variable putchar used before definition

>
>
> Erm... boggle.

lint's stupid sometimes.

>
>
>>Ben.c:17:7: Return value (type int) ignored: putchar(p[i])
>> Result returned by function call is not used.

>
>
> Gosh. Lint really _is_ prehistoric, isn't it?

According to K&R2, putchar() does indeed return an int. I suspect a cast
to void would silence lint, but it's hardly worth it, is it?

[OT]
I use splint, a lint-a-like, myself, and splint gives you the warning,
the explanation, and the argument you can pass to splint to make it shut
up about the damned warning. I usually invoke splint with no flags once,
then with a few to weed out the more egregiously inane whinings.
[/OT]

Ben Pfaff
Guest
Posts: n/a

 01-05-2004
August Derleth <(E-Mail Removed)> writes:

> lint's stupid sometimes.

lint is stupid to the point of uselessness. As just one example,
at least one variety of lint emits a warning for the following:
long x = 0;
saying that the initializer is not of the proper type.
--
"I'm not here to convince idiots not to be stupid.
They won't listen anyway."
--Dann Corbit

Arthur J. O'Dwyer
Guest
Posts: n/a

 01-05-2004

On Mon, 5 Jan 2004, August Derleth wrote:
>
> Richard Bos wrote:
> > Jean-Michel Collard <(E-Mail Removed)> wrote:
> >>Ben Pfaff wrote:
> >>
> >>>int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuv wxyz.\
> >>> \n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
> >>>);while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p[i]\
> >>>);}return 0;}
> >>
> >>huh "Just another C hacker"
> >>
> >>Ben.c: (in function main)
> >>Ben.c:9:18: Variable i initialized to type arbitrary unsigned integral type,
> >> expects int: sizeof(p) / 2

> >
> >
> > Correct for this constant value, though.

>
> Eh, lint can't tell that.

It could if it tried hard enough.

> >>Ben.c:10:9: Function strchr shadows outer declaration
> >> An outer declaration is shadowed by the local declaration.

> >
> > Where, pray, is this "outer declaration" to be found?

>
>
> The old-style implicit declaration of everything returning an int?

Ben's .sig #includes no headers, and "implicit declarations" are
implicit for a reason. They're superseded by "real" declarations.
K&R1 even does this in several places, IIRC. So the bottom line is,
this warning is completely bogus. But my guess is that the guy who
ran lint on the .sig did wrongly #include <string.h> -- how else
would lint be down to line 10 in the source already?

> >>Ben.c:12:10: Test expression for while not boolean, type char: *q
> >> Test expression type is not boolean.

> >
> > Yer_what_?

>
> Here's where lint is a bit too pedantic (well, here's a single instance
> out of possibly thousands ): C acts like it has a boolean type
> sometimes, and it certainly has a boolean context. lint doesn't know,
> and can't be made to know, that things other than boolean-returning
> relational expressions (such as (a > 5) or (f <= 12)) can meaningfully
> be used in a boolean context.
>
> IMNSHO, lint here goes from pedantic to incorrect. Even the earliest
> versions of C would gleefully, and conformantly, accept things that
> aren't strictly booleans where it imposes a boolean context. For lint to

It might be helpful in cases like

if (a=b)

The problems are (1) lint uses the word "boolean" like the programmer
is supposed to know what it means, and which "types" are "boolean"
enough for lint -- but C90 doesn't have boolean types -- and (2) lint
should really know about common idioms like 'if (*q)'. It makes a
large bit of sense to warn about 'if (a+b)' or the like, for the sake
of lint-ness, but lint should know better than to complain in this
case.

> >>Ben.c:17:7: Return value (type int) ignored: putchar(p[i])
> >> Result returned by function call is not used.

> >
> > Gosh. Lint really _is_ prehistoric, isn't it?

>
> According to K&R2, putchar() does indeed return an int. I suspect a cast
> to void would silence lint, but it's hardly worth it, is it?

Some old code, and some overly-portable code, does use casts to
void. We even get questions about (void)printf here occasionally.
I can only assume there's some way to switch off this warning in
modern lints; it would get really obnoxious if you tried to lint a
big source file.

> [OT]
> I use splint, a lint-a-like, myself, and splint gives you the warning,
> the explanation, and the argument you can pass to splint to make it shut
> up about the damned warning. I usually invoke splint with no flags once,
> then with a few to weed out the more egregiously inane whinings.

Excellent. I wish gcc would do this too, for its warnings. It
seems like a very nice feature.

> [/OT]

-Arthur

Eric Sosman
Guest
Posts: n/a

 01-05-2004
Ben Pfaff wrote:
>
> August Derleth <(E-Mail Removed)> writes:
>
> > lint's stupid sometimes.

>
> lint is stupid to the point of uselessness. As just one example,
> at least one variety of lint emits a warning for the following:
> long x = 0;
> saying that the initializer is not of the proper type.

I once encountered a *compiler* that complained about

float f = 0.0;

.... because of the potential loss of precision in the
conversion of `double' to `float'. Perhaps the goal of
the compiler vendor was "Get Nothing Right!"

--
(E-Mail Removed)