For these problematics there are hashtables with progressive resize. For the theory you can see: http://en.wikipedia.org/wiki/Linear_hashing http://en.wikipedi

For these problematics there are hashtables with progressive resize. For the theory you can see: http://en.wikipedia.org/wiki/Linear_hashing http://en.wikipedia.org/wiki/Linear_hashing I did one in C at: http://tommyds.sourceforge.net/ http://tommyds.sourceforge.net/ It's competitive with the googledensehash, sometimes slower, sometimes faster. In the benchmark section there are nice graphs :)