Something Better than ArrayList

Discussion in 'Java' started by Gene Wirchenko, Jun 21, 2011.

  1. 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
    Gene Wirchenko, Jun 21, 2011
    #1
    1. Advertising

  2. 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.



    --

    An exotic journey in downtown Newark is in your future.
    Donkey Hottie, Jun 21, 2011
    #2
    1. Advertising

  3. Donkey Hottie <> wrote:
    > 21.6.2011 8:34, Gene Wirchenko kirjoitti:
    >> 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 think you need a Map<String,String>


    >> I also want to have more than one data item
    >> per entry.


    Map<String,List<DataItem>>

    > 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, Jun 21, 2011
    #3
  4. Gene Wirchenko

    Stefan Ram Guest

    Andreas Leitgeb <> writes:
    >>>I also want to have more than one data item
    >>>per entry.

    >Map<String,List<DataItem>>


    Or, Map<String,Set<DataItem>>.
    Stefan Ram, Jun 21, 2011
    #4
  5. Gene Wirchenko

    Paul Cager Guest

    On Jun 21, 6:34 am, Gene Wirchenko <> wrote:
    > 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
    Paul Cager, Jun 21, 2011
    #5
  6. Stefan Ram <-berlin.de> wrote:
    > Andreas Leitgeb <> writes:
    >>>> I also want to have more than one data item
    >>>> per entry.

    >> Map<String,List<DataItem>>

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


    Ok, you win :)
    Andreas Leitgeb, Jun 21, 2011
    #6
  7. On Mon, 20 Jun 2011 22:34:44 -0700, Gene Wirchenko <>
    wrote:

    >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, Jun 21, 2011
    #7
  8. On Tue, 21 Jun 2011 02:22:46 -0700 (PDT), Paul Cager
    <> wrote:

    >On Jun 21, 6:34 am, Gene Wirchenko <> wrote:
    >> 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


    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
    Gene Wirchenko, Jun 21, 2011
    #8
  9. Gene Wirchenko

    Tom Anderson Guest

    On Tue, 21 Jun 2011, Gene Wirchenko wrote:

    > On Tue, 21 Jun 2011 02:22:46 -0700 (PDT), Paul Cager
    > <> wrote:
    >
    >> On Jun 21, 6:34 am, Gene Wirchenko <> wrote:
    >>> 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

    >
    > 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

    --
    No man ever steps in the same river twice, for it's not the same river
    and he's not the same man. -- Heraclitus
    Tom Anderson, Jun 21, 2011
    #9
  10. Gene Wirchenko

    Tom Anderson Guest

    On Tue, 21 Jun 2011, Andreas Leitgeb wrote:

    > Stefan Ram <-berlin.de> wrote:
    >> Andreas Leitgeb <> writes:
    >>>>> I also want to have more than one data item
    >>>>> per entry.
    >>> Map<String,List<DataItem>>

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

    >
    > Ok, you win :)


    SortedMap<String, Collection<DataItem>>!

    tom

    --
    No man ever steps in the same river twice, for it's not the same river
    and he's not the same man. -- Heraclitus
    Tom Anderson, Jun 21, 2011
    #10
  11. On Tue, 21 Jun 2011 22:56:51 +0100, Tom Anderson
    <> wrote:

    [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
    Gene Wirchenko, Jun 22, 2011
    #11
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Peter Bencsik
    Replies:
    2
    Views:
    822
  2. Replies:
    3
    Views:
    433
  3. SunRaySon
    Replies:
    6
    Views:
    172
    Joel VanderWerf
    Jan 9, 2008
  4. Replies:
    3
    Views:
    147
    Web Surfer
    Apr 19, 2004
  5. Replies:
    17
    Views:
    308
    Arne Vajhøj
    Oct 2, 2013
Loading...

Share This Page