I was sent here from cstheory.stackexchange.com's FAQ, please tell me if this too is the wrong board (this board's FAQ indicates that I have to goto stackoverflow ??)
This is my first question on this board and i am not an algo-person, please feel free to point out any flaws in the question.

MY_MAXIMUM: Variable used to indicate the maximum number of rows in a hash table (AKA unique keys in the table).
MAX_COLLISION: Maximum number of collision admissible for a key.

Type of hashing scheme used: Open hashing ( Each row contains a (key,value) pair, the value element here is a pointer to a list used to hold a maximum of, MAX_COLLISION elements).
Overflow: when trying to insert into a key already containing MAX_COLLISION number of elements, the new prospective element is quietly dropped, instead of applying another hash algorithm or employing a rehashing algorithm. Hence there is a dear need for uniformity in insertion.

Function HASH gets an input value, that is hashed using CRC32 and stored in a hash table. I want to reduce this table to have atmost MY_MAXIMUM number of rows with uniform distribution (The number of unique keys should be atmost MY_MAXIMUM).

A simple idea i had:

Function Hash() { key=crc32(input); key=key%MY_MAXIMUM; // use key .. }

This is not necessarily result in uniform load on the resulting table. Also please note that the primary goal is not in limiting key values to be between (0,MY_MAXIMUM), but in limiting the number of unique keys in the table.

So i seek your advice for an appropriate substitute for key=key%MY_MAXIMUM operation.


It's true that your question would probably be on-topic for SO, but let's see if we can manage it here anyway. (Cstheory.SE wants to be research-level only -- we try to pick up the slack here for student and practical level stuff, but if you like source code more than you like Greek letters, it is possible that you'd feel more at home on SO).

Onwards to the question. You don't really have enough information for a nice authoritative-sounding answer. If you assume that your input data consists of random independent bits, then taking modulus is certainly as good as anything else you can do, but if it isn't, then a meaningful analysis would have to start with some information about how it isn't random.

One general observation that can be made, however, is that CRC32 was designed for something quite different from hashing, namely detection of short-burst transmission errors, and it was also designed to be cheap to implement in hardware. These two goals do not necessarily add up to good collision avoidance properties for practical data. CRC does seem to perform acceptably in practice for collisions, though, but it is not terribly efficient to compute -- the design choices that makes it easy to implement in hardware do not transfer to a software implementation.

I usually recommend using one of the hash functions presented by Bob Jenkins at burtleburtle.net -- not because they have shining academic credentials, but because Jenkins is trying so systematically to do the Right thing that it seems unlikely that he's inadvertently doing something catastrophically wrong.

If you choose to keep CRC32 as the first step, you could post-scramble it by running the final CRC through one of Jenkins' integer hashes. Afterwards, taking a modulus ought to as safe as you can be in that situation. But it's unlikely to really matter in practice, except if your table size is a power of 2. In that case I would do a postscrambling step in order to get at least some nonlinearity into the hash index.

  • $\begingroup$ Thanks a lot for a wonderful answer :) .. a vote up requires 15 reputation .. else you would have gotten one from me. $\endgroup$ – Hex Sep 28 '11 at 18:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.