News for hackers. Stuff that matters.
Re:How we store 400M phone numbers with fast lookup by Veedrac on Wednesday July 29, 2015 @06:39AM (#9967664)
A hash table is more than compact enough. It should work fine even at high load factors (80%/90%) given a decent hash scheme (eg. Robin Hood hashing) which means you need only 4GB memory. It's random access and on average should have one cache miss per lookup. Updating is rather trivial.
Re:How we store 400M phone numbers with fast lookup by bilalhusain on Wednesday July 29, 2015 @12:19PM (#9969663)
Sounds promising. Little bit concerned on the computational cost of hashing function. Gotta explore this option!
Re:How we store 400M phone numbers with fast lookup by Veedrac on Wednesday July 29, 2015 @10:29PM (#9972907)
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

    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.