Saturday, March 8, 2014

TrieMap - A Trie for Java

         Trie is a very simple data structure in concept, however the implementation is a little involved. Suppose you want to have the trie accept entries like
             [ {1,3,4},1 ] ,  [{1}, 3],  [{3,4}, 6] ....
where the values within {} form the keys and the lone value outside it corresponding values then this TrieMap comes in handy for such situations. We can think of behaviors like
1) Adding/updating existing value  
        Ex: {1,3,4}’s value set to supplied value
2) Incrementing prefix partial key’s corresponding values  
        Ex: {3,4},6 will update {3}’s value as well as {3,4}’s value
3) Incrementing prefixes of all suffixes of whole key.
        Ex:{1,3,4} will update {1} {3} {4} {1,3} {3,4} and {1,3,4}’s values respectively .
4) Iterate through all the possible <K,V> combinations.
     Find the open source implementation at github here.  This implementation accepts list of numbers(can be int, byte, double etc).

      A HashMap could have been used as well. The beauty with Trie is say you have a set of keys
  then in a Trie 2  3  and 4 are stored only once because they all belong to same level(if you imagine a Trie as a tree) but a HashMap stores them as many number of times as they appear. There is also a test case within to showcase the usage. Feel free to leave a feedback.

No comments:

Post a Comment