Some sort of searchable or two way Map

[Albretch]

Is there such a thing?

I need a Data Structure that would let you insert Strings into it and give you
back an index you could use later on to refer to the inserted String and it should
work the other way around too, given the String it should return to you the index
if the String exists.

In my code trials I have noticed that:

1._ Yes, a LinkedHashMap is really fast if you have the index, but you can not
get an iterator from it and, it is really slow when you effectively loop over it
via:

get(new Integer(Ix))

2._ A LinkedList is faster but still in order to get to an item you must get an
iterator and go over all of them and check them one by one

I am thinkign of using a class containing two Maps in order to solve the problem,
but there might be a more elegant solution to this prob.

 

[Thomas Kellerer]

Albretch wrote on 26.09.2004 00:23:

Is there such a thing?

I need a Data Structure that would let you insert Strings into it and give you
back an index you could use later on to refer to the inserted String and it should
work the other way around too, given the String it should return to you the index
if the String exists.

ArrayList is exactly what you need.

Have a look at the add(Object) and indexOf(Object) methods.

http://java.sun.com/j2se/1.4.2/docs/api/java/util/ArrayList.html

Thomas

 

[Lasse Reichstein Nielsen]

Is there such a thing?

I need a Data Structure that would let you insert Strings into it
and give you back an index you could use later on to refer to the
inserted String and it should work the other way around too, given
the String it should return to you the index if the String exists.

There is no two-way map, but you can easily build one.
Keep both an ArrayList (for quick index->string lookup) and
a HashMap (for quick string->index lookup). Then make sure
that when adding a string, a map entry mapping the string
to its new index is also created.
/L

 

[Mike Schilling]

Albretch wrote on 26.09.2004 00:23:

ArrayList is exactly what you need.

Have a look at the add(Object) and indexOf(Object) methods.

The pronblem is that ArrayList.indexOf(Object) is implemented with a linear
seach. Not a good idea if the list is much bigger than about 20 objects.

 

[Albretch]

ArrayList is exactly what you need.

Have a look at the add(Object) and indexOf(Object) methods.

http://java.sun.com/j2se/1.4.2/docs/api/java/util/ArrayList.html

Thomas

I do know of ArrayList<String>'s (1.5 typesafe version) add(Object)
and indexOf(Object) methods.

Thing is that if you stress test it (say with 12695 Strings (I am
using all the names of the classes in $JAVA_HOME/lib/rt.jar)), you
will be roughly getting a search time of 1 millisecond per string
which is way to slow.

 

[Albretch]

I do know of ArrayList<String>'s (1.5 typesafe version) add(Object)
and indexOf(Object) methods.

Thing is that if you stress test it (say with 12695 Strings (I am
using all the names of the classes in $JAVA_HOME/lib/rt.jar)), you
will be roughly getting a search time of 1 millisecond per string
which is way to slow.

 

[Tarlika Elisabeth Schmitz]

Is there such a thing?

Have you looked at Jakarta Commons Collections?
http://jakarta.apache.org/commons/index.html

--


Regards/Gruß,

Tarlika Elisabeth Schmitz

 

[Tim Jowers]

There is no two-way map, but you can easily build one.
Keep both an ArrayList (for quick index->string lookup) and
a HashMap (for quick string->index lookup). Then make sure
that when adding a string, a map entry mapping the string
to its new index is also created.
/L

Yes, probably you are building a cache. Store the same object in each
and that is some CacheObject that stores the real object plus the
indices into the two data structures. And there you can store the
lifetime, hits, and other statistics for cleaning the cache. Also can
use a stack. Then the object can be moved up to the top of the stack
and then you can just pop off the end of the stack (queue) the old,
unused objects as needed. Fun stuff to code. Just remember all those
darn immutables in Java so you'll have to constrain they cannot be
stored in the cache.

Another idea is to use Java's inherent GC and marking each object for
lazy collection or whatever that is called. So all objects are stored
in your object pool and drain out by the GC.