Re: Hash function of structs
On May 19, 3:10 pm, CBFalconer <cbfalco...@yah oo.comwrote:
Alexander has keys which are not strings
(terminated by null characters) but defined by lengths.
Chuck's hashlib handles strings, so you will need you to code
your own routines to handle your keys (structs).
As others have mentioned, there are many good hash-table
handling routines available. I do *not* recommend GNU's
hsearch() (or hsearch_r() for reentrance), but will mention
it anyway since it is "standard" (available in some form
in standard GNU and BSD libraries), and very similar to
Chuck's in most ways: GPL license, handles strings, etc.
Like Chuck's hashlib, FSF hsearch() is available
in source code form.
hsearch() has a much *much* simpler interface than
Chuck's hashlib. Chuck's overly complex interface will
just get in the way unless you need it -- and if you do
need a more flexible interface than hsearch_r()'s you're
likely to find Chuck's interface also inadequate.
Hsearch_r() is not appropriate when memory cost is an
issue: it does no "quotientin g" and typically wastes
8 bytes of overhead on every table entry. Again,
however, Chuck's hashlib suffers the same deficiency.
But the main reason I find it impossible to recommend
Chuck's code is that it is infested with gross time
inefficiencies. I'm sure it would get a passing grade
in an undergraduate programming class when the
instructor stipulates that speed is of no concern,
but I find it bizarre that anyone would tout this as a
developed routine for professional use.
As one example of gross time inefficiency, Chuck's code
performs a completely unnecessary division on *every*
reprobe! Of course these gross inefficiencies won't
matter to you if speed isn't critical, but still
certainly make one wonder about the competence and sincerity
of the coding.
The bizarre division (which will be a severe time waster
on some architectures) was pointed out to Chuck several
years ago, along with the trivial source code fix required,
but AFAIK he's never bothered to fix this bug. Again, this
makes one wonder why we should be expected to treat hashlib
as a serious "product".
Without trying to impugn Chuck specifically, I think
many programmers should hone their skills with simple
arithmetic. No special expertise is needed to see and fix
the time-waster in Chuck's hashlib.
On the topic of facility with simple arithmetic, in
<1137404157.948 899.75770@o13g2 000cwo.googlegr oups.com>
two years ago I described a neat multiplication method:
Try to solve this puzzle yourself if you didn't see it then.
Several responders were intrigued by this method,
although it took some follow-on messages to confirm
that the single line above did the trick with no further
testing or shifting.
Amusingly, Chuck Falconer posted *three* follow-ups to this
code, first complaining that it didn't work, then finally
saying he'd need to review algebra to confirm it did work!
Summary: Get your hash routine from someone who understands
simple arithmetic.
James Dow Allen
On May 19, 3:10 pm, CBFalconer <cbfalco...@yah oo.comwrote:
Alexander Mahone wrote:
>
>
Try: <http://cbfalconer.home .att.net/download/hashlib.zip>
>
Written in standard C, and released under GPL.
>
Hello, I'm looking for an hash function to be used for an hash
table that will contain structs of a certain kind. I've looked
into Sourceforge.net , but so far I've found only hash functions
for strings (string->index).
table that will contain structs of a certain kind. I've looked
into Sourceforge.net , but so far I've found only hash functions
for strings (string->index).
Try: <http://cbfalconer.home .att.net/download/hashlib.zip>
>
Written in standard C, and released under GPL.
(terminated by null characters) but defined by lengths.
Chuck's hashlib handles strings, so you will need you to code
your own routines to handle your keys (structs).
As others have mentioned, there are many good hash-table
handling routines available. I do *not* recommend GNU's
hsearch() (or hsearch_r() for reentrance), but will mention
it anyway since it is "standard" (available in some form
in standard GNU and BSD libraries), and very similar to
Chuck's in most ways: GPL license, handles strings, etc.
Like Chuck's hashlib, FSF hsearch() is available
in source code form.
hsearch() has a much *much* simpler interface than
Chuck's hashlib. Chuck's overly complex interface will
just get in the way unless you need it -- and if you do
need a more flexible interface than hsearch_r()'s you're
likely to find Chuck's interface also inadequate.
Hsearch_r() is not appropriate when memory cost is an
issue: it does no "quotientin g" and typically wastes
8 bytes of overhead on every table entry. Again,
however, Chuck's hashlib suffers the same deficiency.
But the main reason I find it impossible to recommend
Chuck's code is that it is infested with gross time
inefficiencies. I'm sure it would get a passing grade
in an undergraduate programming class when the
instructor stipulates that speed is of no concern,
but I find it bizarre that anyone would tout this as a
developed routine for professional use.
As one example of gross time inefficiency, Chuck's code
performs a completely unnecessary division on *every*
reprobe! Of course these gross inefficiencies won't
matter to you if speed isn't critical, but still
certainly make one wonder about the competence and sincerity
of the coding.
The bizarre division (which will be a severe time waster
on some architectures) was pointed out to Chuck several
years ago, along with the trivial source code fix required,
but AFAIK he's never bothered to fix this bug. Again, this
makes one wonder why we should be expected to treat hashlib
as a serious "product".
Without trying to impugn Chuck specifically, I think
many programmers should hone their skills with simple
arithmetic. No special expertise is needed to see and fix
the time-waster in Chuck's hashlib.
On the topic of facility with simple arithmetic, in
<1137404157.948 899.75770@o13g2 000cwo.googlegr oups.com>
two years ago I described a neat multiplication method:
If you've not seen the trick before, consider it a puzzle
to reverse engineer it from the fragment:
c = arr[x+y] - arr[x-y]; /* c = x * y */
It gives competitive performance even on some machines with
blazingly fast multiplies.
to reverse engineer it from the fragment:
c = arr[x+y] - arr[x-y]; /* c = x * y */
It gives competitive performance even on some machines with
blazingly fast multiplies.
Several responders were intrigued by this method,
although it took some follow-on messages to confirm
that the single line above did the trick with no further
testing or shifting.
Amusingly, Chuck Falconer posted *three* follow-ups to this
code, first complaining that it didn't work, then finally
saying he'd need to review algebra to confirm it did work!
Summary: Get your hash routine from someone who understands
simple arithmetic.
James Dow Allen
Comment