Shuffling Bits For Uniform Distribution I am writing an hashing algorithm to be used in 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 whole storage space is uniformly used. In my application, if there too many collisions, we would be forced to evict certain data items. The input is a key and output of the mechanism sought is a &quot;better key&quot; that reduces the collision.
I assume that 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 data store.
The approach I am thinking is to have a predefined padding table, from where we take rest of the bits and shuffle whole thing to produce a new key. For Example, for a smaller key value which can be accommodated in a byte, we pad rest of seven bytes (for 8 byte word). In case of 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 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.
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.