Comment on How we store 400M phone numbers with fast lookupparentComments−bilalhusainOP11ySounds promising. Little bit concerned on the computational cost of hashing function. Gotta explore this option!−Veedrac11yI wouldn't be worried about hashing, either, given you effectively want to hash a 34 bit integer to a ⌈log 4e8⌉ = 29 bit integer.An easy way is to take a 32 to 32 bit hash (eg. http://stackoverflow.com/a/12996028/1763356), calculate hash(top 32 bits) ^ hash(bottom 32 bits) and take the bottom 29 bits of that. I wouldn't be surprised if you can do this in less time than an integer division.
Comments
Sounds promising. Little bit concerned on the computational cost of hashing function. Gotta explore this option!
I wouldn't be worried about hashing, either, given you effectively want to hash a 34 bit integer to a ⌈log 4e8⌉ = 29 bit integer.
An easy way is to take a 32 to 32 bit hash (eg. http://stackoverflow.com/a/12996028/1763356), calculate
and take the bottom 29 bits of that. I wouldn't be surprised if you can do this in less time than an integer division.