«

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.

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

"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:4b4ab939-2548-422f-becb-...
>>>>> 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

On Jul 15, 10:04*am, Mark Space <marksp...@sbc.global.net> 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 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

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

Tegiri Nenashi wrote:
> On Jul 15, 10:04 am, Mark Space <marksp...@sbc.global.net> 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.

On Jul 15, 2:54*pm, Mark Space <marksp...@sbc.global.net> wrote:
> Tegiri Nenashi wrote:
> > On Jul 15, 10:04 am, Mark Space <marksp...@sbc.global.net> 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.

On Jul 15, 1:01*pm, con...@lewscanon.com 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 <> 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).