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.