Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Which hashing function to use?

Reply
Thread Tools

Which hashing function to use?

 
 
user923005
Guest
Posts: n/a
 
      11-19-2007
On Nov 17, 12:09 am, January Weiner <(E-Mail Removed)> wrote:
> user923005 <(E-Mail Removed)> wrote:
> > Your post is more topical in news:comp.programming {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.


The C standard does not contain a hash function. Quite a pity, too.
What hash function you should use will be a function of the
requirements.

The SDBM and Bernstein are good, simple, fast hashes used to operate
on strings when you need something like a join or lookup and a few
rare collisions are OK.
If you need a much lower chance of collision, then a 64 bit hash like
UMAC is probably what is desired.
If you need 0% chance of collisions, then generate a perfect hash
(obviously, this only works if the inputs are distinct).

> What do you think happens when I ask a question like that in
> comp.programming? Some wise guy will set the Followup-To to comp.lang.c
> , that's what would happen.


Well, he would be a wise guy. True, the group news:comp.programming
is not specifically for algorithm discussion, but it's the closest
thing we've got.

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


The practical advice you get here will be of the same quality as
news:comp.lang.c. Indeed, many of the c.l.c regulars read and post in
both places.

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


None of them.

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


Yes. Unfortunately, the answer is not the one you would like to hear.
I guess that this site might be helpful:
http://www.partow.net/programming/hashfunctions/

I guess further that if you state your requirements precisely you will
get better answers.
 
Reply With Quote
 
 
 
 
Paul Hsieh
Guest
Posts: n/a
 
      11-20-2007
On Nov 16, 3:42 pm, January Weiner <(E-Mail Removed)> wrote:
> 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.


There is a google group dedicated to this sort of thing:

http://groups.google.com/group/hash-functions

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Hashing function different values on different OS ? Lawrence Java 16 02-18-2007 09:57 PM
Hashing Function Dave Python 0 11-17-2005 07:45 PM
Hashing function for integer coordinates Owen Jacobson Java 3 05-26-2005 12:29 PM
Hashing function Pat C++ 2 05-18-2004 05:39 PM
Hashing function (possibly OT) Matt Bull C Programming 2 07-07-2003 08:46 PM



Advertisments