Where do I find a standard Trie based map implementation in Java?

views:

2176

answers:

+7 Q:

Where do I find a standard Trie based map implementation in Java?

I have a Java program that stores a lot of mappings from Strings to various objects.

Right now, my options are either to rely on hashing (via HashMap) or on binary searches (via TreeMap). I am wondering if there is an efficient and standard trie-based map implementation in a popular and quality collections library?

I've written my own in the past, but I'd rather go with something standard, if available.

Quick clarification: While my question is general, in the current project I am dealing with a lot of data that is indexed by fully-qualified class name or method signature. Thus, there are many shared prefixes.

Are HashMap and TreeMap that slow?

We maintain some pretty big maps and speed has never seemed to be that much of an issue.

Fortyrunner 2009-03-08 17:05:05

TreeMap and HashMap are interfaces.

Andrew Dashin 2009-03-08 17:09:03

In terms of speed, a hash should be faster than a trie. But I think he's more worried about memory efficiency.

2009-03-08 17:11:31

@Andrew Dashin: They are not interfaces. Their respective interfaces are Map and SortedMap.

Esko Luontola 2009-03-08 17:12:45

They're interfaces but are usually used with an implementation that conforms to their name.

Uri 2009-03-08 17:16:04

Tries are cheaper space wise since they supposedly don't store entire strings (a lot of my strings have common prefixes)

Uri 2009-03-08 17:16:39

@Uri/Andrew Dashin - they're classes

Tom 2009-03-08 17:23:11

Concrete classes. Not abstract, not interfaces:http://java.sun.com/javase/6/docs/api/java/util/TreeMap.htmlhttp://java.sun.com/javase/6/docs/api/java/util/HashMap.html

mtruesdell 2009-03-08 22:33:03

@uri You now have me interested in Tries as well - thanks!@andrew, They're definitely classes and have been since Java 1.2 when I first started using em!

Fortyrunner 2009-03-08 23:29:12

@thaggie: Sorry, my bad, I had an IHashMap and ITreeMap years ago in a C++ project, don't ask. Yes, Map and Tree are the interfaces, but I am using either HashMap or TreeMap and wondering if a Trie wouldn't be better.

Uri 2009-03-09 00:01:50

My main concern with Tries is the cost of accesses. Since each cell may be at a different location in memory.

Uri 2009-03-09 00:02:23

My appologies, I did a mistake.

Andrew Dashin 2009-03-09 13:26:03

TreeMap/HashMaps doesn't solve the same problem as tries. You can do prefix lookups in tries.

nos 2010-02-09 19:36:43

What you need is org.apache.commons.collections.FastTreeMap , I think.

Andrew Dashin 2009-03-08 17:09:19

You might look at this TopCoder one as well (registration required...).

TofuBeer 2009-03-08 17:44:37

+6 A:

You might want to look at the Trie implementation that Limewire is contributing to the Google collections library.

David Schlosnagle 2009-03-08 17:51:51

ansaurus

tags:

views:

answers:

Where do I find a standard Trie based map implementation in Java?

related questions