Awesome

Trie

Trie tree implementation in Java

Setup

Add the module to your project:

<dependency>
  <groupId>io.jmnarloch</groupId>
  <artifactId>trie</artifactId>
  <version>1.0.0-SNAPSHOT</version>
</dependency>

Features

Trie

The Trie is a R way tree that is designed for efficient string searches.

At this moment this component defines four different implementation of the Trie, all of which differs slightly in performance, but far most with the memory consumption.

The available Trie implementations are:

• ArrayTrie
• HashMapTrie
• TroveCharHashMapTrie - that uses Trove TCharObjectHashMap
• KolobokeCharHashMapTrie - that uses Koloboke HashCharObjMap

Ternary Trie Tree

In effort to minimize the memory consumption we can design our tree as a 3-way tree with node links corresponding to character being lower, equal or greater then character within given node.

The available implementation:

• Tst
• ImmutableTst

Benchmark

Project includes simple JMH benchmark that measures the throughput of selected operations on the data structures. For the sake of the benchmark every Trie instance has been populated with 1024 unique entries. The benchmark measures the throughput of retrieving a key value and inserting a new one.

• Benchmark run on Intel Core i7 2.2 GHz (4770HQ)

Memory footprint

Tested on 64 bit JVM with enabled pointer compression (-XX:+UseCompressedOops - which is enabled by default for Java 8) Measured using JAMM. The memory size includes the object overhead and padding.

Size of single tree node

• HashMapTrie - the size appears to be size of empty HashMap, but it expands when new entries are being added.

After populating the Trie trees with 1024 random 36 character length strings we may expect fallowing results:

TODO

• Compressed trie - Patricia trie

License

Apache 2.0