impl a collection

Discussion in 'Java' started by vicky, Jun 19, 2004.

  1. vicky

    vicky Guest

    I want to know if there is any efficient way to implement something
    ;like a hashmap which has the entries in the form
    (key,valu1,value2).The structure should also work for getting the key
    using any one of the values.

    any thought on this?? is there any java libraries which implements
    this??

    -vick
    vicky, Jun 19, 2004
    #1
    1. Advertising

  2. vicky wrote:

    > I want to know if there is any efficient way to implement something
    > ;like a hashmap which has the entries in the form
    > (key,valu1,value2).The structure should also work for getting the key
    > using any one of the values.
    >
    > any thought on this?? is there any java libraries which implements
    > this??


    HashMap implements this. Use three instances, one with your key as key
    and an array with the two values as elements as value, and two with
    the respective values as key and the key as value.
    Michael Borgwardt, Jun 19, 2004
    #2
    1. Advertising

  3. vicky

    vicky Guest

    Using three instances would be very expensive in terms of storage.
    jakarta doubleorderedmap might be a good solution if the values are
    used in an array.

    vick.

    Michael Borgwardt <> wrote in message news:<>...
    > vicky wrote:
    >
    > > I want to know if there is any efficient way to implement something
    > > ;like a hashmap which has the entries in the form
    > > (key,valu1,value2).The structure should also work for getting the key
    > > using any one of the values.
    > >
    > > any thought on this?? is there any java libraries which implements
    > > this??

    >
    > HashMap implements this. Use three instances, one with your key as key
    > and an array with the two values as elements as value, and two with
    > the respective values as key and the key as value.
    vicky, Jun 19, 2004
    #3
  4. vicky wrote:

    > Using three instances would be very expensive in terms of storage.


    Is the number of items really that large or your RAM so small?
    Programming ain't magic. If you want to efficiently search for
    three fields, you need three indexes, no way around it.

    > jakarta doubleorderedmap might be a good solution if the values are
    > used in an array.


    You couldn't look for one value then, only a pair. Besides, the
    API documentation for that class is misleading in regard to its space
    saving. I found the claims (and the concept) intriguing and had a
    look at the code. The only space it saves is the object overhead of
    the node objects and the second copy of the key and value references,
    and some of that is squandered on a pointless caching of hash values.
    With an object overhead of 8 bytes that's less than 20% space saved
    compared to two TreeSet instances with the same data.
    Michael Borgwardt, Jun 19, 2004
    #4
  5. vicky

    Job Numbers Guest

    "vicky" <> wrote in message
    news:...
    >I want to know if there is any efficient way to implement something
    > ;like a hashmap which has the entries in the form
    > (key,valu1,value2).The structure should also work for getting the key
    > using any one of the values.
    >
    > any thought on this?? is there any java libraries which implements
    > this??
    >
    > -vick


    This might sound like a stupid question, but why are you doing something a
    database could do for you?
    Job Numbers, Jun 20, 2004
    #5
  6. In article <>,
    (vicky) wrote:

    > I want to know if there is any efficient way to implement something
    > ;like a hashmap which has the entries in the form
    > (key,valu1,value2).The structure should also work for getting the key
    > using any one of the values.
    >
    > any thought on this?? is there any java libraries which implements
    > this??
    >
    > -vick


    Use three maps, each with a different object as the key, and all three
    sharing the same result Object.

    class FooElement
    {
    final Object key;
    final Object value1;
    final Object value2;
    public FooElement (Object key, Object value1, Object value2)
    {
    this.key= key;
    this.value1= value1;
    this.value2= value2;
    }
    }

    final HashMap m_keyMap= new HashMap ();
    final HashMap m_value1Map= new HashMap ();
    final HashMap m_value2Map= new HashMap ();

    void put (Object key, Object value1, Object value2)
    {
    FooElement f= new FooElement(key, value1, value2);
    m_keyMap(key, f);
    m_value1Map(value1, f);
    m_value2Map(value2, f);
    }

    Object getKeyByValue1 (Object value1)
    {
    FooElement f= (FooElement)m_value1Map.get (value1);
    return (f == null) ? null : f.key;
    }

    // etc...

    This is a somewhat tedious example so adjust it to suit your needs.
    You'll also need to figure out what happens when the mappings aren't
    1:1. If your mapping needs to be large, complex, rule-based, shared, or
    have persistence, a database is exactly what you'll want. The code gets
    to be a mess beyond simple cases like I've shown above.
    Kevin McMurtrie, Jun 20, 2004
    #6
  7. vicky

    Roedy Green Guest

    On 19 Jun 2004 06:41:45 -0700, (vicky) wrote or
    quoted :

    >I want to know if there is any efficient way to implement something
    >;like a hashmap which has the entries in the form
    >(key,valu1,value2).The structure should also work for getting the key
    >using any one of the values.


    You create a Glue object which contains references (possibly to the
    key) and the two data values. Then you do a lookup by key to the Glue
    object.


    A simple Glue object could be new Object[] pair = { value1 , value2 };

    adjust as necessary if value1 and value2 are primitives.

    --
    Canadian Mind Products, Roedy Green.
    Coaching, problem solving, economical contract programming.
    See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.
    Roedy Green, Jun 20, 2004
    #7
  8. vicky

    Job Numbers Guest

    "Kevin McMurtrie" <> wrote in message
    news:...
    > In article <>,
    > (vicky) wrote:
    >
    >> I want to know if there is any efficient way to implement something
    >> ;like a hashmap which has the entries in the form
    >> (key,valu1,value2).The structure should also work for getting the key
    >> using any one of the values.
    >>
    >> any thought on this?? is there any java libraries which implements
    >> this??
    >>
    >> -vick

    >
    > Use three maps, each with a different object as the key, and all three
    > sharing the same result Object.
    >
    > class FooElement
    > {
    > final Object key;
    > final Object value1;
    > final Object value2;
    > public FooElement (Object key, Object value1, Object value2)
    > {
    > this.key= key;
    > this.value1= value1;
    > this.value2= value2;
    > }
    > }
    >
    > final HashMap m_keyMap= new HashMap ();
    > final HashMap m_value1Map= new HashMap ();
    > final HashMap m_value2Map= new HashMap ();
    >
    > void put (Object key, Object value1, Object value2)
    > {
    > FooElement f= new FooElement(key, value1, value2);
    > m_keyMap(key, f);
    > m_value1Map(value1, f);
    > m_value2Map(value2, f);
    > }
    >
    > Object getKeyByValue1 (Object value1)
    > {
    > FooElement f= (FooElement)m_value1Map.get (value1);
    > return (f == null) ? null : f.key;
    > }
    >
    > // etc...
    >
    > This is a somewhat tedious example so adjust it to suit your needs.
    > You'll also need to figure out what happens when the mappings aren't
    > 1:1. If your mapping needs to be large, complex, rule-based, shared, or
    > have persistence, a database is exactly what you'll want. The code gets
    > to be a mess beyond simple cases like I've shown above.


    Exactly
    Job Numbers, Jun 20, 2004
    #8
  9. vicky

    NOBODY Guest

    "Job Numbers" <> wrote in
    news:WE5Bc.11023$:

    > "vicky" <> wrote in message
    > news:...
    >>I want to know if there is any efficient way to implement something
    >> ;like a hashmap which has the entries in the form
    >> (key,valu1,value2).The structure should also work for getting the key
    >> using any one of the values.
    >>
    >> any thought on this?? is there any java libraries which implements
    >> this??
    >>
    >> -vick

    >
    > This might sound like a stupid question, but why are you doing
    > something a database could do for you?



    You are truly misleading people. Using a DB for that case is really
    overkill, and WILL kill your performance.
    NOBODY, Jun 22, 2004
    #9
  10. vicky

    NOBODY Guest

    An array costs ~14 +/- 2 bytes , plus the 2 object ref you intent to put
    in. that is 24 bytes. Writing an object with 2 fields will cost you 8 bytes
    for the object and 2x4 bytes for the refs, 16 bytes total, and you get
    compile time safety.

    concl.: don't use arrays.




    (vicky) wrote in news:f7f2f1e5.0406191055.4eec4ea5
    @posting.google.com:

    > Using three instances would be very expensive in terms of storage.
    > jakarta doubleorderedmap might be a good solution if the values are
    > used in an array.
    >
    > vick.
    >
    > Michael Borgwardt <> wrote in message news:

    <>...
    >> vicky wrote:
    >>
    >> > I want to know if there is any efficient way to implement something
    >> > ;like a hashmap which has the entries in the form
    >> > (key,valu1,value2).The structure should also work for getting the key
    >> > using any one of the values.
    >> >
    >> > any thought on this?? is there any java libraries which implements
    >> > this??

    >>
    >> HashMap implements this. Use three instances, one with your key as key
    >> and an array with the two values as elements as value, and two with
    >> the respective values as key and the key as value.
    NOBODY, Jun 22, 2004
    #10
  11. vicky

    NOBODY Guest

    Re: impl a collection (watch out for big strings)

    FYI, start by mutating your strings... let me explain.

    If you use strings from a substring operation, you must know that the
    new string is just refering to the same char[] but with different
    offset/count. That is, if you read a 1k ascii line from a file, then
    substring only the first word (let's say from stringtokenizer) then
    discard the 1k ascii line, YOU ARE STILL HOLDING the 1000 char string
    that takes about 2040 bytes.

    If you can't afford this space and agree to get a small perf hit, you
    can mutate the string with new String(line.getChars()) in which case the
    class is forced to system.arraycopy() the subsection of char[] for you
    to protect the immutable string.




    (vicky) wrote in
    news::

    > Using three instances would be very expensive in terms of storage.
    > jakarta doubleorderedmap might be a good solution if the values are
    > used in an array.
    >
    > vick.
    >
    > Michael Borgwardt <> wrote in message
    > news:<>...
    >> vicky wrote:
    >>
    >> > I want to know if there is any efficient way to implement something
    >> > ;like a hashmap which has the entries in the form
    >> > (key,valu1,value2).The structure should also work for getting the
    >> > key using any one of the values.
    >> >
    >> > any thought on this?? is there any java libraries which implements
    >> > this??

    >>
    >> HashMap implements this. Use three instances, one with your key as
    >> key and an array with the two values as elements as value, and two
    >> with the respective values as key and the key as value.
    NOBODY, Jun 22, 2004
    #11
  12. vicky

    NOBODY Guest

    Re: impl a collection (watch out for big strings)

    >can mutate the string with new String(line.getChars()) in which case the

    Sorry, I meant new String(substring_of_line.getChars())
    NOBODY, Jun 22, 2004
    #12
  13. vicky

    Tony Morris Guest

    Re: impl a collection (watch out for big strings)

    "NOBODY" <antispam@0.0.0.0> wrote in message
    news:Xns950FD8DC0F964nobodyantispam@207.35.177.134...
    > FYI, start by mutating your strings... let me explain.
    >
    > If you use strings from a substring operation, you must know that the
    > new string is just refering to the same char[] but with different
    > offset/count. That is, if you read a 1k ascii line from a file, then
    > substring only the first word (let's say from stringtokenizer) then
    > discard the 1k ascii line, YOU ARE STILL HOLDING the 1000 char string
    > that takes about 2040 bytes.



    No you aren't.
    Where are you receiving this false information?

    --
    Tony Morris
    (BInfTech, Cert 3 I.T.)
    Software Engineer
    (2003 VTR1000F)
    Sun Certified Programmer for the Java 2 Platform (1.4)
    Sun Certified Developer for the Java 2 Platform
    Tony Morris, Jun 22, 2004
    #13
  14. vicky

    Roedy Green Guest

    On Tue, 22 Jun 2004 01:10:55 GMT, NOBODY <antispam@0.0.0.0> wrote or
    quoted :

    >An array costs ~14 +/- 2 bytes , plus the 2 object ref you intent to put
    >in. that is 24 bytes. Writing an object with 2 fields will cost you 8 bytes
    >for the object and 2x4 bytes for the refs, 16 bytes total, and you get
    >compile time safety.
    >
    >concl.: don't use arrays.


    You can get 512 MB of RAM for about $60 US on Ebay.

    The cost of that RAM overhead you are so upset about is

    is $.0000018

    And it is reusable.

    Granted you are possibly an old fart like me and can easily remember
    when RAM prices first dropped below $1 million per megabyte, but they
    CONTINUED dropping.

    back then it would have cost you $15.25.

    People are still often acting as if nothing changed.

    --
    Canadian Mind Products, Roedy Green.
    Coaching, problem solving, economical contract programming.
    See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.
    Roedy Green, Jun 22, 2004
    #14
  15. vicky

    Roedy Green Guest

    Re: impl a collection (watch out for big strings)

    On Tue, 22 Jun 2004 01:18:22 GMT, NOBODY <antispam@0.0.0.0> wrote or
    quoted :

    >If you can't afford this space and agree to get a small perf hit, you
    >can mutate the string with new String(line.getChars()) in which case the
    >class is forced to system.arraycopy() the subsection of char[] for you
    >to protect the immutable string.


    on the other hand if you are going to process the whole thing as a
    zillion substrings then discard it all, it is more efficient NOT to
    use new String. You save the overhead of all that copying and wasted
    duplicate RAM.

    another option is intern.

    See http://mindprod.com/jgloss/intern.html

    --
    Canadian Mind Products, Roedy Green.
    Coaching, problem solving, economical contract programming.
    See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.
    Roedy Green, Jun 22, 2004
    #15
  16. vicky

    Roedy Green Guest

    Re: impl a collection (watch out for big strings)

    On Tue, 22 Jun 2004 01:18:22 GMT, NOBODY <antispam@0.0.0.0> wrote or
    quoted :

    >can mutate the string with new String(line.getChars())


    That's a bit of a misnomer. Nothing is changed. All you do is make an
    immutable copy of part of the original String.

    What you are doing I called "unencumbering" the string.

    --
    Canadian Mind Products, Roedy Green.
    Coaching, problem solving, economical contract programming.
    See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.
    Roedy Green, Jun 22, 2004
    #16
  17. vicky

    Roedy Green Guest

    Re: impl a collection (watch out for big strings)

    On Tue, 22 Jun 2004 11:49:32 +1000, "Tony Morris"
    <> wrote or quoted :

    >No you aren't.
    >Where are you receiving this false information?


    It is correct. Go look at the code for substring.

    and similar code for StringBuffer.toString.

    --
    Canadian Mind Products, Roedy Green.
    Coaching, problem solving, economical contract programming.
    See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.
    Roedy Green, Jun 22, 2004
    #17
  18. vicky

    Tony Morris Guest

    Re: impl a collection (watch out for big strings)

    "Roedy Green" <> wrote in message
    news:...
    > On Tue, 22 Jun 2004 11:49:32 +1000, "Tony Morris"
    > <> wrote or quoted :
    >
    > >No you aren't.
    > >Where are you receiving this false information?

    >
    > It is correct. Go look at the code for substring.
    > and similar code for StringBuffer.toString.


    The original statement was generalised - the topic of this forum is Java so
    it was assumed that the statement was related to Java, in which case, it is
    incorrect.

    Is there a particular VM implementation that behaves in that fashion?
    No VM implementation that I am looking at causes that statement to become
    true (even after being given a context).

    --
    Tony Morris
    (BInfTech, Cert 3 I.T.)
    Software Engineer
    (2003 VTR1000F)
    Sun Certified Programmer for the Java 2 Platform (1.4)
    Sun Certified Developer for the Java 2 Platform
    Tony Morris, Jun 22, 2004
    #18
  19. vicky

    Sudsy Guest

    Roedy Green wrote:
    <snip>
    > You can get 512 MB of RAM for about $60 US on Ebay.
    >
    > The cost of that RAM overhead you are so upset about is
    >
    > is $.0000018
    >
    > And it is reusable.
    >
    > Granted you are possibly an old fart like me and can easily remember
    > when RAM prices first dropped below $1 million per megabyte, but they
    > CONTINUED dropping.
    >
    > back then it would have cost you $15.25.
    >
    > People are still often acting as if nothing changed.


    Roedy: I hate to mention this, but you're one of those people.
    You recently ranted against XML. We can now justify using a text-
    based interchange format precisely because the costs of memory
    and bandwidth have dropped. We previously used various encoded
    formats simply because it was cost-effective. When you've only
    got 2.4 Kb of bandwidth then you've got to pack as much data as
    possible into short messages. It's not so important when you're
    using 2 Mb/s (T1/DS1+) links to the 'net.
    XML combined with base64 encoding also accomodates encryption,
    enveloped, enveloping, whatever. It's a prudent choice for extra-
    net communications. As a text-based format, it also lends itself
    well to secure communications using HTTPS.
    Kind of ironic that you mentioned one of the primary motivators
    for the adoption of XML, eh?
    Sudsy, Jun 22, 2004
    #19
  20. vicky

    Roedy Green Guest

    Re: impl a collection (watch out for big strings)

    On Tue, 22 Jun 2004 13:42:19 +1000, "Tony Morris"
    <> wrote or quoted :

    >Is there a particular VM implementation that behaves in that fashion?
    >No VM implementation that I am looking at causes that statement to become
    >true (even after being given a context).



    Hmm. The String class code has changed. The new code avoids pinning
    large blocks of RAM, but it does more System.arrayCopys.

    public String substring(int beginIndex, int endIndex) {
    if (beginIndex < 0) {
    throw new StringIndexOutOfBoundsException(beginIndex);
    }
    if (endIndex > count) {
    throw new StringIndexOutOfBoundsException(endIndex);
    }
    if (beginIndex > endIndex) {
    throw new StringIndexOutOfBoundsException(endIndex -
    beginIndex);
    }
    return ((beginIndex == 0) && (endIndex == count)) ? this :
    new String(offset + beginIndex, endIndex - beginIndex,
    value);
    }

    Note that new String does not necessarily make a copy, though it does
    create a new String object.

    public String(String original) {
    this.count = original.count;
    if (original.value.length > this.count) {
    // The array representing the String is bigger than the
    new
    // String itself. Perhaps this constructor is being
    called
    // in order to trim the baggage, so make a copy of the
    array.
    this.value = new char[this.count];
    System.arraycopy(original.value, original.offset,
    this.value, 0, this.count);
    } else {
    // The array representing the String is the same
    // size as the String, so no point in making a copy.
    this.value = original.value;
    }

    Similarly to the way a StringBuffer temporarily gets turned to a
    String after a toString until it is changed is gone.

    The question now is, when did it change?

    This is the sort of thing I would have dug into in Java 1.0.2 days.

    It happened somewhere between then and Java 1.4.2_04.
    --
    Canadian Mind Products, Roedy Green.
    Coaching, problem solving, economical contract programming.
    See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.
    Roedy Green, Jun 22, 2004
    #20
    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. iksrazal
    Replies:
    0
    Views:
    377
    iksrazal
    Aug 21, 2003
  2. Jochen Riekhof
    Replies:
    2
    Views:
    540
    Roedy Green
    Sep 18, 2005
  3. Timo Qvist

    STL hash_set problem, SGI impl

    Timo Qvist, Nov 18, 2004, in forum: C++
    Replies:
    1
    Views:
    869
    Victor Bazarov
    Nov 18, 2004
  4. Replies:
    0
    Views:
    452
  5. Øyvind Isaksen
    Replies:
    1
    Views:
    967
    Øyvind Isaksen
    May 18, 2007
Loading...

Share This Page