Impl of a list of key/value pairs (and more ?)

Discussion in 'Java' started by Sébastien de Mapias, Jul 15, 2008.

  1. Hello,
    I'd like to be able to play with the following structure:
    struct { ("abc", 987), ("oiu", 567), ("abc", 123), ("zye", 234), ...}
    i.e. some kind of 2-dimensional array of keys/values or objects...
    (or struct { ("abc", "987"), ("oiu", "567") etc. as one can't have
    arrays of data of different types)

    As you can see it may contain duplicates (on either side of the
    'pairs').

    And it would be nice too to retrieve a pair through the means of
    an index:
    Object[] obj = struct.get(2)
    => obj[0] would be "oiu", while obj[1] would equal 567 (or "567",
    to make it possible: String[] obj = struct.get(2)).

    I found nothing in the standard util API that might help me.
    Nobody ever saw something similar somewhere ?

    Thanks in advance.
    SR
    Sébastien de Mapias, Jul 15, 2008
    #1
    1. Advertising

  2. "Sébastien de Mapias" <> wrote in message
    news:...
    > Hello,
    > I'd like to be able to play with the following structure:
    > struct { ("abc", 987), ("oiu", 567), ("abc", 123), ("zye", 234), ...}
    > i.e. some kind of 2-dimensional array of keys/values or objects...
    > (or struct { ("abc", "987"), ("oiu", "567") etc. as one can't have
    > arrays of data of different types)
    >
    > As you can see it may contain duplicates (on either side of the
    > 'pairs').
    >
    > And it would be nice too to retrieve a pair through the means of
    > an index:
    > Object[] obj = struct.get(2)
    > => obj[0] would be "oiu", while obj[1] would equal 567 (or "567",
    > to make it possible: String[] obj = struct.get(2)).
    >
    > I found nothing in the standard util API that might help me.
    > Nobody ever saw something similar somewhere ?
    >
    > Thanks in advance.
    > SR


    This scenario could be satisfied by using a Map, where the keys are your
    "abc" or "oiu" strings, and the values are Lists of integers. Write a little
    helper function for adding new key-value pairs.

    AHS
    Arved Sandstrom, Jul 15, 2008
    #2
    1. Advertising

  3. Sébastien de Mapias

    Donkey Hot Guest

    Sébastien de Mapias <> wrote in news:4b4ab939-2548-422f-
    :

    > (or struct { ("abc", "987"), ("oiu", "567") etc. as one can't have
    > arrays of data of different types)


    One can have an array of Objects. Or any other common class.

    But a Map could be your friend, as said.
    Donkey Hot, Jul 15, 2008
    #3
  4. Sébastien de Mapias

    shakah Guest

    On Jul 15, 10:11 am, Donkey Hot <-a-geek.com> wrote:
    > Sébastien de Mapias <> wrote in news:4b4ab939-2548-422f-
    > :
    >
    > But a Map could be your friend, as said.


    Except for the OP's restriction:
    "... it may contain duplicates (on either side of the
    'pairs')."
    shakah, Jul 15, 2008
    #4
  5. Sébastien de Mapias

    Donkey Hot Guest

    Sébastien de Mapias <> wrote in news:4b4ab939-2548-
    :

    > Hello,
    > I'd like to be able to play with the following structure:
    > struct { ("abc", 987), ("oiu", 567), ("abc", 123), ("zye", 234), ...}
    > i.e. some kind of 2-dimensional array of keys/values or objects...
    > (or struct { ("abc", "987"), ("oiu", "567") etc. as one can't have
    > arrays of data of different types)
    >
    > As you can see it may contain duplicates (on either side of the
    > 'pairs').
    >
    > And it would be nice too to retrieve a pair through the means of
    > an index:
    > Object[] obj = struct.get(2)
    >=> obj[0] would be "oiu", while obj[1] would equal 567 (or "567",
    > to make it possible: String[] obj = struct.get(2)).
    >
    > I found nothing in the standard util API that might help me.
    > Nobody ever saw something similar somewhere ?
    >
    > Thanks in advance.
    > SR


    public class KeyValuePair
    {
    private String key ;
    private int value ;

    public KeyValuePair(String key, int value)
    {
    this.key = key ;
    this.value = value;
    }
    // getters and setters if needed
    }

    List struct = new ArrayList();

    struct.add(new KeyValuePair("abc", 987);
    struct.add(new KeyValuePair("oiu", 567);
    struct.add(new KeyValuePair("zye", 124);

    KeyValuePair pair = struct.get(2) ;
    Donkey Hot, Jul 15, 2008
    #5
  6. Sébastien de Mapias

    Donkey Hot Guest

    Donkey Hot <-a-geek.com> wrote in
    news:Xns9ADCAFBE8BA8ESH15SGybs1ysmajw54s5@194.100.2.89:

    > public class KeyValuePair
    > {
    > private String key ;
    > private int value ;
    >
    > public KeyValuePair(String key, int value)
    > {
    > this.key = key ;
    > this.value = value;
    > }
    > // getters and setters if needed
    > }
    >
    > List struct = new ArrayList();
    >
    > struct.add(new KeyValuePair("abc", 987);
    > struct.add(new KeyValuePair("oiu", 567);
    > struct.add(new KeyValuePair("zye", 124);
    >
    > KeyValuePair pair = struct.get(2) ;
    >
    >


    And before someone notices that my code does not compile, I must tell that
    it is not Java, but some pseudo code to illustrate the idea :p

    It converts to Java with

    List<KeyValuePair> struct = new ArrayList<KeyValuePair>();
    Donkey Hot, Jul 15, 2008
    #6
  7. "Eric Sosman" <> wrote in message
    news:1216131788.444181@news1nwk...
    > Arved Sandstrom wrote:
    >> "Sébastien de Mapias" <> wrote in message
    >> news:...
    >>> Hello,
    >>> I'd like to be able to play with the following structure:
    >>> struct { ("abc", 987), ("oiu", 567), ("abc", 123), ("zye", 234), ...}
    >>> i.e. some kind of 2-dimensional array of keys/values or objects...
    >>> (or struct { ("abc", "987"), ("oiu", "567") etc. as one can't have
    >>> arrays of data of different types)
    >>>
    >>> As you can see it may contain duplicates (on either side of the
    >>> 'pairs').
    >>>
    >>> And it would be nice too to retrieve a pair through the means of
    >>> an index:
    >>> Object[] obj = struct.get(2)
    >>> => obj[0] would be "oiu", while obj[1] would equal 567 (or "567",
    >>> to make it possible: String[] obj = struct.get(2)).
    >>>
    >>> I found nothing in the standard util API that might help me.
    >>> Nobody ever saw something similar somewhere ?
    >>>
    >>> Thanks in advance.
    >>> SR

    >>
    >> This scenario could be satisfied by using a Map, where the keys are your
    >> "abc" or "oiu" strings, and the values are Lists of integers. Write a
    >> little helper function for adding new key-value pairs.

    >
    > You seem to have overlooked the "may contain duplicates"
    > part of the problem description.
    > --
    >


    I think my suggestion works. Duplicate keys (e.g. "abc" and "abc") are
    handled by having Lists of integers as the values in the first place. Lists
    themselves allow duplicate elements.

    My first code example does just this:

    import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.Map;

    public class ArrayValue {

    public static void main(String[] args) {
    Map<String, ArrayList<Integer>> test = new HashMap<String,
    ArrayList<Integer>>();

    insert(test, "abc", 10);
    insert(test, "abc", 15);
    insert(test, "oiu", -2);
    insert(test, "abc", 10);
    insert(test, "xyz", 55);
    insert(test, "oiu", -2);

    System.out.println(test.toString());
    }

    private static void insert(Map<String, ArrayList<Integer>> m, String
    key, Integer value) {
    ArrayList<Integer> list = null;
    if (m.get(key) == null) {
    list = new ArrayList<Integer>();
    } else {
    list = m.get(key);
    }
    list.add(value);
    m.put(key, list);
    }
    }

    with an output of

    {abc=[10, 15, 10], oiu=[-2, -2], xyz=[55]}

    This could be finetuned yet further, in case large numbers of duplicate
    values (for given keys) are expected, but the core code already satisfies
    the requirement.

    AHS
    Arved Sandstrom, Jul 15, 2008
    #7
  8. On Jul 15, 6:32 am, Sébastien de Mapias <> wrote:
    > Hello,
    > I'd like to be able to play with the following structure:
    > struct { ("abc", 987), ("oiu", 567), ("abc", 123), ("zye", 234), ...}
    > i.e. some kind of 2-dimensional array of keys/values or objects...
    > (or struct { ("abc", "987"), ("oiu", "567") etc. as one can't have
    > arrays of data of different types)
    >
    > As you can see it may contain duplicates (on either side of the
    > 'pairs').
    >
    > And it would be nice too to retrieve a pair through the means of
    > an index:
    > Object[] obj = struct.get(2)
    > => obj[0] would be "oiu", while obj[1] would equal 567 (or "567",
    > to make it possible: String[] obj = struct.get(2)).
    >
    > I found nothing in the standard util API that might help me.
    > Nobody ever saw something similar somewhere ?
    >
    > Thanks in advance.
    > SR


    Duplicates on value sude is not a problem. For duplicate keys you'll
    have to do some hack, like concatenating each key with unique postfix,
    which can be for example a generated sequencwe number. Then you do a
    range search on keys, to extract the value.
    Tegiri Nenashi, Jul 15, 2008
    #8
  9. Sébastien de Mapias

    Mark Space Guest

    Sébastien de Mapias wrote:
    > Hello,
    > I'd like to be able to play with the following structure:
    > struct { ("abc", 987), ("oiu", 567), ("abc", 123), ("zye", 234), ...}
    > i.e. some kind of 2-dimensional array of keys/values or objects...
    > (or struct { ("abc", "987"), ("oiu", "567") etc. as one can't have
    > arrays of data of different types)


    One can't?

    What does "Object [][] struct;" do?


    >
    > As you can see it may contain duplicates (on either side of the
    > 'pairs').
    >
    > And it would be nice too to retrieve a pair through the means of
    > an index:


    An array like above would work, but Lists are better, as they expand as
    needed, and the Collection API is quite versatile. It's kind of a
    bummer that Java doesn't have any kind of "Pair" object in the standard
    API. But making your own is utterly trivial, which is I'm sure why the
    language designers skipped adding one.

    See Donkey Hot's List example, it seems to be exactly what you need. I
    think folks got confused because your request was so simple. A Map is
    overkill if you just need index look-up.
    Mark Space, Jul 15, 2008
    #9
  10. Sébastien de Mapias

    Stefan Ram Guest

    rossum <> writes:
    >You seem to want a Map that allows duplicate keys.


    Duplicate keys are also supported by Junotal:

    System.out.println( room( "< a=b a=c >" ).getValues( "a" ));

    [b, c]

    http://www.purl.org/stefan_ram/pub/junotal_tutorial

    Junotal even accepts duplicate values for duplicate keys:

    System.out.println( room( "< a=b a=b >" ).getValues( "a" ));



    Since the values of a key are deemed to be a set, here the set
    of values for the key »"a"« only has one element, even though
    it was given twice.

    (However, I am not sure whether this is what the OP wanted.)
    Stefan Ram, Jul 15, 2008
    #10
  11. Sébastien de Mapias

    Stefan Ram Guest

    Eric Sosman <> writes:
    >simultaneously ... Maybe it would be a Good Thing if the O.P.
    >were to describe the larger problem he wants to solve instead
    >of the data structure he's dreamed up to solve it with.


    Or else, - if he still wants to described the object he's
    dreamed up - the best thing would be that he provides

    - the interface (including JavaDoc) to be implemented and
    - a unit test for this interface.

    Then, one could write an implementation against this without
    the additional need to interpret an natural language question.
    Stefan Ram, Jul 15, 2008
    #11
  12. Sébastien de Mapias

    Tom Anderson Guest

    On Tue, 15 Jul 2008, Peter Duniho wrote:

    > On Tue, 15 Jul 2008 07:24:12 -0700, Eric Sosman <> wrote:
    >
    >> [...]
    >>> This scenario could be satisfied by using a Map, where the keys are your
    >>> "abc" or "oiu" strings, and the values are Lists of integers. Write a
    >>> little helper function for adding new key-value pairs.

    >>
    >> You seem to have overlooked the "may contain duplicates"
    >> part of the problem description.

    >
    > It seems to me that Arved's suggestion to use "Lists of integers" as the
    > value for each key would address that.


    Sets of integers would probably be even better.

    Although i think we all misunderstood just what it was the OP wanted.

    tom

    --
    As Emiliano Zapata supposedly said, "Better to die on your feet than
    live on your knees." And years after he died, Marlon Brando played him
    in a movie. So just think, if you unionize, Marlon Brando might play
    YOU in a movie. Even though he's dead. -- ChrisV82
    Tom Anderson, Jul 15, 2008
    #12
  13. "Eric Sosman" <> wrote in message
    news:1216141603.497555@news1nwk...
    > Arved Sandstrom wrote:
    >> "Eric Sosman" <> wrote in message
    >> news:1216131788.444181@news1nwk...
    >>> Arved Sandstrom wrote:
    >>>> "Sébastien de Mapias" <> wrote in message
    >>>> news:...
    >>>>> Hello,
    >>>>> I'd like to be able to play with the following structure:
    >>>>> struct { ("abc", 987), ("oiu", 567), ("abc", 123), ("zye", 234), ...}
    >>>>> i.e. some kind of 2-dimensional array of keys/values or objects...
    >>>>> (or struct { ("abc", "987"), ("oiu", "567") etc. as one can't have
    >>>>> arrays of data of different types)
    >>>>>
    >>>>> As you can see it may contain duplicates (on either side of the
    >>>>> 'pairs').
    >>>>>
    >>>>> And it would be nice too to retrieve a pair through the means of
    >>>>> an index:
    >>>>> Object[] obj = struct.get(2)
    >>>>> => obj[0] would be "oiu", while obj[1] would equal 567 (or "567",
    >>>>> to make it possible: String[] obj = struct.get(2)).
    >>>>>
    >>>>> I found nothing in the standard util API that might help me.
    >>>>> Nobody ever saw something similar somewhere ?
    >>>>>
    >>>>> Thanks in advance.
    >>>>> SR
    >>>> This scenario could be satisfied by using a Map, where the keys are
    >>>> your "abc" or "oiu" strings, and the values are Lists of integers.
    >>>> Write a little helper function for adding new key-value pairs.
    >>> You seem to have overlooked the "may contain duplicates"
    >>> part of the problem description.

    >>
    >> I think my suggestion works. Duplicate keys (e.g. "abc" and "abc") are
    >> handled by having Lists of integers as the values in the first place.
    >> Lists themselves allow duplicate elements.

    >
    > *I* seem to have overlooked a few things. Sorry for my
    > over-hasty (mis)reading of your post.
    >
    > There's still the "access by index" requirement to worry
    > about, though. LinkedHashMap is all well and good, but I don't
    > see how it could associate the key "abc" with indices 0 and 2
    > simultaneously ... Maybe it would be a Good Thing if the O.P.
    > were to describe the larger problem he wants to solve instead
    > of the data structure he's dreamed up to solve it with.


    I tend to agree. I mean, most of us can figure out one way or another of
    creating a "collection" and faking out any access mechanism asked for, but
    without a perspective on the original problem what's the point? Is it that
    access would be required using both the key (e.g "abc") *and* an index
    (presumably by order of addition)? You could do it, but is it the best
    solution for the problem?

    AHS
    Arved Sandstrom, Jul 15, 2008
    #13
  14. On Jul 15, 10:04 am, Mark Space <> wrote:
    > I
    > think folks got confused because your request was so simple.  A Map is
    > overkill if you just need index look-up.


    You do realize that Map, e.g. TreeMap gives you logarithmic access
    time?
    Tegiri Nenashi, Jul 15, 2008
    #14
  15. Sébastien de Mapias

    Guest

    Tegiri Nenashi wrote:
    > You do realize that Map, e.g. TreeMap gives you logarithmic access
    > time?


    Not true. HashMap gives O(1) access time. You are correct about
    TreeMap, but not to generalize that to all Maps.

    --
    Lew
    , Jul 15, 2008
    #15
  16. Sébastien de Mapias

    Guest

    Arved Sandstrom wrote:
    >> This scenario could be satisfied by using a Map, where the keys are
    >> your "abc" or "oiu" strings, and the values are Lists of integers.
    >> Write a little helper function for adding new key-value pairs.


    The points others have made about the vagueness of the requirement are
    valuable. Based on what we do know, I'd generalize Arved's suggestion
    to Map <String, Collection<Integer>>.

    --
    Lew
    , Jul 15, 2008
    #16
  17. Sébastien de Mapias

    Mark Space Guest

    Tegiri Nenashi wrote:
    > On Jul 15, 10:04 am, Mark Space <> wrote:
    >> I
    >> think folks got confused because your request was so simple. A Map is
    >> overkill if you just need index look-up.

    >
    > You do realize that Map, e.g. TreeMap gives you logarithmic access
    > time?
    >


    And do you realize that a List, like ArraryList, gives k * O(1) for
    lookup, with a very small k value to multiply that? (Unlike HashMap,
    where the kO(1) will have a somewhat larger k.)

    Inserts into an ArrayList I think are O(n) because the whole list might
    need to be copied. OTOH, if the problem allows you to predict the total
    array size needed, then insertion into an ArrayList is O(1) also.

    I didn't see where the OP asked for ordered retrieval (which is what
    TreeMap gives you). Just indexed retrieval.
    Mark Space, Jul 15, 2008
    #17
  18. On Jul 15, 2:54 pm, Mark Space <> wrote:
    > Tegiri Nenashi wrote:
    > > On Jul 15, 10:04 am, Mark Space <> wrote:
    > >> I
    > >> think folks got confused because your request was so simple.  A Map is
    > >> overkill if you just need index look-up.

    >
    > > You do realize that Map, e.g. TreeMap gives you logarithmic access
    > > time?

    >
    > And do you realize that a List, like ArraryList, gives k * O(1) for
    > lookup, with a very small k value to multiply that?  (Unlike HashMap,
    > where the kO(1) will have a somewhat larger k.)


    Array is indexed by non-negative integers, and there supposed to be no
    gaps (try putting two pairs (1, "a") and (10000000,"b") into an
    array). Therefore, "array as a map" works in a very-very narrow
    scope.

    > Inserts into an ArrayList I think are O(n) because the whole list might
    > need to be copied.  OTOH, if the problem allows you to predict the total
    > array size needed, then insertion into an ArrayList is O(1) also.
    >
    > I didn't see where the OP asked for ordered retrieval (which is what
    > TreeMap gives you).  Just indexed retrieval.


    Tree map allows index range scan lookup. Suppose you have two
    pairs("a", 10) and ("a", 20) and want to extract both by the key "a".
    It is impossible to have these pairs in any kind of map, but one can
    store something like ("a1", 10) and ("a2", 20) instead. Then, you
    lookup the set of values between "a" and "az"(inclusive), where z is
    the last symbol in the ASCII range, or between "a" and "b"(exclusive).
    I assume that off-the-shelf classes that were mentioned elsewhere in
    the thread shield these details from the user.
    Tegiri Nenashi, Jul 16, 2008
    #18
  19. On Jul 15, 1:01 pm, wrote:
    > Tegiri Nenashi wrote:
    > > You do realize that Map, e.g. TreeMap gives you logarithmic access
    > > time?

    >
    > Not true.  HashMap gives O(1) access time.  You are correct about
    > TreeMap, but not to generalize that to all Maps.


    I suggest the O notation doesn't really work for HashMap. Consider
    HashMap with lookup table size k. Then for an input n < k we indeed
    have constant access time. For large input n >> k the access time
    becomes linear. And the O notation is an approximation of the
    complexity function when input is assumed to grow infinitely large.
    Therefore, the HashMap gives you O(n) access time.

    Any programmatic solution that includes arbitrary constant doesn't
    scale. HashMaps don't scale, while red-black trees do. In database
    field, hash indexes are gone forever. I suggest we deprecate HashMaps
    as well.
    Tegiri Nenashi, Jul 16, 2008
    #19
  20. Sébastien de Mapias

    Stefan Ram Guest

    Tegiri Nenashi <> writes:
    >Array is indexed by non-negative integers, and there supposed
    >to be no gaps (try putting two pairs (1, "a") and
    >(10000000,"b") into an array).


    This holds for the Java language concept of an »array«.

    The general term »array« includes sparse arrays.

    http://en.wikipedia.org/wiki/Sparse_array

    One can see an array as an interface or as an implementation.

    A sparse array (interface) might be implemented with a hash
    map (implementation).
    Stefan Ram, Jul 16, 2008
    #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. heromull
    Replies:
    1
    Views:
    375
    Malik Asif Joyia
    Feb 24, 2005
  2. Florian Lindner

    key - key pairs

    Florian Lindner, Jun 23, 2005, in forum: Python
    Replies:
    8
    Views:
    543
    Paul McGuire
    Jun 24, 2005
  3. Markus Dehmann

    key-value pairs: key consists of 3 ints

    Markus Dehmann, Jan 15, 2006, in forum: C++
    Replies:
    13
    Views:
    627
    Richard Herring
    Jan 23, 2006
  4. Lloyd Dupont
    Replies:
    3
    Views:
    1,294
    Rick Strahl [MVP]
    Apr 28, 2007
  5. Antonio Quinonez
    Replies:
    2
    Views:
    156
    Antonio Quinonez
    Aug 14, 2003
Loading...

Share This Page