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

2) Incrementing prefix partial key’s corresponding values

3) Incrementing prefixes of all suffixes of whole key.

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

{2,3,4,5}

{2,3}

{2,3,4}

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.

[ {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 value2) Incrementing prefix partial key’s corresponding values

**Ex**: {3,4},6 will update {3}’s value as well as {3,4}’s value3) 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

{2,3,4,5}

{2,3}

{2,3,4}

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