I am writing a hashing algorithm to be used in the key-value data store. That is for each key the location of the data is determined. The structure of the data store is given a key, a value needs to be retrieved OR given a key and value we determine a location to store the value. We want the keys to be designed/modified such that the whole storage space is uniformly used. In my application, if they're too many collisions, we would be forced to evict certain data items. The input is a key and the output of the mechanism sought is a "better key" that reduces the collision.

I assume that the key would not have more than 64 bits. For uniform distribution in the data store, I want key bits to be shuffled appropriately so that all the data do not collide in the same slot of the data store.

The approach I am thinking of is to have a predefined padding table, from where we take the rest of the bits and shuffle the whole thing to produce a new key. For Example, for a smaller key value that can be accommodated in a byte, we pad the rest of seven bytes (for 8-byte word). In the case of a 2-byte long key, we have another pad of 6 bytes and so on. I am not sure if this is an efficient way to do the job, but exploring should worth it.

If this is a good way, want to understand from you, how can I create such a table? What bits should be filled in it etc? Will be glad if there any pointers.

The idea of padding bits is to create a uniform distribution. For Example, if the key is a very small number 0xab (say) then the padding bits could be 0x12345cdeadbeef00 such that we could OR the two things to form 0x12345cdeadbeefab. Now we shuffle the whole thing such that the resultant key is uniformly distributed in the storage space.

  • $\begingroup$ Maybe try to implement known hash functions, like the SHA hash function, or even better - use the builtin hash function your coding language has. $\endgroup$ – nir shahar Apr 28 at 6:15
  • 2
    $\begingroup$ I don't understand you're looking for. What is the input, what is the output, and what are the required properties? $\endgroup$ – Yuval Filmus Apr 28 at 6:22
  • 1
    $\begingroup$ I don't understand what a predefined padding table is, or how you are imagining your hash function would work, or what is meant by "produce a new key". I think you'll need to explain the problem statement and your idea for an approach more clearly, if you want others to help you. I don't understand why you are constructing some special homebrew hash function rather than using a standard one. $\endgroup$ – D.W. Apr 28 at 8:44
  • $\begingroup$ @D.W. Added some clarifications $\endgroup$ – ultimate cause Apr 30 at 0:11
  • $\begingroup$ I'm confused. Normally in a hashtable, we hash the key and use that to determine where to store the (key,value) pair. Normally when we're implementing a hashtable we don't get to choose the key value -- we have to deal with whatever key values we're given. Are you saying you can change the key value? i.e., the key-value store can return a response to the client saying "sorry, I didn't like that key, I assigned you a new one, here it is"? That's sufficiently unusual and unlikely that I want to confirm it. If so, why doesn't the key-value store always pick a new key (e.g., a counter)? $\endgroup$ – D.W. Apr 30 at 3:36

It sounds like you might be trying to re-invent double-hashing. I recommend reading up on standard strategies for hash tables, including open addressing, closed addressing, cuckoo hashing, 2-choice hashing, and so on.


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.