Which hashing function to use?

[January Weiner]

Hello,

I need to use a hashing function for relatively short strings (roughly 16
characters or less). The data that needs to be accessed via hash is just a
simple int. I just need to look up values in two dimensional matrices each
time that I encounter a pair of these strings.

I would like to keep the code as simple and standard as
possible, but at the same time to have a reasonable performance.

While looking through the docs on my system I found a few different
implementations :
- hsearch from <search.h>
- tsearch from <search.h>
- bsearch from <stdlib.h>

Which one would you recommend? Or maybe something completly different?
Right now I just use Perl to do the hashing :-) this is nice, but I would
love to have a small, efficient, ANSI C program.

Regards,

January

[user923005]

On Nov 16, 3:42 pm, January Weiner <january.wei... @gmail.comwrote :

Hello,

I need to use a hashing function for relatively short strings (roughly 16
characters or less). The data that needs to be accessed via hash is just a
simple int. I just need to look up values in two dimensional matrices each
time that I encounter a pair of these strings.

I would like to keep the code as simple and standard as
possible, but at the same time to have a reasonable performance.

While looking through the docs on my system I found a few different
implementations :
- hsearch from <search.h>
- tsearch from <search.h>
- bsearch from <stdlib.h>

Which one would you recommend? Or maybe something completly different?
Right now I just use Perl to do the hashing :-) this is nice, but I would
love to have a small, efficient, ANSI C program.

Your post is more topical in news:comp.progr amming {follow-ups set}.

I do not think that your problem has an answer yet. It will depend on
lots of things.
For instance, are the strings a static set that never changes? If so,
then a perfect hash is your choice.
There are string searching algorithms faster than a hash table (See
Sedgewick).

Do you need to preserve the data (e.g in a key/value pair set on
disk)?

"I need a hash, which should I use?" is such an open question that any
simple answer will probably be lacking.

[January Weiner]

user923005 <dc*****@connx. comwrote:

Your post is more topical in news:comp.progr amming {follow-ups set}.

Well, it is not. Not 100%. The reason being that I am looking for
something that is part of the C standard and that is simple to use in C.
What do you think happens when I ask a question like that in
comp.programmin g? Some wise guy will set the Followup-To to comp.lang.c
:-P, that's what would happen. Finally, the reason is that I am not a
computer scientist and need, hm, very practical advice. Practical advice
is something that I always got plenty on comp.lang.c :-) Note that you will
find a discussion on different hashing algorithms in the FAQ of this group
-- however, I do not fully understand it (otherwise I would not be asking
the questions).

I do not think that your problem has an answer yet. It will depend on
lots of things.
For instance, are the strings a static set that never changes? If so,
then a perfect hash is your choice.
There are string searching algorithms faster than a hash table (See
Sedgewick).

OK, as I am not a computer scientist, I will try to look it up somewhere.
Meanwhile, which of that is a part of standard C libraries?

Do you need to preserve the data (e.g in a key/value pair set on
disk)?

Nope, I would go for DBM or SQL if I needed that.

"I need a hash, which should I use?" is such an open question that any
simple answer will probably be lacking.

"I need a hash, which of the ones in the standard C libraries should I use"
is a more specific question, is it not?

Kind regards,

January

[Keith Thompson]

January Weiner wrote:

user923005 <dc*****@connx. comwrote:

>Your post is more topical in news:comp.progr amming {follow-ups set}.

[...]

>"I need a hash, which should I use?" is such an open question that any
simple answer will probably be lacking.

"I need a hash, which of the ones in the standard C libraries should I use"
is a more specific question, is it not?

Yes, it is. And the answer is, there are no hash functions in the
standard C library.

--
Keith Thompson (The_Other_Keit h) <ks***@mib.or g>
Looking for software development work in the San Diego area.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[Richard Heathfield]

Keith Thompson said:

January Weiner wrote:

>user923005 <dc*****@connx. comwrote:

>>Your post is more topical in news:comp.progr amming {follow-ups set}.

[...]

>>"I need a hash, which should I use?" is such an open question that any
simple answer will probably be lacking.

"I need a hash, which of the ones in the standard C libraries should I
use" is a more specific question, is it not?

Yes, it is. And the answer is, there are no hash functions in the
standard C library.

Cases could be made for some of the math functions, and perhaps rand. Not
particularly good cases, admittedly, but theoretically.. .

--
Richard Heathfield <http://www.cpax.org.uk >
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

[Malcolm McLean]

"January Weiner" <ja************ @gmail.comwrote in message

Hello,

I need to use a hashing function for relatively short strings (roughly 16
characters or less). The data that needs to be accessed via hash is just
a
simple int. I just need to look up values in two dimensional matrices each
time that I encounter a pair of these strings.

I would like to keep the code as simple and standard as
possible, but at the same time to have a reasonable performance.

While looking through the docs on my system I found a few different
implementations :
- hsearch from <search.h>
- tsearch from <search.h>
- bsearch from <stdlib.h>

Which one would you recommend? Or maybe something completly different?
Right now I just use Perl to do the hashing :-) this is nice, but I would
love to have a small, efficient, ANSI C program.

There's a general-purpose hash function on my website - under Basic
Algorithms, sample chapter on hash tables.
Whilst it is not specially designed for strings, it's pretty good. Use it
for now, and replace it only if performance is unacceptable.

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

[CBFalconer]

January Weiner wrote:

>
I need to use a hashing function for relatively short strings
(roughly 16 characters or less). The data that needs to be
accessed via hash is just a simple int. I just need to look up
values in two dimensional matrices each time that I encounter a
pair of these strings.

I would like to keep the code as simple and standard as
possible, but at the same time to have a reasonable performance.

While looking through the docs on my system I found a few
different implementations :
- hsearch from <search.h>
- tsearch from <search.h>
- bsearch from <stdlib.h>

Which one would you recommend? Or maybe something completly
different? Right now I just use Perl to do the hashing :-) this
is nice, but I would love to have a small, efficient, ANSI C
program.

There are a couple of very simple, but efficient, string hashing
routines available (in source form) in hashlib.zip. Although
hashlib is copyright and released under GPL, those functions are
pretty common knowledge and there will be no objections to
including them in anything else. You can find hashlib.zip at:

<http://cbfalconer.home .att.net/download/>

--
Chuck F (cbfalconer at maineline dot net)
<http://cbfalconer.home .att.net>
Try the download section.

--
Posted via a free Usenet account from http://www.teranews.com

[January Weiner]

CBFalconer <cb********@yah oo.comwrote:

There are a couple of very simple, but efficient, string hashing
routines available (in source form) in hashlib.zip. Although
hashlib is copyright and released under GPL, those functions are
pretty common knowledge and there will be no objections to
including them in anything else. You can find hashlib.zip at:

Thank you very much, that is precisely the answer that I needed.

January

[January Weiner]

Malcolm McLean <re*******@btin ternet.comwrote :

There's a general-purpose hash function on my website - under Basic
Algorithms, sample chapter on hash tables.
Whilst it is not specially designed for strings, it's pretty good. Use it
for now, and replace it only if performance is unacceptable.

Thanks!

January

[Peter Nilsson]

Keith Thompson <[e-mail] rote:

January Weiner wrote:

"I need a hash, which of the ones in the standard C
libraries should I use" is a more specific question,
is it not?

Yes, it is. And the answer is, there are no hash functions
in the standard C library.

There are at least two that fit the raw definition: strlen()
and strtoul(..., ..., 36). Not necessarily useful, but forms
of hashing nonetheless.

--
Peter