Something Better than ArrayList

[Gene Wirchenko]

Dear Java'ers:

I have been using ArrayList to serve as an expandable array. I
have not cared about the searching efficency since the arrays have
been small.

Now, I need symbol table processing. There will be a lot of
lookups. What class is like ArrayList in being an expandable array
but that has an order? I also want to have more than one data item
per entry. I am looking at
symbol name (which is what the array is to be sorted by)
symbol value
and possibly something else by the time I think on this further.
Symbol name and symbol value will be of type String though I would
like a general answer.

The name of the class is what I need. I assume I can find the
docs once I know what it is called.

Sincerely,

Gene Wirchenko

 

[Donkey Hottie]

21.6.2011 8:34, Gene Wirchenko kirjoitti:

Dear Java'ers:

I have been using ArrayList to serve as an expandable array. I
have not cared about the searching efficency since the arrays have
been small.

Now, I need symbol table processing. There will be a lot of
lookups. What class is like ArrayList in being an expandable array
but that has an order? I also want to have more than one data item
per entry. I am looking at
symbol name (which is what the array is to be sorted by)
symbol value
and possibly something else by the time I think on this further.
Symbol name and symbol value will be of type String though I would
like a general answer.

The name of the class is what I need. I assume I can find the
docs once I know what it is called.

Sincerely,

Gene Wirchenko

I think you need a Map<String,String>

That is the interface, the implementation could be
HashMap<String,String> or TreeMap<String,String>

HashMap does not keep ordering, but TreeMap does. Both offer the lookup
with symbol name though, and that is what you need, I think.

 

[Andreas Leitgeb]

21.6.2011 8:34, Gene Wirchenko kirjoitti:

 

[Stefan Ram]

Map<String,List<DataItem>>

Or, Map<String,Set<DataItem>>.

 

[Paul Cager]

Dear Java'ers:
     The name of the class is what I need.  I assume I can find the
docs once I know what it is called.

Others have already pointed you to java.util.Map, which answers your
immediate question. You might also want to have a look at the Java
"Collections" tutorial for more general information:
http://download.oracle.com/javase/tutorial/collections/index.html

 

[Andreas Leitgeb]

Or, Map<String,Set<DataItem>>.

Ok, you win

 

[Gene Wirchenko]

Dear Java'ers:

Terminology can be a bear. TLA poisoning and all that, but it is
even worse when one does not know the term.

Thank you for your replies. I will be hitting the docs and
tutorials a bit later today.

[snip]

Sincerely,

Gene Wirchenko

 

[Gene Wirchenko]

Others have already pointed you to java.util.Map, which answers your
immediate question. You might also want to have a look at the Java
"Collections" tutorial for more general information:
http://download.oracle.com/javase/tutorial/collections/index.html

I found it rather dry, but did manage to write a proof-of-concept
program for a symbol table. However, I have to check for duplication
before put()ing. Is there a way to combine a Map and a Set to avoid
this?

For the Map

static Map<String,String> SymbolTable=new HashMap<String,String>();

I would like to write something like

static boolean TryToAdd
(
String theKey,
String theData
)
{
return SymbolTable.put(theKey,theData);
}

instead of

static boolean TryToAdd
(
String theKey,
String theData
)
{
if (SymbolTable.containsKey(theKey))
return false;
else
{
SymbolTable.put(theKey,theData);
return true;
}
}

Am I missing something or is this not supported?

Sincerely,

Gene Wirchenko

 

[Tom Anderson]

I found it rather dry, but did manage to write a proof-of-concept
program for a symbol table. However, I have to check for duplication
before put()ing. Is there a way to combine a Map and a Set to avoid
this?

For the Map

static Map<String,String> SymbolTable=new HashMap<String,String>();

I would like to write something like

static boolean TryToAdd
(
String theKey,
String theData
)
{
return SymbolTable.put(theKey,theData);
}

instead of

static boolean TryToAdd
(
String theKey,
String theData
)
{
if (SymbolTable.containsKey(theKey))
return false;
else
{
SymbolTable.put(theKey,theData);
return true;
}
}

Am I missing something or is this not supported?

You can't do it with a normal Map. You can do it with a ConcurrentMap:

http://download.oracle.com/javase/6/docs/api/java/util/concurrent/ConcurrentMap.html

ConcurrentMap has it because you can't easily build an efficient
threadsafe implementation of putIfAbsent on top of the normal Map
interface. It's a bit of a shame Map doesn't have it, because it's useful
even if you're not dealing with multiple threads!

tom

 

[Tom Anderson]

Ok, you win

SortedMap<String, Collection<DataItem>>!

tom

 

[Gene Wirchenko]

On Tue, 21 Jun 2011 22:56:51 +0100, Tom Anderson

[snip]

You can't do it with a normal Map. You can do it with a ConcurrentMap:

http://download.oracle.com/javase/6/docs/api/java/util/concurrent/ConcurrentMap.html

ConcurrentMap has it because you can't easily build an efficient
threadsafe implementation of putIfAbsent on top of the normal Map
interface. It's a bit of a shame Map doesn't have it, because it's useful
even if you're not dealing with multiple threads!

Thank you for that bit. I did not know if I was reading right or
missing something.

Sincerely,

Gene Wirchenko