Which in-memory data structure can accommodate billions of md5 value?
Maybe you can use a binary trie (critbit tree?) that splits in two on each node instead of 256? Of course you get many more nodes, but they are a LOT smaller.
An example implementation in Java is here: critbit