A minimal hash function for C?

c hash hashtable
CDR picture CDR · Apr 13, 2009 · Viewed 49.4k times · Source

I can't use boost:hash because I have to stick with C and can't use C++.

But, I need to hash a large number (10K to 100k) of tokens strings (5 to 40 bytes length) so that search within those are fastest.

MD5, SHA1 or any long hash function seems too heavy for a simple task, I am not doing cryptography. Plus there is the storage and computing cost.

Therefore my question:

  1. What might be the simplest hash algorithm that will ensure collision prevention in most practical cases.

  2. How many bit to use for the hash value? I am developing for 32 bit systems. Does hash algorithm in Perl/Python use 32 bit hashes too? Or do I have to jump to 64?

  3. Regarding implementation of hash tables in common scripting languages: does the implementation check for collisions or can I avoid that part altogether?

Answer

gnud picture gnud · Apr 13, 2009

You can find a good (and fast) hash function, and an interesting read, at http://www.azillionmonkeys.com/qed/hash.html

The only time you should not check for collisions, is if you use a perfect hash -- a good old fashioned lookup table, like gperf.

Related questions

hash function for string

I'm working on hash table in C language and I'm testing hash function for string. The first function I've tried is to add ascii code and use modulo (%100) but i've got poor results with the first test of data: 40 collisions …

Read More
Looking for a good hash table implementation in C

I am primarily interested in string keys. Can someone point me towards a library?

Read More
How to write a hash function in C?

Hash Tables are said to be the fastest/best way of Storing/Retrieving data. My understanding of a hash table, hashing is as follows (Please correct me if I am wrong or Please add If there is anything more): A …

Read More