1
$\begingroup$

For my application, I have to store billions of md5 values, and before storing new md5 I wanna make sure that it doesn't exist already in it. I tried using hash data structure, it worked well but no of lookups goes high with table entries. I tried using trie, each node storing a byte, but the memory consumption is too high. As each node required 256 pointer for successor on next level. Can anyone suggest better data structure which could use less space as well as no of lookups is The ?

$\endgroup$
  • 4
    $\begingroup$ Please edit your question to provide more details. If you're using the hash table correctly, the number of lookups should be $O(1)$, i.e., a small constant. Note that there's a lower bound on the amount of space that will be needed: it's roughly $128n$ bits, where $n$ is the number of MD5 hashes you want to store. $\endgroup$ – D.W. Feb 9 '16 at 0:38
  • 2
    $\begingroup$ Possible partial duplicate: cs.stackexchange.com/questions/20070/… $\endgroup$ – Pseudonym Feb 10 '16 at 11:29
  • $\begingroup$ Tries are notorious for having very compact representations; iirc they approach the information-theoretic minimum. Your problem is that your data set is sparse; a few millions are nothing compared to $256^{32}$ possible hashes. So you probably don't want to store full nodes resp. edge sets for every node. Have you tried using BSTs for representing trie nodes? What about BSTs for the overall problem? There are many other options you could have tried. $\endgroup$ – Raphael Feb 10 '16 at 13:00
1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Given that the data set is sparse, you want to contract unary nodes when doing this. $\endgroup$ – Raphael Feb 10 '16 at 13:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.